이진 탐색 트리: 작은 것은 왼쪽, 큰 것은 오른쪽

값을 노드에 담아 트리 모양으로 매답니다. 노드마다 지키는 규칙은 하나입니다: 왼쪽 아래는 모두 나보다 작고, 오른쪽 아래는 모두 나보다 큽니다. 그러면 무엇을 찾든 루트에서부터 「작으면 왼쪽, 크면 오른쪽」만 따라 내려가면 됩니다.

한 줄 답. 이진 탐색 트리는 노드마다 왼쪽 서브트리는 모두 작고 오른쪽 서브트리는 모두 크다는 규칙을 지키는 트리입니다. 찾기·넣기·지우기는 루트에서 비교하며 한 층씩 내려가므로 트리의 높이(height, 층 수)만큼 걸립니다. 뒤섞인 순서로 넣으면 높이가 log n 에 가까워 빠르지만, 정렬된 순서로 넣으면 한 줄로 늘어져(치우친 트리, degenerate tree) 리스트처럼 n 번 걸립니다. 중위 순회(in-order traversal), 곧 왼쪽-나-오른쪽 순서로 읽으면 값이 정렬되어 나와서, 범위로 찾기(범위 질의, range query)와 순서대로 꺼내기를 잘합니다.

그림 읽기: 주황과 「지금」 화살표 = 지금 노드 · 굵은 주황 화살표와 기호(5 < 8) = 비교한 뒤 내려갈 쪽 · 옅은 초록 = 지나온 길 · 초록 = 찾음 · 파랑 = 새 노드 · 파란 점선 = 새 노드가 붙을 빈자리 · 주황 점선 = 지울 노드 · 보라 = 오른쪽 최솟값 · 보라 화살표 = 값이 옮겨 감 · 흐린 점선 = 값이 떠난 노드

값(0 ~ 99 의 정수)을 적고 단추를 누르면 걸음 목록이 만들어지고, 「다음」으로 한 걸음씩 따라갑니다. 트리는 단추를 누를 때 이미 끝 결과로 바뀌어, 다음 단추는 바뀐 트리에서 시작합니다. 처음 트리는 8, 3, 10, 1, 6, 14, 4, 7 을 이 순서로 넣은 것이고 2절의 손 예제와 같습니다. 값은 20개까지 넣습니다.

해 볼 것. ① 5 로 「찾기」: 8, 3, 6, 4 와 비교하고 4 의 오른쪽이 비어 있어 없다고 끝납니다(비교 횟수 4). ② 그대로 「넣기」: 같은 네 번을 비교한 뒤 그 빈자리(4 의 오른쪽)에 5 가 붙습니다. 찾다가 멈춘 곳이 곧 넣을 곳입니다. ③ 「처음 트리」에서 1 을 지우면 리프라 떼기만 합니다(5걸음). 10 을 지우면 자식 14 가 올라옵니다(4걸음). 3 을 지우면 자식이 둘이라 오른쪽 자식 6 에서 왼쪽 끝 4 까지 내려가 4 를 고르고, 4 를 3 의 자리로 옮긴 뒤(보라 화살표) 4 가 떠난 노드를 뗍니다(7걸음). 어느 경우든 아래 줄의 왼쪽-나-오른쪽 순서는 정렬된 채입니다.

1. 규칙: 왼쪽은 모두 작고, 오른쪽은 모두 크다

트리의 노드(node) 하나에는 값 하나와 자식을 가리키는 간선 둘(왼쪽, 오른쪽)이 있습니다. 맨 위 노드를 루트(root), 자식이 없는 노드를 리프(leaf), 어떤 노드와 그 아래 전부를 그 노드의 서브트리(subtree)라고 부르겠습니다. 이진 탐색 트리는 모든 노드가 아래 규칙을 지킵니다.

왼쪽 서브트리의 값  <  나  <  오른쪽 서브트리의 값     (모든 노드에서)

