트리와 이진 탐색 트리

트리

노드로 이루어진 계층형 자료구조로, 계층 관계를 나타낼 때 사용한다. 자식이 없는 노드를 리프 노드(Leaf Node)라고 한다.

이진 트리

각 노드가 최대 두 개의 자식을 갖는 트리이다.

이진 탐색 트리

모든 노드가 특정 순서를 따르는 이진 트리이다. 모든 노드 n에 대해 다음 조건이 반드시 성립한다.

왼쪽 서브트리의 모든 값 <= n < 오른쪽 서브트리의 모든 값

구현

class Node:
    def __init__(self, val):
        self.val = val
        self.leftChild = None
        self.rightChild = None


class BinarySearchTree:
    def __init__(self):
        self.root = None

    def setRoot(self, val):
        self.root = Node(val)

    # 탐색
    def find(self, val):
        return self.findNode(self.root, val) is not None

    def findNode(self, currentNode, val):
        if currentNode is None:
            return None
        elif val == currentNode.val:
            return currentNode
        elif val < currentNode.val:
            return self.findNode(currentNode.leftChild, val)
        else:
            return self.findNode(currentNode.rightChild, val)

    # 삽입
    def insert(self, val):
        if self.root is None:
            self.setRoot(val)
        else:
            self.insertNode(self.root, val)

    def insertNode(self, currentNode, val):
        if val <= currentNode.val:
            if currentNode.leftChild:
                self.insertNode(currentNode.leftChild, val)
            else:
                currentNode.leftChild = Node(val)
        else:
            if currentNode.rightChild:
                self.insertNode(currentNode.rightChild, val)
            else:
                currentNode.rightChild = Node(val)

    # 중위 순회
    def traverse(self):
        return self.traverseNode(self.root)

    def traverseNode(self, currentNode):
        if currentNode is None:
            return []
        result = []
        result.extend(self.traverseNode(currentNode.leftChild))
        result.append(currentNode.val)
        result.extend(self.traverseNode(currentNode.rightChild))
        return result


bst = BinarySearchTree()
for val in [5, 3, 8, 1, 4]:
    bst.insert(val)

print(bst.find(4))     # True
print(bst.traverse())  # [1, 3, 4, 5, 8]

이진 탐색 트리를 중위 순회(왼쪽 → 자신 → 오른쪽)하면 정렬된 결과를 얻는다.

시간 복잡도

탐색은 루트에서 시작해 한 단계씩 내려가므로 트리의 높이 h만큼 걸린다. 트리가 균형 잡혀 있다면 높이가 h일 때 노드 수는 약 2^h개이므로, N = 2^h에서 h = log₂N이다. 따라서 탐색은 O(log N)이다.

한계: 편향된 이진 탐색 트리

이진 탐색 트리에 정렬된 순서(오름차순 또는 내림차순) 로 값을 삽입하면, 노드가 한쪽으로만 붙어 트리가 깊게 자라난다. 이렇게 편향된 트리는 사실상 연결 리스트와 같아져 시간 복잡도가 O(N)으로 증가한다.

이 문제를 해결하기 위해 스스로 높이 균형을 맞추는 균형 이진 탐색 트리가 등장했다.

그래프와 트리의 차이

트리는 그래프의 한 종류이다. 그래프 중에서 모든 노드가 연결되어 있고 사이클이 없는 그래프를 트리라고 한다. 루트가 있는 트리에서는 간선이 부모에서 자식으로 향하는 방향을 가지며, 루트를 제외한 모든 노드의 부모는 정확히 하나이다.