[자료구조] BST : 이진 탐색 트리

이진 트리는 루트 노드를 기준으로 두 개의 서브트리로 나뉘어 진다. 또한 서브트리도 최대 두 개의 서브트리로 나뉘어지는 것을 이진 트리라 한다. 이진 탐색 트리는 정해진 규칙에 의해 이진 트리의 노드에 데이터를 저장하는 기법이다. 이진 탐색 트리를 통해 데이터를 저장하면 원하는 데이터를 찾을 때 효율적으로 찾을 수 있다.

---

이진 탐색 트리의 원리

이진 탐색 트리는 정해진 규칙에 따라 이진 트리에 데이터를 저장한 트리이다. 아래는 이진 탐색 트리를 가장 잘 표현한 것 같아서 첨부한다. 루트 노드를 기준으로 큰 값이 들어오면 오른쪽으로, 작은 값이 들어온다면 왼쪽으로 보내진다. 이를 통해 루트 노드를 기준으로 왼쪽은 작은 값, 오른쪽은 큰 값이 저장된다.

이제 데이터를 찾아야 한다면 아래와 같은 과정을 거치게 된다. 27을 찾아보자. 

루트 노드인 21보다 크기 때문에 오른쪽 서브트리로 이동한다. 이후에 28보다 작기 때문에 왼쪽 서브트리로 이동하며 25와 비교한 후에 27을 찾을 수 있게 된다.

이진 탐색 트리에 저장된 데이터를 찾을 때는 평균 O(logN)의 시간복잡도를 갖게되며 트리가 한쪽으로 치우친 최악 의 경우에는 O(N)의 시간복잡도를 갖는다.

---

코드로 구현하기

python을 통해 이진 탐색 트리를 구현해보자.

 

노드정의

먼저 아래와 같이 class를 통해 노드를 정의한다. 각각의 노드는 왼쪽 노드, 오른쪽 노드가 포함되어 있다.

class Node:
    def __init__(self, data):
        self.left = None
        self.right = None
        self.data = data

 

이진 탐색 트리 정의

이제 이진 탐색 트리에 대해 class로 정의해보자. 인스턴스 생성시에 root라는 최상위 부모 노드를 입력받아 기준점을 정한다.

class BST():
    def __init__(self, root):
        self.root = root

 

노드의 삽입

이진 탐색 트리에 데이터를 넣는 함수는 다음과 같이 재귀함수로 구현하였다. 루트 노드를 10이라 하고 5를 insert한다고 가정해보자. _insert_value 함수를 통해 알맞은 자리에 위치시키는데 data인 5는 node.data의 10보다 작기 때문에 node.left에 삽입한다. 이때 node.left에 데이터가 이미 존재했을 때는 또다시 재귀호출로 위치를 탐색하지만 node.left가 없을 때는 해당 자리에 5를 저장하고 반환한다.

 

최종적으로 insert 함수는 데이터 삽입이 성공했을 때 True를 반환하게 되며 재귀 호출을 통해 입력받은 data의 자리를 찾아서 위치시킨다.

    def insert(self, data):
        self.root = self._insert_value(self.root, data);
        return self.root is not None

    def _insert_value(self, node, data):
        if node is None:
            node = Node(data)
        else:
            if data < node.data:
                node.left = self._insert_value(node.left, data)
            else:
                node.right = self._insert_value(node.right, data)
        return node

 

노드의 탐색

이제 BST에 데이터를 저장했다면 탐색할 수 있어야한다. BST에 특정 데이터가 존재하면 True, 존재하지 않는다면 False를 반환하도록 구현해보자.

 

탐색도 삽입처럼 재귀호출을 통해 이루어진다. 만약 루트 노드가 비어있거나 탐색을 하려는 데이터가 root일 때 True를 반환한다. 이는 재귀호출을 통해 탐색 대상의 데이터를 발견했을 경우를 의미한다. 또한 탐색을 하려는 데이터를 root.data와 비교하여 작다면 왼쪽 노드, 크거나 같다면 오른쪽 노드를 탐색하도록 한다.

    def find(self, key):
        return self._find_value(self.root, key)

    def _find_value(self, root, key):
        if root is None or root.data == key:
            return root is not None
        elif key < root.data:
            return self._find_value(root.left, key)
        else:
            return self._find_value(root.right, key)

 

노드의 삭제

삭제하려는 노드에 자식 노드가 없을 경우 삭제하려는 노드를 None으로 변경하면 된다. 하지만 자식 노드가 있을 경우는 복잡하다. 자식 노드가 하나일 경우 해당 노드를 자식 노드와 교체하면 되고 자식 노드가 두 개일 경우에는 오른쪽 서브트리에서 가장 왼쪽에 있는 노드와 교체한다. 왜냐하면 해당 노드는 삭제하려고하는 노드의 왼쪽 서브트리의 노드보다 크고 오른쪽 서브트리보다는 작기 때문에 새로운 부모 노드가 되기에 적합하다.

 

먼저 삭제하려고 하는 노드를 찾았을 때 자식 노드가 2개인 경우를 보자.

오른쪽 서버트리에서 가장 아래의 왼쪽에 위치하는 노드를 찾는다. 이는 해당 서브트리의 새로운 루트 노드가 된다. 찾은 후에는 child에 저장된다. 이제 child의 왼쪽 노드를 현재 노드의 왼쪽 노드로 교체한다. 

그리고 child의 부모 노드인 parent와 node가 다를 때는 child의 왼쪽 노드를 parent의 왼쪽 노드로 변경하며 child의 오른쪽 노드는 node의 오른쪽 노드로 교체하면서 이진 탐색 트리를 유지시킨다.

 

그리고 삭제하려고 하는 노드를 찾지 못했을 때는 크기 비교 후에 왼쪽 서브트리 또는 오른쪽 서브트리로 이동하여 삭제할 노드를 찾는다.

    def delete(self, key):
        self.root, deleted = self._delete_value(self.root, key)
        return deleted

    def _delete_value(self, node, key):
        if node is None:
            return node, False

        deleted = False
        if key == node.data:
            deleted = True
            # 자식 노드가 2개일 경우
            if node.left and node.right:
                # 오른쪽 서브트리에서 가장 작은 노드를 찾는다.
                parent, child = node, node.right
                while child.left is not None:
                    parent, child = child, child.left
                # 가장 작은 노드의 left를 삭제하려하는 노드의 left로 교체
                child.left = node.left
                if parent != node:
                    parent.left = child.right
                    child.right = node.right
                # 최종적으로 현재 삭제하려는 node를 가장 작은 노드로 교체    
                node = child
            elif node.left or node.right:
                node = node.left or node.right
            else:
                node = None
        elif key < node.data:
            node.left, deleted = self._delete_value(node.left, key)
        else:
            node.right, deleted = self._delete_value(node.right, key)
        return node, deleted

---

정리

• 효율적인 탐색을 위해서는 저장하는 방법도 중요하다.
• 이진 탐색 트리는 루트 노드를 기준으로 작으면 왼쪽, 크면 오른쪽에 저장한다.
• 평균적으로 O(logN), 최악의 경우 O(N)의 시간복잡도를 갖는다.