이진 탐색 트리 - 정렬된 채로 넣고 찾기

이 장에서 배우는 것

앞 장에서 정렬은 여러 값을 일정한 순서로 다시 배치하는 작업이었다. 그런데 정렬한 뒤에도 값이 계속 들어오고 빠져나간다면 어떨까. 새 값을 받을 때마다 전체를 다시 정렬하는 대신, 값을 넣는 위치에 규칙을 둘 수 있다. 이 장에서는 작은 값은 왼쪽으로, 큰 값은 오른쪽으로 연결하는 구조를 직접 만든다.

이 구조를 전공 수업에서는 이진 탐색 트리(binary search tree)라고 부르며, 코드에서는 줄여서 BST라고 쓴다. 여기서 ‘정렬된 채’라는 말은 메모리에 값이 한 줄로 정렬되어 있다는 뜻이 아니다. 연결 관계에 순서 규칙이 있어서, 정해진 순서로 방문하면 정렬 결과가 나온다는 뜻이다. 《논리로 푸는 알고리즘》이 자료구조를 활용하는 쪽이라면, 여기서는 그 연결과 변경을 직접 책임지는 쪽을 살펴본다.

노드와 자식 연결을 이용해 삽입과 탐색을 구현한다.
자식이 없는 경우, 하나인 경우, 둘인 경우를 나누어 삭제한다.
중위 순회로 값을 오름차순으로 읽고 방문 횟수를 센다.
같은 값도 입력 순서에 따라 높이와 탐색 비용이 달라짐을 확인한다.
완성한 트리와 내장 리스트의 순차 탐색 결과 및 검사 횟수를 비교한다.

문제 상황

작업 요청을 정수 번호로 관리하는 작은 프로그램을 만든다고 하자. 요청은 수시로 추가되며, 처리한 번호는 지운다. 특정 번호가 남아 있는지도 자주 확인한다. 화면에는 현재 번호를 작은 순서대로 보여 주어야 한다. 번호가 중복으로 들어오면 기존 요청을 유지하고 새 요청은 추가하지 않는다고 정한다.

배열의 앞에서부터 번호를 찾으면 구현은 간단하지만, 끝에 있는 번호를 찾을 때 앞의 값까지 모두 검사한다. 항상 정렬된 배열을 유지하면 탐색 경로를 줄일 수 있으나, 가운데에 삽입하거나 삭제할 때 뒤쪽 값을 옮겨야 한다. 이번 구현은 값 이동 대신 노드 사이의 연결을 바꾼다.

다만 트리를 만든다고 언제나 탐색이 빨라지는 것은 아니다. 번호가 1, 2, 3처럼 증가하는 순서로 들어오면 오른쪽 연결만 길어질 수 있다. 그러므로 구현이 끝났는지만 보지 않고, 같은 번호 집합을 두 순서로 넣어 높이와 검사 횟수까지 비교한다. 이 비교가 자료구조의 모양과 실행 비용 사이를 연결해 준다.

작은 값은 왼쪽, 큰 값은 오른쪽

값 하나와 연결 정보를 묶은 객체를 전공 수업에서는 노드(node)라고 부른다. 가장 위에서 출발점이 되는 노드는 루트(root)다. 어떤 노드에서 바로 아래로 연결한 노드는 자식이며, 그 자식 입장에서 위쪽 노드는 부모다. 자식이 없는 노드는 잎이라고 부른다. 여기서는 각 노드가 왼쪽과 오른쪽에 자식을 하나씩만 둘 수 있다. 그래서 이름에 ‘이진’이 붙는다.

어떤 노드와 그 아래에 연결된 전체 부분을 서브트리(subtree)라고 부른다. 탐색 트리의 규칙은 바로 옆 자식 두 개에만 적용되지 않는다. 왼쪽 서브트리의 모든 값은 현재 값보다 작고, 오른쪽 서브트리의 모든 값은 현재 값보다 커야 한다. 이 규칙이 연결을 바꾼 뒤에도 유지되어야 한다.