「왼쪽 자식이 나보다 작다」가 아니라 왼쪽 서브트리 전부가 작다는 점이 중요합니다. 그래서 어느 노드에서 오른쪽으로 내려가면, 그 뒤로 만나는 값은 모두 그 노드보다 큽니다. 비교할 때마다 남은 후보의 한쪽을 통째로 버릴 수 있는 까닭입니다. 이진 탐색이 정렬된 배열의 가운데와 비교하며 반씩 버리는 것과 같은 생각을, 배열 대신 간선으로 이은 노드에 담은 것입니다.

성질쉬운 말실험에서
찾기·넣기·지우기는 높이만큼한 번 비교할 때 한 층 내려간다. 걸음 수는 많아야 트리의 층 수다① 의 걸음 수
찾다가 멈춘 곳이 넣을 곳없는 값을 찾으면 빈자리에서 멈추고, 넣기는 그 빈자리에 새 노드를 단다. 다른 노드는 움직이지 않는다① 해 볼 것 ①·②
왼쪽-나-오른쪽으로 읽으면 정렬된 줄규칙이 지켜지는 한 늘 작은 것부터 나온다① 의 아래 줄
모양은 넣는 순서가 정한다같은 값이라도 순서가 다르면 높이가 다르다. 정렬된 순서면 한 줄이 된다② 의 두 단추
가장 작은 값은 왼쪽 끝루트에서 왼쪽으로만 내려가 더 갈 곳이 없는 노드. 가장 큰 값은 오른쪽 끝지우기의 자식 둘 경우

2. 손으로 따라가기

빈 트리에 8, 3, 10, 1, 6, 14, 4, 7 을 이 순서로 넣습니다. 값마다 루트에서 출발해 작으면 왼쪽, 크면 오른쪽으로 가다가 빈자리를 만나면 거기에 답니다.

넣는 값비교하는 길(작으면 왼쪽, 크면 오른쪽)다는 곳(처음 만난 빈자리)
8(빈 트리)루트
33 < 8 → 왼쪽8 의 왼쪽
1010 > 8 → 오른쪽8 의 오른쪽
11 < 8 → 왼쪽, 1 < 3 → 왼쪽3 의 왼쪽
66 < 8 → 왼쪽, 6 > 3 → 오른쪽3 의 오른쪽
1414 > 8 → 오른쪽, 14 > 10 → 오른쪽10 의 오른쪽
44 < 8 → 왼쪽, 4 > 3 → 오른쪽, 4 < 6 → 왼쪽6 의 왼쪽
77 < 8 → 왼쪽, 7 > 3 → 오른쪽, 7 > 6 → 오른쪽6 의 오른쪽

다 넣으면 4층짜리 트리가 됩니다. 1층에 8, 2층에 3 과 10, 3층에 1, 6, 14, 4층에 4 와 7 입니다.

31647 4167 지울 노드 오른쪽 최솟값 떠난 자리 ① ② ③ 전 후
자식이 둘인 3 지우기. ① 오른쪽 자식 6 으로 내려가고 ② 왼쪽으로 끝까지 가면 4 입니다(오른쪽 서브트리의 가장 작은 값). ③ 4 를 3 의 자리로 옮겨 적고, 4 가 떠난 노드(흐린 점선)는 떼어 냅니다.

값마다 찾는 데 비교하는 횟수는 그 값이 있는 층의 번호, 곧 깊이(depth)와 같습니다. 이 트리에서 여덟 값의 평균은 (1×1 + 2×2 + 3×3 + 4×2) ÷ 8 = 22 ÷ 8 = 2.75 번입니다.

3. 중위 순회: 왼쪽-나-오른쪽으로 돌면 정렬된 줄이 나온다

노드마다 「왼쪽 서브트리를 다 읽고 → 나를 읽고 → 오른쪽 서브트리를 다 읽는」 순서로 트리 전체를 돕니다(중위 순회). 규칙에 따라 왼쪽 서브트리는 모두 나보다 작고 오른쪽 서브트리는 모두 크니, 나는 늘 작은 것들 바로 뒤, 큰 것들 바로 앞에 나옵니다. 서브트리 안에서도 같은 일이 되풀이되므로 전체가 작은 것부터 늘어섭니다. 2절의 트리는 1, 3, 4, 6, 7, 8, 10, 14 로 읽힙니다.

