Open Eunice0927 opened 5 months ago
1. 개요 2. 트리란 무엇인가 3. 바이너리 트리와 바이너리 서치 트리 4. 데이터 검색 시간 복잡도 5. 데이터 삽입과 시간 복잡도 6. 데이터 삭제와 시간 복잡도 7. 바이너리 서치 트리의 단점과 균형 바이너리 트리 8. 참고자료
Binary Search Tree는 약자로 BST, 한글로 이진 탐색 트리라고도 한다.
이미지 출처: https://velog.io/@kwontae1313/트리Tree에-대해서-알아보자
우리가 자주 사용하는 배열은 선형 자료구조의 대표적인 예시로, 특정 데이터를 검색할 때 순서대로 자료를 찾아나가야 한다는 점과 같은 제한적인 구조를 가지고 있다.
선형 자료구조의 대표적인 문제로는 계층적 문제와 순환 종속성 문제가 있다.
먼저 계층적 문제는 계층적인 속성을 가지는 자료를 선형 구조로 표현하기 어렵다는 것을 의미한다.
아래와 같은 조직도가 대표적인 예시이다.
부사장>홍보부>언론팀>전략팀>IT부>DB>업무지원 순으로 선형적으로 표시한다면 홍보부가 IT부보다 상위 계층에 속하는 것 처럼 표시될 수 있다는 한계를 가진다.
이미지 출처: https://maloveforme.tistory.com/69
다음으로 순환 종속성 문제는 두 개 이상의 요소가 서로 순환적으로 의존하여 발생하는 문제를 의미한다.
아래와 같은 관계도를 선형 구조로 표시한다면 내가 친구1, 친구2, 엄마, 아빠 모두와 관계가 있다는 것을 표시하기 어려울 것이다.
위에서 살펴 본 예시 중 계층적 문제는 비선형 자료구조 중 트리로, 순환 종속성 문제는 그래프로 표현해 볼 수 있다.
오늘은 이 중 트리에 대해 알아볼 것이다.
트리는 node와 edge로 이루어진 사이클을 이루지 않는 비선형 자료구조이다.
트리의 중요한 특징으로는 세 가지가 있다.
그림으로 표시하면 아래와 같다.
이미지 출처: https://pooh-footprints.tistory.com/entry/Swift-자료구조-이진-탐색트리-Binary-Search-Tree 그래프는 node와 branch로 이루어진 비선형 자료구조이다. 그래프와 트리의 대표적인 차이점으로는 그래프는 사이클이 가능하고, 루트 노드의 개념이 없다는 점이 있다. 이미지 출처: https://velog.io/@kwontae1313/트리와-그래프에-대해-알아보자
이미지 출처: https://pooh-footprints.tistory.com/entry/Swift-자료구조-이진-탐색트리-Binary-Search-Tree
그래프는 node와 branch로 이루어진 비선형 자료구조이다. 그래프와 트리의 대표적인 차이점으로는 그래프는 사이클이 가능하고, 루트 노드의 개념이 없다는 점이 있다.
이미지 출처: https://velog.io/@kwontae1313/트리와-그래프에-대해-알아보자
이제 트리가 뭔지 대충 감을 잡았다면 오늘의 주제인 바이너리 서치 트리에 대해 알아보자.
바이너리 서치 트리는 바이너리 트리의 일종이며, 바이너리 트리는 한 부모 노드가 최대 두 개의 자식 노드를 가지는 트리를 말한다.
그 중에서도 바이너리 서치 트리는 모든 노드에 중복 값이 존재하지 않으며 left node는 부모 노드보다 작은 값을, right node는 큰 값을 가지는 형태의 바이너리 트리이다.
바이너리 서치 트리의 장점은 데이터 삽입, 탐색, 삭제의 속도가 선형 자료 구조보다 개선되었다는 점이다.
아래와 같이 바이너리 서치 트리와 정렬된 배열에서 27이라는 값을 탐색하는 속도를 비교 해 볼 수 있다.
잘 만들어진 바이너리 서치 트리는 배열보다 월등히 빠른 탐색 속도를 가진다는 점을 알 수 있다.
이미지 출처: https://www.mathwarehouse.com/programming/gifs/binary-search-tree.php#binary-search-tree-insertion-node
그렇다면 바이너리 서치 트리의 시간 복잡도는 어떻게 될까?
결론부터 말하면 바이너리 서치 트리에서 데이터를 검색, 삽입, 삭제하는 평균 시간 복잡도는 $O(logN)$이다.
그 중 검색 속도부터 자세히 알아보자.
검색 속도는 위에서 본 바와 같이 트리를 순회하며 타겟 데이터의 위치를 찾는 연산이 필요하므로, 트리의 높이에 비례하여 시간 복잡도가 증가한다.
이미지 출처: https://blog.penjee.com/5-gifs-to-understand-binary-search-tree/#binary-search-tree-insertion-node)
따라서 트리의 높이를 $h$라고 할 때 바이너리 서치 트리의 검색 시간복잡도는 $O(h)$로 표기할 수 있다.
하지만 시간 복잡도는 원소의 개수인 $n$으로 표기할 때 조금 더 좋은 표현이라고 할 수 있으므로 $n$으로 치환해보도록 하겠다.
높이가 $h$인 트리의 최대 노드의 개수 $n$은 $1+2+4+8+...+2^{h-1}$ 으로 등비수열 합공식(자세한 합공식 유도 방법은 🔗링크 참고)에 따라 $2^h - 1$이 된다.
계산을 이어나가보면 아래와 같은 계산을 거쳐 $O(h) = O(logN)$이 된다는 것을 알 수 있다.
$$n = 2^h-1$$ $$2^h = n+1$$ $$h = log(n+1)$$
이 때 $log(N+1)$이 아닌 $logN$이 되는 이유는 Big-O 표기법이 가장 큰 영향을 주는 항만 계산하는 점근적 표기법에 해당되기 때문이다.
예시의 트리는 $2^4-1=15$개의 노드를 가진다.
트리에 새로운 데이터는 어떻게 삽입하게 될까?
데이터 검색 과정에 새로운 노드를 추가하는 단계 하나만 추가되면 된다.
예를 들어 위와 같은 트리에 35라는 값을 가지는 노드를 삽입해보자.
루트 노드인 20에서 출발하여 더이상 갈 수 없으면 그 곳에 삽입을 하게 된다.
검색때와 동일하게 트리의 높이 $h$만큼 탐색을 하게 됨을 알 수 있다.
이 때 데이터를 추가하는 과정은 $O(1)$만큼의 시간 복잡도를 가지는데, 이는 점근적 표기법에 따라 무시된다.
따라서 데이터를 삽입하는 평균 시간 복잡도는 $O(logN)$이다.
바이너리 서치 트리에서 데이터를 삭제하는 상황에는 세 가지 경우가 존재한다.
이 경우는 삭제할 노드의 부모 노드와 자식 노드간의 연결을 끊어주면 된다.
예를 들어 트리에서 7이라는 노드를 삭제 할 경우 8의 자식 노드에 해당되는 값을 nil처리 하여 7과의 연결을 해제할 수 있다.
이 경우 시간복잡도는 데이터를 삽입할 때와 동일하게 데이터를 검색하는 과정에 연결을 해제하는 $O(1)$만큼의 과정이 추가되므로 평균 시간 복잡도는 $O(logN)$이 된다.
삭제할 노드 a의 부모 노드의 자식 노드를 본인에서 삭제할 노드 a의 자식 노드로 변경 해 주면 된다.
예를 들어 아래의 그래프에서 노드 40을 삭제 할 경우, 해당 노드의 부모 노드인 20의 자식 노드를 기존 40에서 본인의 자식 노드인 30으로 변경 해 주면 된다.
이 경우 시간복잡도는 데이터를 삽입할 때와 동일하게 데이터를 검색하는 과정에 연결을 변경하는 $O(1)$만큼의 과정이 추가되므로 평균 시간 복잡도는 $O(logN)$이 된다.
자식이 두 개인 노드를 삭제하는 경우는 또 다시 두 가지 방법으로 나누어진다.
첫 번째 방법은 삭제하고자 하는 노드의 left subtree에서 가장 큰 요소와 삭제 할 요소의 자리를 바꾸는 것이고,
두 번째 방법은 삭제하고자 하는 노드의 right subtree에서 가장 작은 요소와 삭제 할 요소의 자리를 바꾸는 것이다. 먼저 첫 번째 방법부터 자세히 살펴보자.
트리에서 노드 10을 삭제하기로 한다.
전체 트리에서 10을 찾는다. → 시간복잡도 $O(logN)$
10의 left subtree에서 가장 큰 값, 즉 마지막 right child를 찾는다. → 시간복잡도 $O(logN)$
마지막 right child인 8의 부모 노드를 20, 자식 노드를 6으로 참조값을 변경한다. → 시간복잡도 $O(log1)$
마지막 right child의 left child가 있다면 right child 의 부모 노드와 연결 해 준다. → 시간복잡도 $O(log1)$
두 번째 방법도 첫 번째 방법과 거의 유사하다.
이번에는 노드 20을 삭제하기로 한다.
전체 트리에서 20을 찾는다. → 시간복잡도 최대 $O(logN)$
20의 right subtree에서 가장 작은 값, 즉 마지막 left child를 찾는다. → 시간복잡도 $O(logN)$
마지막 left child인 25를 root 노드가 되고, 자식 노드를 40으로 참조값을 변경한다. → 시간복잡도 $O(log1)$
위 두 경우의 시간복잡도는 각각 $O(log(2N+2))$와 $O(log2N)$인데 두 경우 모두 점근적 표기법에 따라 $O(logN)$이 된다.
따라서 최종적으로 바이너리 서치 트리의 검색, 삽입, 삭제시 시간복잡도는 $O(logN)$이다.
바이너리 서치 트리 의 시간복잡도는 $O(logN)$이라고 지금까지 설명했지만 사실 최악의 경우는 $O(N)$이 나온다.
간단한 예로 트리가 아래와 같이 편향된 모양의 바이너리 서치 트리가 있다고 가정해보자.
이 트리에 새로운 값 6을 삽입하려면 $h$만큼 탐색을 하게 되고 $h=n$으로 결국 $O(N)$만큼의 시간 복잡도를 가지게 된다.
Big-O 표기법은 최악의 시간인 경우로 표기해야 하므로 엄밀히 따지자면 바이너리 서치 트리의 시간복잡도는 $O(N)$가 된다.
이는 배열 등의 선형 자료구조와 동일한 시간복잡도를 가지게 되는 것이다.
그렇다면 원소를 어떤 순서로 삽입하더라도 편향된 모양의 트리가 되지 않게 할 수는 없을까?
컴플리트 바이너리 트리의 모습(바이너리 서치 트리는 컴플리트 바이너리 트리(Complete Binary Tree / 완전 이진 트리) 구조로 쌓아야 원소 개수 N개 대비 최소 높이가 된다.)
모든 노드의 좌우 서브 트리 높이가 1이상 1이상 차이 나지 않는 트리를 Balanced Binary Search Tree(균형 이진 탐색 트리)라고 부른다.
노드의 삽입과 삭제가 일어날 때 균형을 유지하도록 하는 알고리즘을 추가한 균형 이진 탐색 트리에는 대표적으로 AVL 트리와 Red-black 트리가 있다.
AVL 트리와 Red-black 트리에 대해 자세히 알아보고 싶다면 🔗링크를 참고하자.
목차
1. 개요 2. 트리란 무엇인가 3. 바이너리 트리와 바이너리 서치 트리 4. 데이터 검색 시간 복잡도 5. 데이터 삽입과 시간 복잡도 6. 데이터 삭제와 시간 복잡도 7. 바이너리 서치 트리의 단점과 균형 바이너리 트리 8. 참고자료
1. 개요
Binary Search Tree는 약자로 BST, 한글로 이진 탐색 트리라고도 한다.
우리가 자주 사용하는 배열은 선형 자료구조의 대표적인 예시로, 특정 데이터를 검색할 때 순서대로 자료를 찾아나가야 한다는 점과 같은 제한적인 구조를 가지고 있다.
선형 자료구조의 대표적인 문제로는 계층적 문제와 순환 종속성 문제가 있다.
먼저 계층적 문제는 계층적인 속성을 가지는 자료를 선형 구조로 표현하기 어렵다는 것을 의미한다.
아래와 같은 조직도가 대표적인 예시이다.
부사장>홍보부>언론팀>전략팀>IT부>DB>업무지원 순으로 선형적으로 표시한다면 홍보부가 IT부보다 상위 계층에 속하는 것 처럼 표시될 수 있다는 한계를 가진다.
다음으로 순환 종속성 문제는 두 개 이상의 요소가 서로 순환적으로 의존하여 발생하는 문제를 의미한다.
아래와 같은 관계도를 선형 구조로 표시한다면 내가 친구1, 친구2, 엄마, 아빠 모두와 관계가 있다는 것을 표시하기 어려울 것이다.
위에서 살펴 본 예시 중 계층적 문제는 비선형 자료구조 중 트리로, 순환 종속성 문제는 그래프로 표현해 볼 수 있다.
오늘은 이 중 트리에 대해 알아볼 것이다.
2. 트리란 무엇인가
트리는 node와 edge로 이루어진 사이클을 이루지 않는 비선형 자료구조이다.
트리의 중요한 특징으로는 세 가지가 있다.
그림으로 표시하면 아래와 같다.
3. 바이너리 트리와 바이너리 서치 트리
이제 트리가 뭔지 대충 감을 잡았다면 오늘의 주제인 바이너리 서치 트리에 대해 알아보자.
바이너리 서치 트리는 바이너리 트리의 일종이며, 바이너리 트리는 한 부모 노드가 최대 두 개의 자식 노드를 가지는 트리를 말한다.
그 중에서도 바이너리 서치 트리는 모든 노드에 중복 값이 존재하지 않으며 left node는 부모 노드보다 작은 값을, right node는 큰 값을 가지는 형태의 바이너리 트리이다.
바이너리 서치 트리의 장점은 데이터 삽입, 탐색, 삭제의 속도가 선형 자료 구조보다 개선되었다는 점이다.
아래와 같이 바이너리 서치 트리와 정렬된 배열에서 27이라는 값을 탐색하는 속도를 비교 해 볼 수 있다.
잘 만들어진 바이너리 서치 트리는 배열보다 월등히 빠른 탐색 속도를 가진다는 점을 알 수 있다.
그렇다면 바이너리 서치 트리의 시간 복잡도는 어떻게 될까?
결론부터 말하면 바이너리 서치 트리에서 데이터를 검색, 삽입, 삭제하는 평균 시간 복잡도는 $O(logN)$이다.
그 중 검색 속도부터 자세히 알아보자.
4. 데이터 검색 시간 복잡도
검색 속도는 위에서 본 바와 같이 트리를 순회하며 타겟 데이터의 위치를 찾는 연산이 필요하므로, 트리의 높이에 비례하여 시간 복잡도가 증가한다.
따라서 트리의 높이를 $h$라고 할 때 바이너리 서치 트리의 검색 시간복잡도는 $O(h)$로 표기할 수 있다.
하지만 시간 복잡도는 원소의 개수인 $n$으로 표기할 때 조금 더 좋은 표현이라고 할 수 있으므로 $n$으로 치환해보도록 하겠다.
높이가 $h$인 트리의 최대 노드의 개수 $n$은 $1+2+4+8+...+2^{h-1}$ 으로 등비수열 합공식(자세한 합공식 유도 방법은 🔗링크 참고)에 따라 $2^h - 1$이 된다.
계산을 이어나가보면 아래와 같은 계산을 거쳐 $O(h) = O(logN)$이 된다는 것을 알 수 있다.
$$n = 2^h-1$$ $$2^h = n+1$$ $$h = log(n+1)$$
이 때 $log(N+1)$이 아닌 $logN$이 되는 이유는 Big-O 표기법이 가장 큰 영향을 주는 항만 계산하는 점근적 표기법에 해당되기 때문이다.
5. 데이터 삽입과 시간 복잡도
트리에 새로운 데이터는 어떻게 삽입하게 될까?
데이터 검색 과정에 새로운 노드를 추가하는 단계 하나만 추가되면 된다.
예를 들어 위와 같은 트리에 35라는 값을 가지는 노드를 삽입해보자.
루트 노드인 20에서 출발하여 더이상 갈 수 없으면 그 곳에 삽입을 하게 된다.
검색때와 동일하게 트리의 높이 $h$만큼 탐색을 하게 됨을 알 수 있다.
이 때 데이터를 추가하는 과정은 $O(1)$만큼의 시간 복잡도를 가지는데, 이는 점근적 표기법에 따라 무시된다.
따라서 데이터를 삽입하는 평균 시간 복잡도는 $O(logN)$이다.
6. 데이터 삭제와 시간 복잡도
바이너리 서치 트리에서 데이터를 삭제하는 상황에는 세 가지 경우가 존재한다.
1) 자식이 없는 노드(leaf(단말) 노드)를 삭제하는 경우
이 경우는 삭제할 노드의 부모 노드와 자식 노드간의 연결을 끊어주면 된다.
예를 들어 트리에서 7이라는 노드를 삭제 할 경우 8의 자식 노드에 해당되는 값을 nil처리 하여 7과의 연결을 해제할 수 있다.
이 경우 시간복잡도는 데이터를 삽입할 때와 동일하게 데이터를 검색하는 과정에 연결을 해제하는 $O(1)$만큼의 과정이 추가되므로 평균 시간 복잡도는 $O(logN)$이 된다.
2) 자식이 한 개인 노드를 삭제하는 경우
삭제할 노드 a의 부모 노드의 자식 노드를 본인에서 삭제할 노드 a의 자식 노드로 변경 해 주면 된다.
예를 들어 아래의 그래프에서 노드 40을 삭제 할 경우, 해당 노드의 부모 노드인 20의 자식 노드를 기존 40에서 본인의 자식 노드인 30으로 변경 해 주면 된다.
이 경우 시간복잡도는 데이터를 삽입할 때와 동일하게 데이터를 검색하는 과정에 연결을 변경하는 $O(1)$만큼의 과정이 추가되므로 평균 시간 복잡도는 $O(logN)$이 된다.
3) 자식이 두 개인 노드를 삭제하는 경우
자식이 두 개인 노드를 삭제하는 경우는 또 다시 두 가지 방법으로 나누어진다.
첫 번째 방법은 삭제하고자 하는 노드의 left subtree에서 가장 큰 요소와 삭제 할 요소의 자리를 바꾸는 것이고,
두 번째 방법은 삭제하고자 하는 노드의 right subtree에서 가장 작은 요소와 삭제 할 요소의 자리를 바꾸는 것이다.
먼저 첫 번째 방법부터 자세히 살펴보자.
트리에서 노드 10을 삭제하기로 한다.
전체 트리에서 10을 찾는다. → 시간복잡도 $O(logN)$
10의 left subtree에서 가장 큰 값, 즉 마지막 right child를 찾는다. → 시간복잡도 $O(logN)$
마지막 right child인 8의 부모 노드를 20, 자식 노드를 6으로 참조값을 변경한다. → 시간복잡도 $O(log1)$
마지막 right child의 left child가 있다면 right child 의 부모 노드와 연결 해 준다. → 시간복잡도 $O(log1)$
두 번째 방법도 첫 번째 방법과 거의 유사하다.
이번에는 노드 20을 삭제하기로 한다.
전체 트리에서 20을 찾는다. → 시간복잡도 최대 $O(logN)$
20의 right subtree에서 가장 작은 값, 즉 마지막 left child를 찾는다. → 시간복잡도 $O(logN)$
마지막 left child인 25를 root 노드가 되고, 자식 노드를 40으로 참조값을 변경한다. → 시간복잡도 $O(log1)$
위 두 경우의 시간복잡도는 각각 $O(log(2N+2))$와 $O(log2N)$인데 두 경우 모두 점근적 표기법에 따라 $O(logN)$이 된다.
따라서 최종적으로 바이너리 서치 트리의 검색, 삽입, 삭제시 시간복잡도는 $O(logN)$이다.
7. 바이너리 서치 트리의 단점과 균형 바이너리 트리
바이너리 서치 트리 의 시간복잡도는 $O(logN)$이라고 지금까지 설명했지만 사실 최악의 경우는 $O(N)$이 나온다.
간단한 예로 트리가 아래와 같이 편향된 모양의 바이너리 서치 트리가 있다고 가정해보자.
이 트리에 새로운 값 6을 삽입하려면 $h$만큼 탐색을 하게 되고 $h=n$으로 결국 $O(N)$만큼의 시간 복잡도를 가지게 된다.
Big-O 표기법은 최악의 시간인 경우로 표기해야 하므로 엄밀히 따지자면 바이너리 서치 트리의 시간복잡도는 $O(N)$가 된다.
이는 배열 등의 선형 자료구조와 동일한 시간복잡도를 가지게 되는 것이다.
그렇다면 원소를 어떤 순서로 삽입하더라도 편향된 모양의 트리가 되지 않게 할 수는 없을까?
모든 노드의 좌우 서브 트리 높이가 1이상 1이상 차이 나지 않는 트리를 Balanced Binary Search Tree(균형 이진 탐색 트리)라고 부른다.
노드의 삽입과 삭제가 일어날 때 균형을 유지하도록 하는 알고리즘을 추가한 균형 이진 탐색 트리에는 대표적으로 AVL 트리와 Red-black 트리가 있다.
AVL 트리와 Red-black 트리에 대해 자세히 알아보고 싶다면 🔗링크를 참고하자.
8. 참고자료
<트리의 개념>
<시간복잡도>