Chapter 5: 이진 탐색 트리

내용 정리

이진 탐색 트리 구조

• 트리는 노드가 여러 갈래로 분기하는 계층적 자료 구조다

• 연결 리스트에서 각 노드는 하나의 다음 노드만 가리키지만, 트리의 노드는 여러 자식 노드를 가리킬 수 있다

• 이진 트리는 각 노드가 최대 2개의 자식을 가질 수 있다

• 노드에 부모 포인터를 저장하면 탐색이나 노드 제거 같은 연산에서 유용하다

• 모든 노드 N에 대해,

  • N의 왼쪽 하위 트리에 속한 모든 노드의 값은 N의 값보다 작으며,

  • N의 오른쪽 하위 트리에 속한 모든 노드의 값은 N의 값보다 크다

• 노드 값은 큰 범위를 왼쪽, 작은 범위를 오른쪽(또는 그 반대)으로 구분하는 표지판 역할을 한다

이진 탐색 트리에서 탐색하기

• 반복적 탐색(Iterative)

  • 설명

    • while 루프를 사용해 트리를 내려가며 탐색한다

  • 장점

    • 스택을 사용하지 않아 메모리를 효율적으로 쓸 수 있다

  • e.g.

    ```python
    from __future__ import annotations
    from typing import Optional
    
    class TreeNode:
        def __init__(self, value: int) -> None:
            self.value = value
            self.left: Optional[TreeNode] = None
            self.right: Optional[TreeNode] = None
    
    def insert_node_iterative(root: Optional[TreeNode], value: int) -> TreeNode:
        if root is None:
            return TreeNode(value)
    
        current = root
        while True:
            if value < current.value:
                if current.left is None:
                    current.left = TreeNode(value)
                    break
                current = current.left
            else:
                if current.right is None:
                    current.right = TreeNode(value)
                    break
                current = current.right
        return root
    
    def iterative_search(root: Optional[TreeNode], value: int) -> bool:
        current = root
        while current:
            if current.value == value:
                return True
            current = current.left if value < current.value else current.right
        return False
    ```

• 재귀적 탐색(Recursive)

  • 설명

    • 함수가 자신을 호출하는 구조

  • 장점

    • 간결한 코드

  • 단점

    • 트리가 깊을 경우 스택 오버플로우 위험이 있다

  • e.g.

    ```python
    def insert_node_recursive(root: Optional[TreeNode], value: int) -> TreeNode:
        if root is None:
            return TreeNode(value)
        if value < root.value:
            root.left = insert_node_recursive(root.left, value)
        else:
            root.right = insert_node_recursive(root.right, value)
        return root
    
    def recursive_search(root: Optional[TreeNode], value: int) -> bool:
        if root is None:
            return False
        if root.value == value:
            return True
        if value < root.value:
            return recursive_search(root.left, value)
        else:
            return recursive_search(root.right, value)
    ```

이진 탐색 트리 변경하기

• 이진 탐색 트리를 감싸는 간단한 자료 구조(wrapper)를 사용하면 루트 노드 처리를 단순화할 수 있다

• 노드를 삽입할 때는 탐색과 같은 로직을 따라가며, 중복 허용 여부에 따라 처리 방식이 달라진다

• 노드를 제거할 때는 노드가 리프인지, 자식이 하나인지, 두 개인지에 따라 제거 방식이 달라진다

• 두 자식을 가진 노드를 제거하려면 후속자(successor) 노드와 교환 후 제거하는 과정을 거친다

균형이 맞지 않는 트리

• 트리가 완전히 균형을 이룰 경우 노드 수가 2배로 늘어날 때마다 트리 깊이는 1씩만 증가해 대략 O(log N) 성능을 낸다

• 균형이 무너진 트리는 삽입·삭제를 반복할 때 깊이가 선형적으로 늘어나 O(N)까지 성능이 떨어질 수 있다

• 균형을 유지하려면 red-black 트리처럼 추가 규칙을 도입해야 하며, 이로 인한 연산 복잡도 증가라는 대가가 따른다

이진 탐색 트리 대량 구축

• 반복 삽입으로 트리를 만들면 균형이 깨질 위험이 있다

• 정렬된 배열에서 중간 요소를 루트로 잡고, 왼쪽/오른쪽 서브트리에 대해 재귀적으로 같은 작업을 수행하면 균형 잡힌 이진 탐색 트리를 만들 수 있다