이진 탐색 트리의 검색과 수정

정렬되지 않은 목록에서 값을 찾으려면 하나씩 모두 비교해야 하지만, 사전처럼 정렬되어 있으면 펼친 쪽보다 앞인지 뒤인지 보고 절반을 건너뛸 수 있습니다. 이진 탐색 트리는 이 생각을 트리에 담은 구조입니다. 정점마다 "작은 것은 왼쪽, 큰 것은 오른쪽"이라는 약속을 지키면, 루트에서 내려가며 한 번 비교할 때마다 한쪽 부분 트리를 통째로 건너뛸 수 있습니다. 이 글에서는 트리와 이진 트리의 구조의 이진 트리에 이 약속을 더한 이진 탐색 트리를 다룹니다.

부분 트리 전체에 걸리는 조건

이진 탐색 트리(binary search tree)는 모든 정점에서 왼쪽 부분 트리의 모든 키가 그 정점의 키보다 작고, 오른쪽 부분 트리의 모든 키가 그 정점의 키보다 큰 이진 트리입니다. 이 글에서는 같은 키를 두 번 저장하지 않습니다. 조건은 바로 아래 자식뿐 아니라 부분 트리의 모든 자손에 걸린다는 점이 중요합니다. 자식과만 비교해서 맞더라도 더 깊은 자손이 조건을 깨면 이진 탐색 트리가 아닙니다.

그래서 조건을 검사할 때는 내려가면서 각 정점의 키가 놓일 수 있는 범위를 함께 넘깁니다. 루트는 범위 제한이 없고, 왼쪽으로 내려가면 지금 키가 새 상한이, 오른쪽으로 내려가면 지금 키가 새 하한이 됩니다.

def is_bst(node, low=float("-inf"), high=float("inf")):
    if node is None:
        return True
    value, left, right = node
    return low < value < high and is_bst(left, low, value) and is_bst(right, value, high)


good = (8, (3, (1, None, None), (6, None, None)), (10, None, None))
bad = (8, (3, None, (9, None, None)), (10, None, None))
print(is_bst(good), is_bst(bad))

True False

정점은 앞 글처럼 (값, 왼쪽, 오른쪽) 튜플이고, float("inf")는 어떤 수보다도 큰 무한대입니다. bad에서 9는 부모 3보다 크므로 3의 오른쪽 자식이라는 점만 보면 맞습니다. 하지만 9는 루트 8의 왼쪽 부분 트리에 있으므로 상한 8을 넘어 조건을 깹니다. 3으로 내려갈 때 범위가 8 미만으로, 다시 9의 자리로 내려갈 때 3 초과 8 미만으로 좁아지기 때문에 is_bst가 이것을 찾아냅니다.

이 조건이 있으면 중위 순회가 키를 언제나 오름차순으로 내놓습니다. 트리의 구조에 대한 귀납법으로 보일 수 있습니다. 왼쪽 부분 트리의 중위 순회는 귀납 가정에 따라 오름차순이고 그 키들은 모두 루트보다 작으며, 오른쪽 부분 트리의 중위 순회도 오름차순이고 키들이 모두 루트보다 큽니다. 그래서 왼쪽 결과, 루트, 오른쪽 결과를 차례로 이으면 전체가 오름차순입니다.

검색, 삽입, 삭제

검색은 루트에서 시작해 찾는 키가 지금 키보다 작으면 왼쪽으로, 크면 오른쪽으로 내려가다가, 같은 키를 만나거나 빈 자리에 닿으면 멈춥니다. 빈 자리에 닿았다면 키가 트리에 없다고 확신할 수 있습니다. 조건에 따라 그 키가 있을 수 있는 곳은 지나온 길뿐이기 때문입니다. 삽입은 같은 길을 따라 내려가 닿은 빈 자리에 새 정점을 놓습니다.

삭제는 지울 정점의 자식 수에 따라 세 경우로 나뉩니다. 잎이면 그냥 지우고, 자식이 하나이면 그 자식을 지운 정점의 자리로 올립니다. 자식이 둘이면 오른쪽 부분 트리에서 가장 작은 키, 곧 중위 순회에서 바로 다음에 오는 키인 후속자(successor)를 지운 자리로 옮기고, 원래 후속자 정점을 지웁니다. 후속자는 오른쪽 부분 트리의 가장 왼쪽에 있어 왼쪽 자식이 없으므로, 후속자를 지우는 일은 앞의 두 경우 가운데 하나가 됩니다. 후속자는 왼쪽 부분 트리의 모든 키보다 크고 오른쪽에 남은 키들보다 작으므로, 그 자리에 놓아도 조건이 지켜집니다.

