[Data Structure] Binary Search Tree - 이진 탐색트리

이진 탐색트리란? - BST (Binary Search Tree)

그림 1. 이진 탐색트리 (이미지 출처 : 위키피디아)

 이진 탐색트리는 트리 구조로써 한 노드가 자신보다 작은 값을 가진 Left Child와 자신보다 큰 값을 가진 Right Child 두 노드를 가지는 구조를 말한다.

 탐색 시에 값의 대소비교를 통해 자식 노드를 탐색하면서 값을 찾아내므로 탐색 횟수가 일반적인 트리구조(한쪽으로 치우쳐 있지 않은)의 깊이인 log 2의 N과 같다고 볼 수 있기 때문에 O(log N)의 시간 복잡도를 가진다.

이진 탐색 트리의 특징

 1. 이진 탐색트리는 DFS로 탐색하며 값을 출력했을 경우 오름차순으로 출력된다는 특징이 있다.

 2. 이미 정렬되어 있는 값을 넣는 경우, 한쪽으로 치우치게 자식이 만들어지므로 탐색시간이 N으로 늘어나게 된다.

 3. 한 노드 A의 왼쪽 서브트리의 모든 값은 A보다 작아야하며, A의 오른쪽 서브트리의 모든 값은 A보다 커야한다.

이진 탐색트리의 삽입과 삭제

삽입

 삽입의 경우 노드가 비어있으면 값을 대입하고, 그렇지 않으면 노드의 값과 비교해 작으면 왼쪽 자식트리로, 크면 오른쪽 자식트리로 이동하면 된다.

삭제

그림 2. 이진 탐색트리의 삭제 (이미지 출처 : 위키피디아)

 맨 아래 노드를 삭제하는 경우 문제가 없지만 중간 노드를 제거하면 중간 노드가 비어버리는 문제점이 있다.

 이 경우는 해당 노드의 왼쪽 서브트리의 최대값이나 오른쪽 서브트리의 최소값을 넣어주면 된다. 

 이진 탐색트리임을 증명하기 위해서는 1이나 3의 조건이 맞는지 확인하면 된다. 1의 경우 모든 노드에 대해 검사를 해야 하므로 시간이 많이 걸리지만 3의 경우 노드 갯수만큼 탐색을 하면 되므로 시간이 방법 1보다 적게 걸린다.

 특징 2를 해결하기 위해서는 어떻게 해야 할까?

 

 고민해 보았으나 트리의 치우침 정도를 계속 감시하면서 (x번 이상 오른쪽 트리 삽입을 했는지 검사) 중간값을 root 노드로 잡고 트리를 재구성하면 된다 생각했으나 삽입이 잦은경우 이 방법이 문제가 된다.

 하지만 레드블랙 트리라는 이진탐색트리의 진화형이 존재한다. 이것을 사용하면 항상 균형있는 형태의 트리 구조를 유지하게 되므로 최악 N의 시간 복잡도를 가지게 되진 않는다. 실제로 레드블랙 트리는 self-balancing BST 라고도 불린다