8 / 14강

탐색 트리와 균형

트리에서 원하는 값을 찾을 때 모든 노드를 살펴봐야 할까요? 작은 값은 왼쪽, 큰 값은 오른쪽에 두면 한쪽을 건너뛸 수 있습니다. 이것이 이진 탐색 트리(BST)의 기본 규칙입니다. 이 수업에서는 중복 값이 없다고 가정합니다.

규칙은 자식 하나에만 적용되지 않습니다

어떤 노드를 기준으로 왼쪽 부분 트리의 모든 값은 더 작고, 오른쪽 부분 트리의 모든 값은 더 큽니다. 바로 옆 자식만 비교해서는 충분하지 않습니다.

      40
     /  \
   20    60
  /  \
 10  30

30을 찾으면 40 → 20 → 30으로 갑니다. 40보다 작으니 왼쪽, 20보다 크니 오른쪽입니다. 60이 있는 쪽은 살펴보지 않습니다.

코드로 찾기

tree = (40, (20, (10, None, None), (30, None, None)),
        (60, None, None))

def contains(node, target):
    while node is not None:
        value, left, right = node
        if target == value:
            return True
        node = left if target < value else right
    return False

print(contains(tree, 30))
print(contains(tree, 50))

결과는 True, False입니다. 탐색 비용은 트리 높이 h에 비례하는 O(h)입니다.

균형이 중요한 이유

10, 20, 30, 40을 차례로 넣어 한쪽으로만 이어지면 연결 리스트와 비슷해집니다. 높이가 n에 가까워져 탐색도 최악에 O(n)입니다. 이진 트리라고 항상 O(log n)인 것은 아닙니다.

AVL 트리는 모든 노드에서 왼쪽과 오른쪽 부분 트리의 높이 차를 1 이하로 유지합니다. 삽입이나 삭제로 기울어지면 회전으로 연결을 조정합니다. 균형을 유지하는 비용을 들여 탐색, 삽입, 삭제를 O(log n)에 처리합니다.

한 노드에 여러 키를 담는 B 트리는 많은 데이터를 블록 단위로 읽는 저장 장치에 쓰입니다. 빈 자식 참조를 순회용 연결로 쓰는 스레드 트리는 또 다른 목적의 변형입니다. 어떤 비용을 줄이려는지부터 구분하세요.

확인 문제

위 트리에서 20의 오른쪽 자리에 45를 넣으면 올바른 탐색 트리일까요?