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

정렬되지 않은 목록에서는 원하는 키를 하나씩 찾지만, 검색 방향을 결정할 기준이 있으면 일부를 건너뛸 수 있습니다. 이진트리의 구조에 순서를 추가한 BST를 익힙니다.

모든 후손에 적용되는 불변식

이 절에서는 중복 키를 저장하지 않습니다. 각 정점의 왼쪽 하위트리 모든 키는 현재 키보다 작고, 오른쪽 하위트리 모든 키는 큽니다. 바로 아래 자식 두 개만 비교해 맞아도 더 깊은 후손이 조건을 깨면 BST가 아닙니다.

8,3,10,1,6을 순서대로 삽입하면 8이 루트이고, 3은 왼쪽, 10은 오른쪽, 1은 3의 왼쪽, 6은 3의 오른쪽에 들어갑니다. 6 검색은 8보다 작아서 3으로, 3보다 커서 6으로 갑니다. 7 검색은 8→3→6의 오른쪽 빈 자식에서 실패합니다. 빈 자리까지 도달했다는 것은 순서 조건상 다른 가지에 7이 있을 수 없다는 뜻입니다.

중위순회는 키를 오름차순으로 출력합니다. 왼쪽의 작은 키들을 먼저, 현재 키를 다음, 오른쪽의 큰 키들을 나중에 읽기 때문입니다. 일반 이진트리에는 이 성질이 없습니다.

삭제의 세 경우

잎 1을 지우면 부모의 연결을 비웁니다. 자식이 하나인 정점을 지우면 부모가 그 자식을 직접 가리키게 합니다. 자식 둘인 8을 지우면 오른쪽 하위트리의 최솟값인 중위 후속자 10을 대신 놓고, 원래 10 정점을 제거합니다. 오른쪽 최솟값을 가진 정점에는 왼쪽 자식이 없어 그 위치의 삭제는 잎이거나 자식이 하나인 경우로 줄어듭니다. 왼쪽 하위트리의 최댓값인 선행자를 써도 되지만 한 방법을 일관되게 적용합니다.

def contains(node, key):
    # 정점은 (값, 왼쪽, 오른쪽), 빈 자식은 None
    while node is not None:
        value, left, right = node
        if key == value:
            return True
        node = left if key < value else right
    return False

tree = (8, (3, (1,None,None), (6,None,None)), (10,None,None))
print(contains(tree,6), contains(tree,7))  # True False

균형이 없으면 높이가 커진다

검색·삽입·삭제는 높이 h에 비례합니다. 균형이 유지되는 경우 h가 로그 크기지만, 1,2,3,4,…를 차례로 넣으면 한쪽 사슬이 되어 h=n−1입니다. 일반 BST가 항상 O(log n)이라는 주장은 틀립니다. AVL·적흑트리 등 균형을 유지하는 구조는 알고리즘 교재의 확장 주제입니다.

스스로 풀어보기

문제 1. 위 BST에 5를 삽입할 위치를 찾으세요.

풀이: 5<8이므로 왼쪽 3, 5>3이므로 오른쪽 6, 5<6이므로 6의 왼쪽 빈 자식에 넣습니다. 중위순서는 1,3,5,6,8,10입니다. 임의의 빈 자리에 넣으면 불변식을 깨뜨립니다.

문제 2. 루트 8, 왼쪽 자식 3, 3의 오른쪽 자식 9인 트리는 BST인가요?

풀이: 아닙니다. 9>3이라 부모와의 비교는 맞지만 9가 8의 왼쪽 하위트리에 있으면서 8보다 큽니다. 조건은 바로 아래 자식뿐 아니라 모든 후손에 적용됩니다.

복습할 때 각 키가 허용되는 상한·하한을 내려가며 적습니다. 전체 그래프를 연결하는 트리는 다음 최소 신장트리에서 다룹니다.