def insert(node, key):
    if node is None:
        return (key, None, None)
    value, left, right = node
    if key < value:
        return (value, insert(left, key), right)
    if key > value:
        return (value, left, insert(right, key))
    return node


def search_path(node, key):
    path = []
    while node is not None:
        value, left, right = node
        path.append(value)
        if key == value:
            return path, True
        node = left if key < value else right
    return path, False


def delete(node, key):
    if node is None:
        return None
    value, left, right = node
    if key < value:
        return (value, delete(left, key), right)
    if key > value:
        return (value, left, delete(right, key))
    if left is None:
        return right
    if right is None:
        return left
    successor = right
    while successor[1] is not None:
        successor = successor[1]
    return (successor[0], left, delete(right, successor[0]))


def inorder(node):
    if node is None:
        return []
    value, left, right = node
    return inorder(left) + [value] + inorder(right)


def height(node):
    if node is None:
        return -1
    return 1 + max(height(node[1]), height(node[2]))


tree = None
for key in (8, 3, 10, 1, 6):
    tree = insert(tree, key)
print(tree)
print(search_path(tree, 6), search_path(tree, 7))
print(delete(tree, 8), inorder(delete(tree, 8)))
for keys in ((1, 2, 3, 4, 5, 6, 7), (4, 2, 6, 1, 3, 5, 7)):
    chain = None
    for key in keys:
        chain = insert(chain, key)
    print(keys, "높이", height(chain))

(8, (3, (1, None, None), (6, None, None)), (10, None, None))
([8, 3, 6], True) ([8, 3, 6], False)
(10, (3, (1, None, None), (6, None, None)), None) [1, 3, 6, 10]
(1, 2, 3, 4, 5, 6, 7) 높이 6
(4, 2, 6, 1, 3, 5, 7) 높이 2

튜플은 바꿀 수 없으므로 insert와 delete는 원래 트리를 고치지 않고, 바뀐 길 위의 정점만 새로 만든 트리를 돌려줍니다. 8, 3, 10, 1, 6을 차례로 넣으면 트리와 이진 트리의 구조의 예제 트리가 됩니다. 6을 찾을 때는 8보다 작아 왼쪽의 3으로, 3보다 커서 오른쪽의 6으로 내려가 찾고, 7을 찾을 때는 같은 길로 6까지 내려간 뒤 6의 오른쪽 빈 자리에서 멈춥니다. 자식이 둘인 루트 8을 지우면 오른쪽 부분 트리의 가장 작은 키 10이 루트로 올라오고, 중위 순회는 여전히 오름차순입니다. height는 빈 트리의 높이를 −1로 정해, 잎의 높이가 1 + max(−1, −1) = 0이 되도록 했습니다.

높이가 비용을 정한다

검색, 삽입, 삭제는 모두 루트에서 한 길을 따라 내려가므로 비교 횟수가 트리의 높이 h에 비례합니다. 그래서 같은 키들이라도 넣는 순서에 따라 비용이 크게 달라집니다. 1부터 7까지를 크기 순서대로 넣으면 모든 정점이 오른쪽 자식 하나만 가지는 사슬이 되어 높이가 6, 곧 n − 1입니다. 이때 검색은 목록을 하나씩 훑는 것과 다를 바가 없습니다. 4, 2, 6, 1, 3, 5, 7 순서로 넣으면 포화 이진 트리가 되어 높이가 2이고, 어떤 키든 세 번 안에 찾습니다.

트리와 이진 트리의 구조에서 본 것처럼 정점 n개인 이진 트리의 높이는 적어도 $\log_2(n+1)-1$이므로, 이진 탐색 트리가 가장 잘 해도 비교 횟수는 $\log_2 n$ 정도입니다. 키를 무작위 순서로 넣으면 높이가 평균적으로 $\log_2 n$에 비례한다는 것이 알려져 있지만, 이미 정렬된 데이터가 들어오는 일은 실제로 흔합니다. 그래서 일반 이진 탐색 트리의 연산이 언제나 $O(\log n)$이라고 말하면 틀리고, 최악의 경우는 $O(n)$입니다. 삽입과 삭제 때마다 모양을 고쳐 높이를 $O(\log n)$으로 유지하는 AVL 트리나 레드-블랙 트리 같은 균형 이진 탐색 트리가 있지만, 이 교재의 범위를 넘습니다.

