이진 탐색 트리(Binary Search Tree)

---

모든 노드에 대해서 왼쪽 서브트리에 있는 데이터는 모두 현재 노드의 값보다 작고 오른쪽은 모두 큰 성질을 만족하는 이진트리.

이진탐색과 유사한 점이 많아 이진탐색과 비교해보았습니다.

장점 : 데이터 원소의 추가, 삭제가 용이하다.
단점 : 공간 소요가 큼

이진탐색트리의 추상적 자료구조

---

데이터 표현- 각 노드는 key, value 쌍으로 이루어져있다.
key를 이용해서 검색 가능하다.

이진탐색트리 연산의 정의

• insert(key, data) 데이터원소를 추가
• remove(key)특정 원소 삭제
• lookup(key) 특정 원소 검색
• inorder() 키의 순서대로 원소 나열
• min,max 최소키 최대키를 가지는 원소 탐색

이진탐색트리 구현

---

이진탐색트리 연산중에 대부분 연산들은 간단했지만 remove 연산은 조금 복잡합니다.

루트 노드 또는 내부 노드가 삭제되는 경우에는 다른 노드들을 이리저리 옮겨서 트리의 모습을 갖추도록 구조를 조정해야 하기 때문입니다.

remove를 구현할 때 상황을 정리해 보았습니다.
삭제되는 노드가
1. 말단 (leaf) 노드인 경우
그냥 그 노드를 없애면 된다.
→ 부모 노드의 링크를 조정 (좌? 우?)
→ 삭제되는 노드 (X) 가 root node 인 경우도 특별 처리!

2.자식을 하나 가지고 있는 경우
삭제되는 노드 자리에 그 자식을 대신 배치
→ 자식이 왼쪽? 오른쪽?
→ 부모 노드의 링크를 조정 (좌? 우?)
→ 삭제되는 노드 (X) 가 root node 인 경우, 대신 들어오는 자식이 새로 root가 됨

3.자식을 둘 가지고 있는 경우
삭제되는 노드보다 바로 다음 (큰) 키를 가지는 노드를 찾아
그 노드를 삭제되는 노드 자리에 대신 배치하고
이 노드를 대신 삭제

다음은 remove에 대한 구현입니다.

def remove(self, key):
        node, parent = self.lookup(key)

        if node:
            nChildren = node.countChildren()
            # The simplest case of no children
            if nChildren == 0:
                # 만약 parent 가 있으면
                # node 가 왼쪽 자식인지 오른쪽 자식인지 판단하여
                # parent.left 또는 parent.right 를 None 으로 하여
                # leaf node 였던 자식을 트리에서 끊어내어 없앱니다.
                if parent:
                    if node == parent.right:
                        parent.right = None
                    if node == parent.left:
                        parent.left = None
                # 만약 parent 가 없으면 (node 는 root 인 경우)
                # self.root 를 None 으로 하여 빈 트리로 만듭니다.
                else:
                    self.root = None
            # When the node has only one child
            elif nChildren == 1:
                # 하나 있는 자식이 왼쪽인지 오른쪽인지를 판단하여
                # 그 자식을 어떤 변수가 가리키도록 합니다.
                if node.left:
                    direct = node.left
                else:
                    direct = node.right
                # 만약 parent 가 있으면
                # node 가 왼쪽 자식인지 오른쪽 자식인지 판단하여
                # 위에서 가리킨 자식을 대신 node 의 자리에 넣습니다.
                if parent:
                    if node == parent.right:
                        parent.right = direct
                    else:
                        parent.left = direct
                # 만약 parent 가 없으면 (node 는 root 인 경우)
                # self.root 에 위에서 가리킨 자식을 대신 넣습니다.
                else:
                    self.root = direct
            # When the node has both left and right children
            else:
                parent = node
                successor = node.right
                # parent 는 node 를 가리키고 있고,
                # successor 는 node 의 오른쪽 자식을 가리키고 있으므로
                # successor 로부터 왼쪽 자식의 링크를 반복하여 따라감으로써
                # 순환문이 종료할 때 successor 는 바로 다음 키를 가진 노드를,
                # 그리고 parent 는 그 노드의 부모 노드를 가리키도록 찾아냅니다.
                while successor.left:
                    parent = successor
                    successor = successor.left
                # 삭제하려는 노드인 node 에 successor 의 key 와 data 를 대입합니다.
                node.key = successor.key
                node.data = successor.data
                # 이제, successor 가 parent 의 왼쪽 자식인지 오른쪽 자식인지를 판단하여
                # 그에 따라 parent.left 또는 parent.right 를
                # successor 가 가지고 있던 (없을 수도 있지만) 자식을 가리키도록 합니다.
                    if successor.key == parent.left.key:
                        parent.left = successor.right
                    else:
                        parent.right = successor.right

                return True

---

💡이진탐색트리가 만약에 한줄로 늘어서 있을 때, 탐색 연산 복잡도는 선형 탐색 복잡도와 동일해 진다는 단점을 알았다.