Data Structure (8) Binary Search Tree

1 트리(Tree)

정의: 이진 탐색 트리 (Binary Search Tree, BST)

이진 탐색 트리는 각 노드의 왼쪽 서브트리에는 더 작은 값, 오른쪽 서브트리에는 더 큰 값만 오는 이진 트리다.

• 탐색/삽입/삭제: 균형 잡힌 경우 \(O(\log N)\), 편향된 경우 \(O(N)\)
• 중위 순회(In-order): 항상 오름차순으로 원소를 방문한다
• Python 표준 라이브러리는 BST를 직접 제공하지 않는다 (sortedcontainers.SortedList 활용)

• 트리는 가계도와 같이 계층적인 구조를 표현할 때 사용할 수 있는 자료구조다.
• 나무(tree)의 형태를 뒤집은 것과 같이 생겼다.
• 다수의 데이터를 관리하기에 적합한 트리 자료 구조의 가장 기본적인 형태

2 왜 필요한가

• 정렬된 데이터의 탐색, 삽입, 삭제를 평균 \(O(\log N)\) 에 수행할 수 있다.
• 데이터베이스 인덱스 구조의 기반이 되는 개념이다.
• 중위 순회를 수행하면 정렬된 순서로 데이터를 출력할 수 있다.
• 균형 이진 탐색 트리(AVL, Red-Black Tree)는 최악의 경우에도 \(O(\log N)\) 을 보장한다.

3 트리 용어 정리

• 루트 노드(root node): 부모가 없는 최상위 노드
• 단말 노드(leaf node): 자식이 없는 노드
• 트리(tree)에서는 부모와 자식 관계가 성립한다 (직계).
• 형제 관계 (sibling, 방계): 부모 node로 부터 왼쪽 자식과 오른쪽 자식과의 관계
• 깊이(depth): 루트 노드에서의 길이(length), 루트 노드로부터 손자까지의 depth=2
  • 이때, 길이란 출발 노드에서 목적지 노드까지 거쳐야 하는 간선의 수를 의미한다.
• 트리의 높이(height)은 루트 노드에서 가장 깊은 노드까지의 길이를 의미한다.

4 이진 트리(Binary Tree)

• 이진 트리는 최대 2개의 자식을 가질 수 있는 트리를 말한다.

5 이진 탐색 트리(Binary Search Tree)

• 다수의 데이터를 관리(조회, 저장, 삭제)하기 위한 가장 기본적인 자료구조 중 하나다.
• 이진 탐색 트리의 성질: 순서가 있음
  • 왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드
  • 루트 노드 기준 모든 왼쪽 노드들은 루트 노드보다 작음
  • 루트 노드 기준 모든 오른쪽 노드들은 루트 노드보다 큼
  • 2진 탐색을 가능하게 하는 구조

직관적 이해: 전화번호부 이진 탐색과 같다. 찾는 이름이 현재 페이지보다 앞이면 왼쪽 절반, 뒤면 오른쪽 절반을 탐색한다. 매번 탐색 범위가 절반으로 줄어 \(O(\log N)\) 이 된다.

BST 구조 시각화 (삽입 순서: 7, 4, 9, 2, 6):

        7           ← 루트 (root)
       / \
      4   9         ← 7보다 작으면 왼쪽, 크면 오른쪽
     / \
    2   6           ← 4보다 작으면 왼쪽, 크면 오른쪽

탐색(6): 7→왼쪽→4→오른쪽→6 (3번 비교)
탐색(8): 7→오른쪽→9→왼쪽→없음 (3번 비교, 탐색 실패)

5.1 이진 탐색 트리(Binary Search Tree)의 성질

• 특정한 노드의 키(key) 값보다 그 왼쪽 자식 노드의 키(key) 값이 더 작다.
• 특정한 노드의 키(key) 값보다 그 오른쪽 자식 노드의 키(key) 값이 더 크다.
• 특정한 노드의 왼쪽 서브 트리, 오른쪽 서브 트리 모두 이진 탐색 트리다.
• worst case: 찾는게 없을 때 혹은 찾고자 하는 데이터가 가장 마지막에 있을 때
  • 탐색시 재귀적으로 중앙값을 기준으로 오른쪽만 찾음
  • 매 실행마다 데이터의 개수가 절반씩 줄어듬
  • 그러면, 몇 번만에 사이즈가 1이 되는가?
  • 수식 유도, input size를 N이라고 가정했을때
  • \(N \times {(\frac{1}{2})}^{k}=1 \rightarrow N=2^k \rightarrow k = log_2N\)
  • 위의 수식을 점근적 표기법으로 표현하면 \(\Theta(logN)\)