이 성질 덕분에 「가장 작은 것」, 「7 바로 다음 값」, 「4 이상 9 이하의 값 모두」 같은 질문을 잘 풉니다. 범위의 시작을 찾는 데 높이만큼, 그다음은 꺼내는 개수만큼 걸립니다. 키가 섞여 저장되는 해시 테이블은 이런 질문에 답하려면 전부 꺼내 정렬해야 합니다.

4. 찾기·넣기·지우기는 트리 높이만큼 걸린다

세 일 모두 루트에서 비교하며 한 층씩 내려가고, 지우기의 자식 둘 경우도 더 아래로 내려갈 뿐입니다. 그래서 걸리는 시간은 트리의 높이(층 수)에 비례합니다. 같은 값 n 개라도 높이는 크게 다를 수 있습니다.

값의 수 n가장 낮게 세우면(층마다 1, 2, 4, … 개)한 줄로 늘어지면(치우친 트리)
154층15층
1,000,00020층(2²⁰ = 1,048,576 이라 20층에 다 들어간다)1,000,000층

가장 낮은 높이는 log₂(n + 1) 을 올린 값입니다. n 이 두 배가 되면 한 층 늘 뿐입니다(O(log n)). 한 줄이면 n 이 두 배일 때 걸음도 두 배입니다(O(n)). 출처는 뒤섞인 순서로 넣은 트리라면 찾는 데 드는 평균 걸음이 log n 에 비례한다고 보입니다. 아래 실험에서 순서만 바꿔 보세요.

값은 1 부터 n 까지(7 ~ 15개)입니다. 「뒤섞어 넣기」는 고정 씨앗 난수기로 섞어 쪽을 열 때마다 같은 순서입니다. 평균 찾는 걸음은 트리에 있는 값을 하나씩 찾을 때 비교하는 횟수의 평균입니다.

해 볼 것. ① 처음(15개, 뒤섞기)은 높이 6층, 평균 찾는 걸음 3.87번입니다. 가장 낮은 4층보다 조금 높습니다(4층으로 꽉 채우면 평균 49 ÷ 15 ≈ 3.27). ② 「작은 것부터 차례로 넣기」를 누르면 모든 값이 바로 앞 값의 오른쪽에 붙어 15층, 평균 8번이 됩니다. 맨 끝 값 15 를 찾으려면 15번 비교합니다. 리스트를 처음부터 훑는 것과 같습니다. ③ 값의 수를 7 로 두면 뒤섞기는 3층(가장 낮은 높이), 평균 2.43번이고 차례로는 7층, 평균 4번입니다. ④ 11 로 두면 뒤섞기도 8층으로 높습니다. 뒤섞으면 보통 낮지만 늘 그렇지는 않습니다.

모양을 운에 맡기지 않으려면 넣고 지울 때마다 노드를 돌려 높이를 log n 쯤으로 지키는 균형 잡힌 트리를 씁니다. 다음 쪽 레드-블랙 트리가 그 방법입니다.

5. 언제 무엇을 쓰나

O(1) 은 n 과 상관없이 몇 번, O(log n) 은 n 이 두 배면 한 번 더, O(n) 은 n 이 두 배면 두 배, O(n log n) 은 그보다 조금 더입니다. n 은 저장한 값의 수, k 는 꺼내는 값의 수입니다.

선택지찾기(좋을 때 · 보통 · 나쁠 때)넣기 · 지우기범위 질의 · 순서대로 꺼내기더 드는 메모리쓰는 경우
이진 탐색 트리(이 쪽)O(1) 루트에 있을 때 · O(log n) 뒤섞인 순서로 넣었을 때 · O(n) 한 줄일 때찾기와 같다잘한다. O(높이 + k)값마다 자식 줄 둘배울 때. 넣는 순서가 뒤섞여 있다고 믿을 수 있을 때
균형 잡힌 트리O(1) · O(log n) · O(log n)O(log n), 나쁠 때도잘한다. O(log n + k)줄 둘에 노드마다 색 표시 하나순서가 필요한 사전을 오래 바꿔 가며 쓸 때
해시 테이블O(1) · O(1) · O(n) 모두 한 칸에 몰릴 때보통 O(1)못한다. 다 꺼내 정렬해야 한다 O(n log n)비워 둔 칸이 있는 표정확한 키로만 찾을 때
정렬된 배열 + 이진 탐색O(1) · O(log n) · O(log n)O(n). 뒤의 값을 한 칸씩 민다잘한다. O(log n + k)없다한 번 만들고 거의 바꾸지 않을 때