더 깊이: 무작위 순서와 균형 트리의 비교 횟수

높이와 달리, 검색 한 번이 평균적으로 하는 비교 횟수에는 간단한 계수가 알려져 있습니다. Sedgewick와 Wayne의 Algorithms 교재 사이트에 따르면, 키를 무작위 순서로 넣어 만든 이진 탐색 트리에서 있는 키를 찾는 검색은 평균적으로 비교를 약 $2\ln n$번, 곧 약 $1.39\log_2 n$번 하고, 없는 키를 찾거나 새 키를 넣을 때도 같습니다. 가장 잘 균형 잡힌 트리의 $\log_2 n$보다 39% 정도 많을 뿐이므로, 무작위 순서라면 균형을 따로 맞추지 않아도 꽤 좋은 셈입니다.

이 계수는 퀵 정렬과 같은 구조에서 나옵니다. 키를 넣는 순서대로 배열에 두고, 맨 앞 원소를 피벗으로 삼아 나머지를 원래 순서 그대로 작은 쪽과 큰 쪽으로 나누는 퀵 정렬을 생각하면, 처음 넣은 키가 루트가 되어 나머지를 작은 쪽과 큰 쪽으로 나누는 것이 피벗으로 배열을 나누는 것과 같습니다. 두 키가 비교되는 것도 한쪽이 다른 쪽의 조상일 때, 곧 한쪽이 다른 쪽을 포함한 구간의 피벗이었을 때뿐이므로, 트리를 만드는 동안의 비교와 퀵 정렬의 비교는 정확히 같습니다. 같은 사이트가 퀵 정렬의 평균 비교 횟수를 약 $2n\ln n$으로 정리하므로, 이를 키 n개로 나누면 키 하나를 찾는 데 드는 평균 $2\ln n$이 나옵니다. 이것은 키 하나를 찾는 평균 비용이고, 가장 깊은 정점까지의 높이는 이보다 커서 Reed가 2003년에 보인 대로 기댓값이 약 $4.311\ln n$, 곧 약 $2.99\log_2 n$에서 $\ln\ln n$에 비례하는 작은 항을 뺀 값입니다.

균형 트리는 이 평균이 아니라 최악의 경우를 보장합니다. 같은 사이트는 키가 n개인 2-3 트리의 검색과 삽입이 많아야 $\log_2 n$개의 정점을 지나고, 그 2-3 트리를 이진 트리로 나타낸 레드-블랙 트리의 높이는 어떤 순서로 넣어도 $2\log_2 n$을 넘지 않는다고 정리합니다. 정렬된 데이터를 넣어도 이 상한은 그대로입니다.

정리

• 이진 탐색 트리는 모든 정점에서 왼쪽 부분 트리의 모든 키가 작고 오른쪽 부분 트리의 모든 키가 큰 이진 트리이며, 조건은 자식뿐 아니라 모든 자손에 걸립니다.
• 조건은 내려가면서 키의 범위를 좁혀 검사하고, 조건이 지켜지면 중위 순회가 오름차순입니다.
• 검색과 삽입은 비교 결과에 따라 한 길을 내려가며, 빈 자리에 닿으면 키가 없다는 것을 확신할 수 있습니다.
• 자식이 둘인 정점을 지울 때는 후속자를 그 자리로 옮기며, 후속자에는 왼쪽 자식이 없어 삭제가 쉬운 경우로 줄어듭니다.
• 연산의 비용은 높이에 비례하고, 넣는 순서에 따라 높이가 $\log_2 n$ 정도에서 n − 1까지 달라집니다.

연습 문제

1. 삽입 위치 찾기

본문의 트리(8, 3, 10, 1, 6을 넣은 트리)에 5를 넣으면 어디에 들어가고, 중위 순회는 어떻게 되나요?

2. 놓일 수 있는 키의 범위

본문의 트리에서 10의 왼쪽 자식 자리에 새 키를 놓으려면 그 키는 어떤 범위에 있어야 하나요?

3. 선행자로 지우기

본문의 트리에서 루트 8을 지울 때 후속자 대신 왼쪽 부분 트리의 가장 큰 키인 선행자(predecessor)를 쓰면 트리는 어떻게 되나요?

이진 탐색 트리를 손으로 추적할 때는 내려가는 정점마다 키가 놓일 수 있는 상한과 하한을 옆에 적어 보세요. 다음 글 신장 트리와 Prim·Kruskal에서는 그래프의 모든 정점을 가장 적은 비용으로 잇는 트리를 찾습니다.