• best case: 한번에 찾았을 때
  • \(\Theta(1)\)
• 그러므로, lower bound = \(\Theta(1)\), upper bound = \(O(logN)\)

5.2 삽입 연산

• 루트 노드에서 출발하여 아래쪽으로 내려오면서, 삽입할 위치를 찾는다.
  1. 삽입할 노드의 키(key)가 작으면 왼쪽으로,
  2. 삽입할 노드의 키(key)가 크면 오른쪽으로 삽입
• 삽입할 노드 목록 예시: [7,4,5,9,6,2,3,2,8]으로 트리 생성해보기



Binary Tree

Sorcue: 코딩 테스트를 위한 트리(Tree) 자료구조 10분 핵심 요약 By 동빈나

5.3 조회 연산

• 루트 노드에서 출발하여 아래쪽으로 내려오면서, 찾고자 하는 원소를 조회한다. 삽입 연산과 같은 로직을 따름
• 1 삽입할 노드의 키(key)가 작으면 왼쪽으로, 2 삽입할 노드의 키(key)가 크면 오른쪽으로 조회
• 조회할 노드 목록 예시: 5번 노드

5.4 삭제 연산

• 루트 노드에서 출발하여 아래쪽으로 내려오면서, 삭제할 원소에 접근한다.
• 삭제할 노드 목록 예시: 7번 노드
  • Case #1 왼쪽 자식이 없는 경우 → 오른쪽 자식으로 대체
  • Case #2 오른쪽 자식이 없는 경우 → 왼쪽 자식으로 대체
  • Case #3 왼쪽, 오른쪽이 모두 있는 경우 → 오른쪽 서브
• 트리에서 가장 작은 노드로 대체
• 삭제할 노드 목록 예시: 4번 노드



Binary Tree Deletion

Sorcue: 코딩 테스트를 위한 트리(Tree) 자료구조 10분 핵심 요약 By 동빈나

6 트리의 순회

• 트리에 포함되어 있는 정보를 모두 출력하고자 할 때, 어떤 방식을 사용할 수 있을까?
• 바로 순회(traversal)를 사용할 수 있다.
• 트리의 모든 노드를 특정한 순서(조건)에 따라서 방문하는 방법을 순회(traversal)라고 한다.

1. 전위 순회(pre-order traverse): 루트 방문 → 왼쪽 자식 방문 → 오른쪽 자식 방문
2. 중위 순회(in-order traverse): 왼쪽 자식 방문 → 루트 방문 → 오른쪽 자식 방문
3. 후위 순회(post-order traverse): 왼쪽 자식 방문 → 오른쪽 자식 방문 → 루트 방문

트리 순회는 “어떤 순서로 모든 노드를 방문하는가”의 문제다. 루트를 언제 방문하느냐에 따라 전위/중위/후위로 나뉜다.

• 전위(Pre-order): 루트 → 왼쪽 → 오른쪽 (트리 복사, 직렬화에 사용)
• 중위(In-order): 왼쪽 → 루트 → 오른쪽 (BST에서 오름차순 출력)
• 후위(Post-order): 왼쪽 → 오른쪽 → 루트 (트리 삭제, 후위 표기법에 사용)

6.1 트리의 순회 한 눈에 보기

• 전위 순회(pre-order traverse): A → B → D → E → C → F → G
• 중위 순회(in-order traverse): D → B → E → A → F → C → G
• 후위 순회(post-order traverse): D → E → B → F → G → C → A



Binary Tree Traverse

Sorcue: 코딩 테스트를 위한 트리(Tree) 자료구조 10분 핵심 요약 By 동빈나

6.2 전위 순회(pre-order traverse)

• 방문 방법: 현재 노드 → 왼쪽 자식 노드 → 오른쪽 자식 노드

def _preorder(self, node):
  if node:
    print(node.key, end=' ')
    self._preorder(node.left)
    self._preorder(node.right)

6.3 중위 순회(Inorder Traversal)

• 방문 방법: 왼쪽 자식 노드 → 현재 노드 → 오른쪽 자식 노드

def _inorder(self, node):
  if node:
    self._inorder(node.left)
    print(node.key, end=' ')
    self._inorder(node.right)