그림에서 3은 2보다 크므로 2의 오른쪽에 있다. 동시에 4의 왼쪽 전체에 속하므로 4보다 작아야 한다. 루트의 왼쪽 자식만 확인해서는 전체 규칙을 검사할 수 없다는 뜻이다. 코드에 입력하는 4, 2, 6, 1, 3, 5, 7은 이 연결을 그대로 만든다.

탐색은 루트에서 시작한다. 찾는 값이 현재 값과 같으면 끝난다. 더 작으면 왼쪽으로, 더 크면 오른쪽으로 간다. 빈 연결에 도달하면 값이 없다. 삽입도 같은 경로를 따라가되, 처음 만나는 빈 연결에 새 노드를 붙인다. 같은 값을 만나면 아무것도 추가하지 않고 실패를 나타내는 False를 돌려준다.

Python 객체를 변수에 담으면 그 객체를 가리키는 참조를 보관한다. 이 구현의 left와 right도 노드 객체에 대한 참조다. 비어 있는 연결은 None으로 표시한다. 노드를 배열 칸에 억지로 넣을 필요가 없으므로, 트리 자체는 내장 리스트나 딕셔너리를 저장소로 쓰지 않는다.

연결을 따라 이동한 횟수와 값 비교 횟수를 혼동하지 않도록 측정 기준도 정한다. 이 장에서는 반복문이 실제 노드 하나를 꺼내 검사할 때마다 visits를 1 늘린다. 이를 노드 검사 횟수라고 부른다. 한 번의 검사 안에서 동등 비교와 대소 비교를 함께 할 수 있으므로, visits는 Python 비교 연산자의 실행 횟수와 같지는 않다. 두 비교의 수는 노드당 일정한 상한이 있어서 시간 복잡도를 확인하는 데 이 계수를 쓸 수 있다.

삭제는 연결을 이어 주는 작업이다

삭제는 먼저 지울 값을 탐색한다. 이때 현재 노드뿐 아니라 그 부모도 기억한다. 삭제 뒤에는 부모가 다른 노드를 가리켜야 할 수 있기 때문이다. 루트를 지울 때는 부모가 없으므로 self.root 자체를 바꾼다.

삭제할 노드의 자식 수에 따라 바꿀 연결
자식 수	처리	규칙이 유지되는 이유
0개	부모의 연결을 None으로 바꾼다	남은 값의 위치가 변하지 않는다
1개	부모를 유일한 자식에 연결한다	자식 아래의 값도 기존 범위 안에 있다
2개	오른쪽 최솟값으로 값을 바꾼 뒤 그 원래 노드를 제거한다	왼쪽 전체보다 크고 나머지 오른쪽 값보다 작다

자식이 둘이면 어느 한쪽을 그대로 올려 붙이는 것만으로는 나머지 연결을 처리할 수 없다. 대신 오른쪽 서브트리에서 가장 작은 값을 찾는다. 오른쪽으로 한 번 간 뒤 왼쪽 연결이 끝날 때까지 이동하면 된다. 정렬 순서에서 현재 값 바로 다음에 오는 값이므로, 전공 수업에서는 이를 중위 후계자(inorder successor)라고 부른다.

루트 4를 지운다면 후계자는 5다. 4가 있던 노드의 값을 5로 바꾸고, 원래 5가 있던 노드를 제거한다. 후계자는 왼쪽 자식이 없다. 왼쪽 자식이 있다면 그쪽에 더 작은 값이 있어서 후계자 선택과 모순되기 때문이다. 다만 오른쪽 자식은 있을 수 있으므로 그 연결은 보존해야 한다.

완성 코드에서는 후계자를 찾은 다음 parent와 current가 후계자의 부모와 후계자를 가리키게 한다. 그러면 나머지 처리를 자식이 최대 하나인 삭제와 합칠 수 있다. 값만 바꾸고 원래 후계자 노드를 남기면 같은 값이 두 번 나타나므로, 마지막 연결 변경까지 해야 삭제가 끝난다.