6. 진짜 코드

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

def insert(node, key):                  # 넣은 뒤의 루트를 돌려준다
    if node is None:
        return Node(key)
    if key < node.key:
        node.left = insert(node.left, key)
    elif key > node.key:
        node.right = insert(node.right, key)
    return node

def inorder(node):                      # 중위 순회: 왼쪽-나-오른쪽
    return inorder(node.left) + [node.key] + inorder(node.right) if node else []

root = None
for key in [8, 3, 10, 1, 6, 14, 4, 7]:
    root = insert(root, key)
print(inorder(root))                    # [1, 3, 4, 6, 7, 8, 10, 14]

파이썬 표준 라이브러리에는 이 트리가 없습니다. 비슷한 일은 정렬된 리스트와 bisect 로 합니다: bisect.insort(values, 5). 찾기는 O(log n) 이지만 넣기는 뒤의 값을 미느라 O(n) 입니다(위 표의 넷째 줄).

어디에 쓰나

자주 묻는 것

같은 값을 두 번 넣으면 어떻게 되나요?

정하기 나름입니다. 이 쪽의 실험은 같은 값이 오면 아무것도 하지 않습니다. 출처의 구현은 키와 값을 짝으로 두는 사전이라, 같은 키가 오면 노드를 새로 만들지 않고 값만 바꿉니다. 같은 값을 여러 개 두려면 「같으면 오른쪽」처럼 한쪽으로 정하거나, 노드에 개수를 적어 둡니다.

지울 때 왼쪽 서브트리의 가장 큰 값으로 바꿔도 되나요?

됩니다. 왼쪽 서브트리의 가장 큰 값은 지울 노드보다 작은 값 가운데 가장 크므로, 그 자리에 놓아도 왼쪽은 모두 작고 오른쪽은 모두 크다는 규칙이 지켜집니다. 이 쪽과 출처는 오른쪽 서브트리의 가장 작은 값을 씁니다.

왜 실무에서는 이 트리를 그대로 잘 쓰지 않나요?

넣는 순서에 따라 한 줄로 늘어질 수 있기 때문입니다. 차례로 늘어나는 번호처럼 이미 정렬된 순서로 들어오면 찾기가 리스트처럼 n 번 걸립니다. 그래서 넣고 지울 때마다 모양을 다시 맞춰 높이를 log n 쯤으로 지키는 균형 잡힌 트리(레드-블랙 트리 등)를 씁니다.

낱말

여기서 쓴 말책에서 부르는 말
작은 것은 왼쪽, 큰 것은 오른쪽인 트리이진 탐색 트리(binary search tree, BST)
값 하나를 담는 동그라미노드(node)
맨 위 노드 · 자식이 없는 노드루트(root) · 리프(leaf)
어떤 노드와 그 아래 전부서브트리(subtree)
층 수 · 몇 층에 있나높이(height) · 깊이(depth). 책에 따라 층 수가 아니라 간선 수로 세어 1 작게 적기도 한다
비교하기비교(compare)
왼쪽-나-오른쪽 순서로 돌기중위 순회(in-order traversal)
오른쪽 서브트리의 가장 작은 값후계자(successor)
자식 둘인 노드를 후계자로 바꿔 지우기히바드 삭제(Hibbard deletion)
범위로 찾기범위 질의(range search, range query)
한 줄로 늘어진 트리치우친 트리, 퇴화 트리(degenerate tree)
높이를 log n 쯤으로 지키는 트리균형 이진 탐색 트리(balanced BST)

출처

← 해시 테이블레드블랙 트리 →