6.4 후위 순회(Postorder Traversal)

• 방문 방법: 왼쪽 자식 노드 → 오른쪽 자식 노드 → 현재 노드

def _postorder(self, node):
  if node:
    self._postorder(node.left)
    self._postorder(node.right)
    print(node.key, end=' ')

6.5 레벨 순회(Level Order Traversal)

• 낮은 레벨(루트)부터 높은 레벨까지 순차적으로 방문한다.
• 단순히 루트 노드에서부터 너비 우선 탐색(BST)를 진행하면 된다.
• 레벨 순회 순회(level-order traverse): A → B → C → D → E → F → G

7 이진 탐색 트리의 구현

• 다른 메서드 안에서 사용되는 메서드는 이름 앞에 언더바(_) 기호를 붙인다.

def search(self, node, key):
  return self._search(self.root, key) # search: recursively 조회

def _search(self, node, key):
  if node is None or node.key == key:
    return node

  # 현재 노드의 key보다 작은 경우
  if node.key > key:
    return self._search(node.left, key)

  # 현재 노드의 key보다 큰 경우
  elif node.key < key:
    return self._search(node.right, key)

7.1 편향 이진 트리(Skewed Binary Tree)

• 편향 이진 트리는 다음의 두 가지 속성을 가진다.

1. 같은 높이의 이진 트리 중 최소 개수의 노드 개수를 가진다.
2. 왼쪽 혹은 오른쪽으로 한 방향에 대한 서브 트리를 가진다.

7.2 이진 탐색 트리의 시간 복잡도

• 노드의 개수가 N개일 때, 시간 복잡도는 다음과 같다.
• 트리의 높이(height)을 H라고 할 때, 엄밀한 시간 복잡도는 \(O(H)\) 다.
• 이상적인 경우 H = log2 N로 볼 수 있다.
• 하지만 최악의 경우(편향된 경우) H = N로 볼 수 있다.

표 1: a list of the time complexity of the binary search trees in Python

Number	Methods	조회	삽입	삭제	수정
1	균형 잡힌 이진 탐색 트리	\(O(logN)\)	\(O(logN)\)	\(O(logN)\)	\(O(logN)\)
2	편향 이진 탐색 트리	\(O(N)\)	\(O(N)\)	\(O(N)\)	\(O(N)\)

See 표 1.

7.3 균형 잡힌 트리: AVL 트리

• AVL stands for Adelson-Velsky and Landis
• 이진 탐색 트리는 편향 트리가 될 수 있으므로, 최악의 경우 \(O(N)\) 을 요구한다.
• 반면에 AVL 트리는 균형이 갖춰진 이진 트리다.
• 간단한 구현 과정으로 완전 이진 트리에 가까운 형태를 유지하도록 한다.

from collections import deque


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


class BinarySearchTree:
    def __init__(self):
        self.root = None

    def search(self, node, key):
        return self._search(self.root, key)

    def _search(self, node, key):
        if node is None or node.key == key:
            return node

        # 현재 노드의 key보다 작은 경우
        if node.key > key:
            return self._search(node.left, key)
        # 현재 노드의 key보다 큰 경우
        elif node.key < key:
            return self._search(node.right, key)

    def insert(self, key):
        self.root = self._insert(self.root, key)

    def _insert(self, node, key):
        if node is None:
            return Node(key)

        # 현재 노드의 key보다 작은 경우
        if node.key > key:
            node.left = self._insert(node.left, key)
        # 현재 노드의 key보다 큰 경우
        elif node.key < key:
            node.right = self._insert(node.right, key)

        return node

    def delete(self, key):
        self.root = self._delete(self.root, key)

    def _delete(self, node, key):
        if node is None:
            return None

        # 현재 노드의 key보다 작은 경우
        if node.key > key:
            node.left = self._delete(node.left, key)
        # 현재 노드의 key보다 큰 경우
        elif node.key < key:
            node.right = self._delete(node.right, key)
        # 삭제할 노드를 찾은 경우
        else:
            # 왼쪽 자식이 없는 경우
            if node.left is None:
                return node.right
            # 오른쪽 자식이 없는 경우
            elif node.right is None:
                return node.left
            # 왼쪽과 오른쪽 자식 모두 있는 경우
            node.key = self._get_min(node.right)
            node.right = self._delete(node.right, node.key)

        return node

    def _get_min(self, node):
        key = node.key
        while node.left:
            key = node.left.key
            node = node.left
        return key

    def preorder(self):
        self._preorder(self.root)

    def _preorder(self, node):
        if node:
            print(node.key, end=' ')
            self._preorder(node.left)
            self._preorder(node.right)

    def inorder(self):
        self._inorder(self.root)

    def _inorder(self, node):
        if node:
            self._inorder(node.left)
            print(node.key, end=' ')
            self._inorder(node.right)

    def postorder(self):
        self._postorder(self.root)

    def _postorder(self, node):
        if node:
            self._postorder(node.left)
            self._postorder(node.right)
            print(node.key, end=' ')

    def levelorder(self):
        return self._levelorder(self.root)

    def _levelorder(self, node):
        if node is None:
            return

        result = []

        queue = deque()
        queue.append((0, node))  # (level, node)

        while queue:
            level, node = queue.popleft()
            if node:
                result.append((level, node.key))
                queue.append((level + 1, node.left))
                queue.append((level + 1, node.right))

        for level, key in result:
            print(f"level: {level}, key: {key}")

    def to_list(self):
        return self._to_list(self.root)

    def _to_list(self, node):
        if node is None:
            return []
        return self._to_list(node.left) + [node.key] + self._to_list(
            node.right)