이 구현은 정수 값만 보관한다. 노드에 번호와 본문 같은 여러 정보가 함께 있다면, 후계자에서 복사할 정보의 범위도 따로 정해야 한다. 또한 삭제 중에 노드의 값이 바뀌므로 외부에 노드 객체를 공개하지 않는다. 사용자는 값의 존재 여부와 순회 결과만 받는다.

순회와 높이로 구조를 확인한다

모든 노드를 정해진 순서로 방문하는 일을 순회(traversal)라고 부른다. 왼쪽 전체를 먼저 방문하고, 현재 값을 읽고, 오른쪽 전체를 방문하는 순서는 중위 순회(inorder traversal)다. 왼쪽에는 작은 값만 있고 오른쪽에는 큰 값만 있으므로, 이 순서로 읽으면 오름차순이 된다. 정렬 함수를 호출해서 결과를 만드는 것이 아니다.

왼쪽으로 내려갔다가 되돌아오려면 아직 읽지 않은 노드를 기억해야 한다. 여기서는 나중에 넣은 것을 먼저 꺼내는 스택을 고정 크기 배열로 만든다. 파이썬 리스트는 [None] * 크기로 한 번 만들고, append나 pop 대신 다음 빈 칸의 위치를 나타내는 top으로 읽고 쓴다. 노드 수만큼 확보하면 어느 경로에서도 부족하지 않다.

높이(height)는 루트에서 가장 먼 잎까지 지나가는 연결의 수로 정의한다. 노드 하나인 트리의 높이는 0이고, 빈 트리의 높이는 -1로 정한다. 높이를 노드 수로 세는 정의도 있으므로, 수치를 비교하기 전에 기준을 확인해야 한다. 높이 계산에는 노드 배열과 깊이 배열을 나란히 두며 각 노드의 깊이를 함께 저장한다.

높이가 h이면 루트에서 출발하는 삽입과 탐색은 많아야 h + 1개 정도의 기존 노드를 검사한다. 삭제도 탐색 경로와 후계자 경로를 따라가므로 O(h + 1)이다. O는 입력 크기에 따라 비용이 얼마나 커지는지를 나타내는 표기다. 노드 수 n이 커질 때 높이가 로그 규모로 유지되면 O(log n), 한쪽으로 이어져 높이가 n - 1이 되면 O(n)으로 표현한다.

로그 규모라는 말은 후보가 반복해서 대략 절반으로 줄어드는 경우를 가리킨다. 하지만 이 구현에는 그런 모양을 보장하는 장치가 없다. 그림의 모양과 정렬 입력의 모양을 실제 계수로 비교해야 한다. 빈 트리를 처음 만들 때의 상수 비용까지 표현하려면 O(h + 1)이 더 정확하고, 비어 있지 않은 큰 트리의 성질을 설명할 때는 흔히 O(h)라고 줄여 쓴다.

완성 코드

다음 전체를 main.py로 저장한다. 입력 순서는 길이가 고정된 튜플로 준비한다. 작업용 배열은 고정 크기 리스트로만 사용하고, 내장 리스트를 일반 컨테이너로 만드는 부분은 마지막 비교에 둔다. 난수와 외부 패키지를 사용하지 않으므로 실행할 때마다 출력이 같다.

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


