이진 탐색 트리 (Binary Search Tree)

이진 탐색 트리

이진 탐색 트리는 다음 조건을 만족하는 트리이다.

이진 탐색 트리 예시

• 특정 노드의 자식 노드가 최대 2개인 이진 트리
• 특정 노드의 왼쪽 서브트리에 존재하는 모든 값이 해당 노드의 값보다 작음
• 특정 노드의 오른쪽 서브트리에 존재하는 모든 값이 해당 노드의 값보다 큼

이진 탐색 트리는 최적의 경우, 노드의 개수가 $N$일때 삽입, 삭제, 탐색 모두 $O(\log N)$의 시간복잡도를 갖게 된다. 일반적으로는 트리의 높이를 $h$라고 했을 때, 세 작업 모두 $O(h)$의 시간복잡도를 갖게 된다.

 

이진 탐색 트리의 구현

트리의 기본적인 뼈대를 Python으로 구성하면 아래와 같다. 이때 탐색, 삽입, 제거의 동작을 구현해보자.

class Node:
    def __init__(self, val):
        self.val = val
        self.left_child = None
        self.right_child = None

class BinarySearchTree:
    def __init__(self, root):
        self.root = Node(root)

 

탐색 (Search)

이진 탐색 트리에서의 탐색은 이진 탐색에서의 탐색과 동일하다. 즉, Root 노드부터 시작해서 탐색하고자 하는 값이 해당 노드보다 작으면 왼쪽 자식 노드로, 크다면 오른쪽 자식 노드로 이동하여 구하고자 하는 값이 나올 때까지 반복하면 된다. 이때 더 이상 이동할 수 없다면, 탐색하려는 값이 트리에 존재하지 않는 것으로 볼 수 있다.

class BinarySearchTree:
    ...
    def search(self, value):
        cur_node = self.root
        while cur_node != None:
            if cur_node.val == value:
                return cur_node
            elif cur_node.val > value:
                cur_node = cur_node.left_child
            else:
                cur_node = cur_node.right_child
        return None

 

삽입 (Insert)

Root 노드부터 현재 노드와 입력하고자 하는 값의 대소비교를 통해서 제일 아래쪽 자식 노드(Leaf Node)까지 내려간 후, 해당 Leaf 노드의 값보다 입력할 값이 작으면 왼쪽 자식 노드로, 크면 아래쪽 자식 노드로 삽입하면 된다.

class BinarySearchTree:
    ...
    def insert(self, value):
        cur_node = self.root
        while cur_node.left_child or cur_node.right_child:
            if cur_node.val > value:
                cur_node = cur_node.left_child
            else:
                cur_node = cur_node.right_child

        if cur_node.val > value:
            cur_node.left_child = Node(value)
        else:
            cur_node.right_child = Node(value)

 

삭제 (Delete)

노드의 삭제는 크게 세 가지 경우에서 일어날 수 있다.

1. 삭제하려는 노드의 자식 노드가 0개인 경우, 단순히 해당 노드를 제거하는 것으로 삭제 작업이 끝나게 된다.
2. 삭제하려는 노드의 자식 노드가 1개인 경우, 해당 노드를 지우고, 해당 노드의 자식 노드를 해당 노드의 부모 노드와 연결하면 끝난다.
3. 삭제하려는 노드의 자식 노드가 2개인 경우, 지우려는 노드의 값보다 큰 숫자 중에 제일 작은 숫자를 가진 노드(=Successor)를 해당 위치로 옮기고, 원래 successor에 해당하는 위치의 노드를 삭제한다.

 

삭제의 3번 경우는 어떻게 가능한 것일까?

삭제하려는 노드의 Successor는 항상 자식이 없거나, 오른쪽 자식 노드만 존재(=자식 노드가 1개)하므로 위와 같은 동작이 성립할 수 있다. 만약, Successor의 자식 노드가 2개라고 한다면, 이는 Successor 노드보다 작은 값을 갖는 노드가 존재한다는 것으로 이는 Successor 노드의 정의에 모순하게 된다. 즉, Successor 노드는 특정 노드의 오른쪽 서브트리의 제일 왼쪽에 위치한 노드로 볼 수 있으므로 해당 노드의 삭제는 1번과 2번 경우로 모두 해결 할 수 있게 된다.

 

한계점

이진 탐색 트리는 최적의 경우, 노드의 수가 $N$일 때 모든 동작이 $O(\log N)$의 시간복잡도로 해결될 수 있다. 그러나 최악의 경우에는 이진 탐색 트리의 Root 노드 값이 트리의 최대값 또는 최소값이 될 수 있다. 이런 경우 트리의 높이 $h = N$이 되어 모든 동작이 $O(N)$이 된다. 즉, 최악의 경우에는 연결 리스트와 동일한 구조라고 볼 수 있으며 모든 연산이 비효율적으로 동작하게 된다.

이진 탐색 트리의 시간복잡도

 

자가 균형 이진 탐색 트리 (Self-Balancing BST)

위와 같은 일반 이진 탐색 트리의 한계점을 해결하기 위해, 트리 높이의 불균형이 발생할 때 마다 트리의 구조를 균형으로 바꿔 항상 시간복잡도를 $O(\log N)$으로 유지하도록 하는 트리이다. 대표적인 종류로는 Red-Black Tree, AVL Tree 등이 있다. 아래와 같은 Rotation 동작을 통해서 트리의 높이를 모든 경로에서 항상 균일하게 유지하도록 할 수 있다. 이러한 자가 균형 이진 탐색 트리를 사용할 때 비로소 이진 탐색 트리를 효율적으로 사용할 수 있게 된다.

 

References

• https://ko.wikipedia.org/wiki/이진_탐색_트리
• https://ratsgo.github.io/data%20structure&algorithm/2017/10/22/bst/
• https://engineerinsight.tistory.com/321#💋 노드의 successor (후임자)-1