arr = [7, 4, 5, 9, 6, 3, 2, 8]
bst = BinarySearchTree()
for x in arr:
    bst.insert(x)
print('전위 순회:', end=' ')
bst.preorder()
print('\n중위 순회:', end=' ')
bst.inorder()
print('\n후위 순회:', end=' ')
bst.postorder()
print('\n[레벨 순회]')
bst.levelorder()

bst.delete(7)
print('\n전위 순회:', end=' ')
bst.preorder()
print('\n중위 순회:', end=' ')
bst.inorder()
print('\n후위 순회:', end=' ')
bst.postorder()
print('\n[레벨 순회]')
bst.levelorder()

bst.delete(4)
print('\n전위 순회:', end=' ')
bst.preorder()
print('\n중위 순회:', end=' ')
bst.inorder()
print('\n후위 순회:', end=' ')
bst.postorder()
print('\n[레벨 순회]')
bst.levelorder()

bst.delete(3)
print('\n전위 순회:', end=' ')
bst.preorder()
print('\n중위 순회:', end=' ')
bst.inorder()
print('\n후위 순회:', end=' ')
bst.postorder()
print('\n[레벨 순회]')
bst.levelorder()

print(bst.to_list())
# 출력:
# 전위 순회:  7 4 3 2 5 6 9 8
# 중위 순회:  2 3 4 5 6 7 8 9
# 후위 순회:  2 3 6 5 4 8 9 7
# [레벨 순회]
# level: 0, key: 7
# level: 1, key: 4
# level: 1, key: 9
# level: 2, key: 3
# level: 2, key: 5
# level: 2, key: 8
# level: 3, key: 2
# level: 3, key: 6
# (delete(7) 후)
# 전위 순회:  8 4 3 2 5 6 9
# 중위 순회:  2 3 4 5 6 8 9
# 후위 순회:  2 3 6 5 4 9 8
# (delete(4) 후)
# 전위 순회:  8 5 3 2 6 9
# 중위 순회:  2 3 5 6 8 9
# 후위 순회:  2 3 6 5 9 8
# (delete(3) 후)
# 전위 순회:  8 5 2 6 9
# 중위 순회:  2 5 6 8 9
# 후위 순회:  2 6 5 9 8
# [2, 5, 6, 8, 9]

8 응용 분야

• 데이터베이스 인덱스: MySQL의 B-트리 인덱스가 BST를 기반으로 범위 쿼리를 \(O(\log N)\) 에 처리한다.
• 파일 시스템: 디렉터리 구조가 트리 형태로 구성된다.
• 딥러닝 의사결정 트리: 피처 분기 구조가 이진 트리로 표현된다.
• 중위 순회 활용: BST의 중위 순회 결과가 정렬 배열이므로, 정렬된 데이터 순회에 활용된다.
• 자동완성 검색: Trie(접두사 트리)가 BST의 확장형으로 문자열 탐색을 구현한다.

9 관련 주제

• 자료구조 개요
• 배열
• 연결 리스트
• 파이썬 리스트
• 스택
• 큐
• 덱
• 우선순위 큐
• 그래프