class BST:
    def __init__(self):
        self.root = None
        self.size = 0

    def insert(self, key):
        if self.root is None:
            self.root = Node(key)
            self.size = 1
            return True, 0

        current = self.root
        visits = 0
        while True:
            visits += 1
            if key == current.key:
                return False, visits
            if key < current.key:
                if current.left is None:
                    current.left = Node(key)
                    break
                current = current.left
            else:
                if current.right is None:
                    current.right = Node(key)
                    break
                current = current.right
        self.size += 1
        return True, visits

    def contains(self, key):
        current = self.root
        visits = 0
        while current is not None:
            visits += 1
            if key == current.key:
                return True, visits
            if key < current.key:
                current = current.left
            else:
                current = current.right
        return False, visits

    def delete(self, key):
        parent = None
        current = self.root
        visits = 0

        while current is not None:
            visits += 1
            if key == current.key:
                break
            parent = current
            if key < current.key:
                current = current.left
            else:
                current = current.right

        if current is None:
            return False, visits

        if current.left is not None and current.right is not None:
            successor_parent = current
            successor = current.right
            while True:
                visits += 1
                if successor.left is None:
                    break
                successor_parent = successor
                successor = successor.left
            current.key = successor.key
            parent = successor_parent
            current = successor

        if current.left is not None:
            child = current.left
        else:
            child = current.right

        if parent is None:
            self.root = child
        elif parent.left is current:
            parent.left = child
        else:
            parent.right = child

        self.size -= 1
        return True, visits

    def inorder(self):
        stack = [None] * self.size
        result = [None] * self.size
        top = 0
        used = 0
        current = self.root

        while current is not None or top > 0:
            while current is not None:
                stack[top] = current
                top += 1
                current = current.left
            top -= 1
            current = stack[top]
            stack[top] = None
            result[used] = current.key
            used += 1
            current = current.right
        return result, used

    def height(self):
        if self.root is None:
            return -1, 0

        nodes = [None] * self.size
        depths = [0] * self.size
        nodes[0] = self.root
        top = 1
        maximum = 0
        visits = 0

        while top > 0:
            top -= 1
            node = nodes[top]
            depth = depths[top]
            nodes[top] = None
            visits += 1
            if depth > maximum:
                maximum = depth
            if node.right is not None:
                nodes[top] = node.right
                depths[top] = depth + 1
                top += 1
            if node.left is not None:
                nodes[top] = node.left
                depths[top] = depth + 1
                top += 1
        return maximum, visits


def build(order):
    tree = BST()
    visits = 0
    for key in order:
        inserted, count = tree.insert(key)
        assert inserted
        visits += count
    return tree, visits


def show(label, tree):
    values, visits = tree.inorder()
    print(label, values, "순회 검사", visits)


def builtin_find(values, key):
    checks = 0
    for value in values:
        checks += 1
        if value == key:
            return True, checks
    return False, checks


def main():
    balanced_order = (4, 2, 6, 1, 3, 5, 7)
    ascending_order = (1, 2, 3, 4, 5, 6, 7)
    balanced, balanced_cost = build(balanced_order)
    ascending, ascending_cost = build(ascending_order)

    for name, tree, cost in (
        ("가운데부터", balanced, balanced_cost),
        ("오름차순", ascending, ascending_cost),
    ):
        height, visits = tree.height()
        print(name, "삽입 검사 합계", cost,
              "높이", height, "높이 검사", visits)
        show("중위", tree)
        for key in (7, 8):
            found, count = tree.contains(key)
            print("탐색", key, found, "검사", count)

    inserted, count = balanced.insert(4)
    print("중복 삽입", inserted, "검사", count,
          "크기", balanced.size)

    for key in (4, 1, 6):
        removed, count = balanced.delete(key)
        print("삭제", key, removed, "검사", count)
        show("남은 값", balanced)

    removed, count = balanced.delete(8)
    print("없는 값 삭제", removed, "검사", count,
          "크기", balanced.size)

    edge = BST()
    assert edge.height() == (-1, 0)
    assert edge.contains(1) == (False, 0)
    assert edge.delete(1) == (False, 0)
    edge.insert(2)
    edge.insert(1)
    assert edge.delete(2) == (True, 1)
    assert edge.root.key == 1
    assert edge.delete(1) == (True, 1)
    assert edge.root is None and edge.size == 0

    special, _ = build((4, 2, 6, 7))
    assert special.delete(4) == (True, 2)
    values, _ = special.inorder()
    assert tuple(values) == (2, 6, 7)

    linked, _ = build((4, 2, 8, 6, 7))
    assert linked.delete(4) == (True, 3)
    values, _ = linked.inorder()
    assert tuple(values) == (2, 6, 7, 8)
    print("경계 사례 확인 완료")

    print("내장 list 순차 탐색과 비교")
    reference_tree, _ = build(balanced_order)
    reference_list = list(balanced_order)
    for key in (7, 8):
        tree_found, tree_count = reference_tree.contains(key)
        list_found, list_count = builtin_find(reference_list, key)
        assert tree_found == list_found
        print("값", key, "결과", tree_found,
              "BST 검사", tree_count, "list 검사", list_count)


