Skip to content

Latest commit

 

History

History
108 lines (89 loc) · 4.65 KB

05_이진_탐색_트리.md

File metadata and controls

108 lines (89 loc) · 4.65 KB

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 트리처럼 추가 규칙을 도입해야 하며, 이로 인한 연산 복잡도 증가라는 대가가 따른다

이진 탐색 트리 대량 구축

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