if __name__ == "__main__":
    main()

줄별 해설

Node.__init__의 세 대입문은 값과 두 연결을 만든다. 이어지는 BST.__init__은 시작 연결과 전체 노드 수를 준비한다. size는 중복을 제외한 실제 노드 수다. 작업용 배열의 크기도 이 값을 사용하므로 삽입과 삭제에서 정확하게 갱신해야 한다.

insert의 첫 조건은 빈 트리 전용 처리다. 루트가 없으므로 기존 노드 검사 횟수는 0이다. 그 아래 반복문은 기존 노드를 하나 검사할 때마다 visits를 늘린다. 중복이면 바로 돌아가고, 빈 자식을 찾으면 새 노드를 연결하고 break로 반복을 끝낸다. 따라서 size를 늘리는 마지막 줄은 새 노드가 생긴 경우에만 실행된다.

contains는 삽입에서 연결을 만드는 부분을 뺀 형태다. None에 도달했다는 것은 규칙에 따라 갈 수 있는 경로를 다 확인했다는 뜻이다. 없는 값을 찾는다고 다른 가지를 다시 탐색할 필요는 없다. 프로그램에서는 7의 성공과 8의 실패를 모두 출력해 같은 경로 길이의 성공과 실패를 확인한다.

delete의 첫 반복문에서 parent를 갱신하는 위치를 살펴보자. 현재 값이 목표라면 break하므로 parent는 그 위 노드에 그대로 남는다. 목표가 아니면 현재 노드를 부모로 기억한 뒤 자식으로 내려간다. 탐색이 실패한 경우에는 연결과 size를 건드리지 않는다.

자식 둘을 검사하는 조건 다음에는 후계자 탐색이 나온다. successor_parent는 후계자의 직전 노드를 따라간다. successor의 왼쪽이 비었는지 검사하는 순간도 노드 검사이므로 계수에 포함한다. 값을 복사한 뒤 current를 후계자로 바꾸면, 이후 코드는 실제로 제거할 노드를 대상으로 작동한다.

child는 제거할 노드의 남은 연결이다. 두 자식이 모두 없으면 오른쪽 값인 None이 들어가고, 하나만 있으면 그 자식이 들어간다. parent.left is current의 is는 두 변수가 같은 객체를 가리키는지 묻는다. 값의 크기를 다시 판단하는 대신 실제 연결을 확인한다. 마지막에 size를 한 번만 줄이는 것도 이 처리의 일부다.

inorder에서 top은 스택에 들어 있는 노드 수이자 다음 빈 칸의 위치다. 왼쪽으로 내려갈 때는 노드를 저장하고 top을 늘린다. 더 내려갈 수 없으면 top을 먼저 줄이고 저장한 노드를 꺼낸다. 그 값을 result에 쓴 뒤 오른쪽으로 이동한다. used는 결과를 쓴 횟수이므로 전체 노드 방문 횟수와 같다.

height는 꺼낸 노드의 깊이로 최댓값을 갱신한다. 오른쪽과 왼쪽 자식을 저장할 때 각각 부모 깊이에 1을 더한다. 두 배열의 같은 위치는 한 쌍이다. 노드만 저장하거나 깊이만 저장하면 이 대응이 깨진다. 모든 노드를 한 번씩 꺼내므로 반환하는 visits는 size와 같다.

build는 각 삽입의 검사 횟수를 누적한다. assert는 조건이 참인지 확인하며, 거짓이면 실행을 멈추는 검증문이다. 마지막의 경계 사례는 빈 트리, 루트의 한 자식, 마지막 노드, 오른쪽 자식 자체가 후계자인 경우, 후계자에게 오른쪽 자식이 있는 경우를 실행한다. 출력용 예제만으로 놓치기 쉬운 연결을 확인하는 부분이다.

builtin_find는 내장 리스트의 값을 앞에서부터 비교한다. 리스트 내부 코드를 측정했다고 주장하는 함수가 아니라, 리스트를 대상으로 직접 쓴 순차 탐색이다. 마지막 비교에서는 삭제 전 상태를 새로 만들어 같은 집합과 같은 질의를 사용한다. 리스트에는 순서 있는 연결 정보가 없으므로 검사한 원소 수를 세어 트리의 노드 검사 수와 나란히 표시한다.

실행 결과

파일이 있는 디렉터리에서 다음 명령을 실행한다. assert 검증이 통과하면 아래 출력까지 진행하고 끝난다.

python3 main.py

가운데부터 삽입 검사 합계 10 높이 2 높이 검사 7
중위 [1, 2, 3, 4, 5, 6, 7] 순회 검사 7
탐색 7 True 검사 3
탐색 8 False 검사 3
오름차순 삽입 검사 합계 21 높이 6 높이 검사 7
중위 [1, 2, 3, 4, 5, 6, 7] 순회 검사 7
탐색 7 True 검사 7
탐색 8 False 검사 7
중복 삽입 False 검사 1 크기 7
삭제 4 True 검사 3
남은 값 [1, 2, 3, 5, 6, 7] 순회 검사 6
삭제 1 True 검사 3
남은 값 [2, 3, 5, 6, 7] 순회 검사 5
삭제 6 True 검사 2
남은 값 [2, 3, 5, 7] 순회 검사 4
없는 값 삭제 False 검사 3 크기 4
경계 사례 확인 완료
내장 list 순차 탐색과 비교
값 7 결과 True BST 검사 3 list 검사 7
값 8 결과 False BST 검사 3 list 검사 7

가운데부터 넣는 순서의 삽입 검사는 0 + 1 + 1 + 2 + 2 + 2 + 2로 10이다. 오름차순 입력은 0 + 1 + 2 + 3 + 4 + 5 + 6으로 21이다. 일반적으로 오름차순 n개를 넣을 때 합계는 n × (n - 1) / 2다. 개별 삽입의 최악 비용은 O(n)이지만, 그 삽입을 반복해 전체 트리를 만드는 비용은 O(n²)이 될 수 있다.

루트 4의 삭제에서는 4를 한 번, 후계자 경로의 6과 5를 각각 한 번 검사해 3이 나온다. 그 뒤 잎 1을 지울 때는 5, 2, 1을 검사한다. 이어서 6을 지울 때는 5와 6을 검사하고 자식 7을 올린다. 이 순서로 자식 둘, 없음, 하나의 삭제가 모두 실행된다.

순회 검사 횟수는 항상 남은 노드 수와 같다. 한쪽으로 치우쳐도 모든 값을 출력하려면 모든 노드를 읽어야 한다. 높이 계산도 같은 이유로 O(n)이다. 다만 계수는 핵심 방문만 센다. 이 구현에서 배열을 처음 확보하는 비용까지 포함해도 순회와 높이 계산은 O(n)이고, 사용한 추가 공간 역시 O(n)이다.

마지막 비교에서 두 탐색의 참·거짓 결과는 같지만 검사 수는 다르다. 이것이 실제 실행 시간의 배율을 뜻하지는 않는다. Python 반복문과 객체 접근의 비용까지 같지는 않기 때문이다. 여기서 확인한 것은 알고리즘이 검사한 항목 수다. 내장 리스트는 일반적인 순서 보관 용도이며, 표준 라이브러리에 이 코드와 같은 범용 BST 컨테이너가 들어 있다고 가정하지 않는다.

실무에서 자주 틀리는 것

같은 값을 계속 오른쪽에 넣는다

중복 허용 여부를 정하지 않고 작으면 왼쪽, 나머지는 오른쪽으로 보내면 같은 값도 추가된다. 이 장의 계약은 중복을 저장하지 않는 것이므로 동등 비교가 먼저 필요하다. 다음은 삽입 반복문 안에서의 차이다.

# 틀린 코드: 같은 값도 오른쪽 경로로 보낸다.
if key < current.key:
    current = current.left
else:
    current = current.right

# 고친 코드: 연결을 따라가기 전에 중복을 끝낸다.
if key == current.key:
    return False, visits
if key < current.key:
    current = current.left
else:
    current = current.right

중복을 수량으로 저장하고 싶다면 노드에 별도 개수를 두고 삭제 계약도 바꿔야 한다. 한 메서드만 바꾸면 size와 순회 결과의 의미가 서로 달라질 수 있다.

후계자를 지우면서 오른쪽 자식을 버린다

후계자는 왼쪽 자식이 없지만 오른쪽 자식까지 없다는 뜻은 아니다. 부모의 연결을 무조건 None으로 만들면 그 아래 값이 검색에서 사라진다.

# 틀린 코드: 후계자의 오른쪽 연결을 잃는다.
successor_parent.left = None

# 고친 코드: 후계자가 붙어 있던 실제 방향을 확인한다.
if successor_parent.left is successor:
    successor_parent.left = successor.right
else:
    successor_parent.right = successor.right

후계자가 삭제 대상의 바로 오른쪽 자식이면 두 번째 가지가 필요하다. 완성 코드는 current와 parent를 바꿔 같은 효과를 일반 삭제 처리에서 얻는다. linked 검증은 후계자 6의 오른쪽 값 7이 남는지 확인한다.

루트에도 부모가 있다고 가정한다

부모가 없는 루트를 지울 때 parent.left에 접근하면 오류가 난다. 객체가 아니라 지역 변수 current만 바꾸어도 트리의 시작점은 바뀌지 않는다.

# 틀린 코드: 지역 변수만 바뀐다.
if parent is None:
    current = child

# 고친 코드: 트리가 보관하는 시작 연결을 바꾼다.
if parent is None:
    self.root = child

마지막 노드를 지우는 것도 같은 분기로 처리한다. 이때 child가 None이어서 빈 트리로 돌아간다. 완성 코드의 edge 검증이 이 상태와 size를 함께 확인한다.

치우친 트리에서 재귀 깊이를 잊는다

함수가 자신을 다시 호출하는 방식을 재귀(recursion)라고 부른다. 순회를 짧게 쓸 수 있지만 한쪽으로 긴 트리에서는 호출도 길게 쌓인다. 호출 깊이 제한에 도달할 수 있으므로 이번 구현은 배열 스택을 사용한다. 다음의 첫 코드는 순회 순서 자체는 맞지만, 길게 치우친 입력도 처리한다는 조건에서는 문제가 된다.

# 문제가 되는 코드: 높이만큼 함수 호출이 쌓인다.
def walk(node):
    if node is None:
        return
    walk(node.left)
    print(node.key)
    walk(node.right)

# 고친 코드: 명시적인 고정 크기 작업 배열을 사용한다.
def walk(tree):
    stack = [None] * tree.size
    top = 0
    current = tree.root
    while current is not None or top > 0:
        while current is not None:
            stack[top] = current
            top += 1
            current = current.left
        top -= 1
        current = stack[top]
        print(current.key)
        current = current.right

호출 제한을 피했다고 높이 문제가 해결되는 것은 아니다. 오름차순 입력의 탐색은 여전히 최대 n개 노드를 검사한다. 다음 장에서는 삽입 뒤 연결을 조정해 높이를 관리하는 방법을 다룬다.

한눈에 보기

노드 수 n과 높이 h에 따른 연산 비용
연산	시간 복잡도	계수로 확인한 사실	추가 공간
삽입	O(h + 1)	입력 7개의 누적 검사 10 또는 21	새 노드 O(1)
탐색	O(h + 1)	같은 값 7에 검사 3 또는 7	O(1)
삭제	O(h + 1)	4, 1, 6 삭제에 각각 3, 3, 2	O(1)
중위 순회	O(n)	각 노드를 한 번 결과에 쓴다	결과 포함 O(n)
높이 계산	O(n)	두 트리 모두 검사 7	O(n)
리스트 순차 탐색	O(n)	예제의 성공과 실패 모두 검사 7	O(1)

트리 자체가 차지하는 공간은 노드마다 값과 연결 두 개를 보관하므로 O(n)이다. 삽입과 삭제는 순서를 유지하지만 균형까지 유지하지는 않는다. 순회 결과가 정렬되어 있다는 사실과 탐색 경로가 짧다는 사실은 따로 확인해야 한다.

연습 문제

7, 6, 5, 4, 3, 2, 1을 차례로 넣는다. 삽입 검사 합계, 높이, 값 1의 탐색 검사 횟수를 예측한 뒤 코드로 확인하라.
빈 트리에서는 None을, 그 밖에는 최솟값을 반환하는 minimum 메서드를 추가하라. 반환값에는 노드 검사 횟수도 포함하라. 오른쪽 연결을 볼 필요가 없는 이유를 설명하라.
4, 2, 8, 6, 7로 만든 트리에서 4를 삭제하라. 후계자와 그 오른쪽 자식의 연결을 설명하고, 중위 순회 결과와 size를 검증하라.
빈 트리에서 시작해 2, 1, 3을 넣고 2, 1, 3 순서로 모두 삭제하라. 각 삭제 직후의 중위 순회와 마지막 높이 및 노드 수를 검증하라.

정답과 해설

왼쪽으로만 연결되므로 삽입 검사 합계는 21, 높이는 6, 값 1의 탐색 검사는 7이다. 오름차순 예제와 방향만 다르고 경로 길이는 같다. main 안에 다음을 넣어 확인한다.
```
tree, cost = build((7, 6, 5, 4, 3, 2, 1))
assert cost == 21
assert tree.height() == (6, 7)
assert tree.contains(1) == (True, 7)
```
BST 클래스 안에 다음 메서드를 넣는다. 가장 왼쪽 노드는 자신보다 작은 값을 아래에 갖지 않는다. 어떤 오른쪽 서브트리의 값도 그 서브트리가 갈라진 노드보다 크므로 최솟값 후보가 될 필요가 없다. 검사 횟수는 높이와 관련되며, 빈 트리에서는 0이다.
```
def minimum(self):
    current = self.root
    visits = 0
    while current is not None:
        visits += 1
        if current.left is None:
            return current.key, visits
        current = current.left
    return None, visits
```
메서드를 추가한 뒤 main 안에서 다음을 실행한다.
```
tree, _ = build((4, 2, 6, 1, 3, 5, 7))
assert tree.minimum() == (1, 3)
assert BST().minimum() == (None, 0)
```
후계자는 6이다. 루트 값을 6으로 바꾸고, 원래 6의 부모인 8의 왼쪽을 7에 연결한다. 7은 새 루트 6보다 크고 8보다 작으므로 규칙을 만족한다. 루트 탐색 1회와 후계자 경로 8, 6의 검사 2회를 합쳐 3회다.
```
tree, _ = build((4, 2, 8, 6, 7))
assert tree.delete(4) == (True, 3)
values, visits = tree.inorder()
assert tuple(values) == (2, 6, 7, 8)
assert tree.size == 4 and visits == 4
assert tree.root.right.left.key == 7
```

2를 지우면 후계자 3이 루트 값이 되고, 1을 지우면 루트 하나만 남는다. 마지막 3을 지우면 root가 None으로 바뀐다. 빈 트리의 순회에서는 배열 칸에 접근하지 않으며, 높이는 약속한 -1이다.

tree, _ = build((2, 1, 3))
for key, expected in (
    (2, (1, 3)),
    (1, (3,)),
    (3, ()),
):
    removed, _ = tree.delete(key)
    assert removed
    values, visits = tree.inorder()
    assert tuple(values) == expected
    assert visits == len(expected)
assert tree.size == 0
assert tree.root is None
assert tree.height() == (-1, 0)