트리와 이진 탐색 트리

트리(Tree)는 계층 관계를 표현하는 비선형 자료구조다. 노드 하나가 여러 자식을 가지는 1:N 관계가 반복된다. 그래프의 관점에서 보면 사이클이 없는 연결 그래프이고, 노드가 n개면 간선은 정확히 n-1개다. 파일 시스템, DOM, 조직도, 힙, 구문 트리가 모두 트리다.

용어

이진 트리

모든 노드의 자식이 최대 2개이고, 왼쪽 자식과 오른쪽 자식을 구분하는 트리다. 정의 자체가 재귀적이다. 이진 트리는 공집합이거나, 루트와 왼쪽 이진 트리·오른쪽 이진 트리로 이루어진 것이다. 그래서 거의 모든 연산을 재귀로 짤 수 있다.

높이가 h인 이진 트리의 노드 수 n은 다음 범위에 있다.

h + 1  ≤  n  ≤  2^(h+1) - 1
(편향 트리)    (포화 이진 트리)

배열로 표현하기

완전 이진 트리는 레벨 순서대로 번호를 매겨 배열에 담을 수 있다. 0번 칸을 비우고 루트를 1번에 두면 인덱스 계산이 간단해진다.

부모: i // 2      왼쪽 자식: 2i      오른쪽 자식: 2i + 1

편향 트리를 배열로 담으면 빈 칸이 지수적으로 늘어나므로, 모양이 자유로운 트리는 노드에 left·right 참조를 두는 연결 표현을 쓴다.

순회 (Traversal)

노드에서 할 일은 세 가지다. 자기 값 처리(V), 왼쪽 서브트리(L), 오른쪽 서브트리(R). V를 언제 하느냐로 순회 이름이 갈린다.

def preorder(node):
    if node is None:          # 재귀 순회의 종료 조건
        return
    print(node.val)
    preorder(node.left)
    preorder(node.right)

값이 모두 다를 때 전위 + 중위 순회 결과가 있으면 트리를 하나로 복원할 수 있다. 전위의 첫 원소가 루트이고, 중위에서 그 루트의 왼쪽이 왼쪽 서브트리, 오른쪽이 오른쪽 서브트리다. 이 분할을 재귀로 반복한다. 후위 + 중위도 같은 원리다. 전위 + 후위만으로는 자식이 하나인 노드의 방향을 알 수 없어 복원이 안 된다. 중위 순회 하나만으로도 모양이 정해지지 않으므로, 트리를 직렬화할 때는 빈 자식 자리까지 기록한 전위(또는 후위) 순회를 쓴다.

재귀 순회는 호출 스택에 높이 h만큼 프레임이 쌓여 공간 O(h) 다. 균형 트리면 O(log n)이지만 편향 트리면 O(n)이고, 노드가 수만 개면 재귀 한도에 걸린다. 그래서 반복문 버전도 짤 수 있어야 한다. 전위는 스택에 루트를 넣고 꺼낼 때마다 오른쪽, 왼쪽 순으로 넣는다. 중위는 왼쪽 끝까지 내려가며 쌓고, 꺼내서 방문한 뒤 오른쪽 자식으로 옮긴다.

def inorder_iter(root):
    stack, node, out = [], root, []
    while stack or node:
        while node:                 # 왼쪽 끝까지 내려가며 쌓는다
            stack.append(node)
            node = node.left
        node = stack.pop()
        out.append(node.val)        # 왼쪽을 다 본 뒤 자기 자신
        node = node.right           # 그다음 오른쪽 서브트리
    return out

이진 탐색 트리 (BST)

이진 탐색 트리는 모든 노드에서 왼쪽 서브트리의 키 < 노드의 키 < 오른쪽 서브트리의 키가 성립하는 이진 트리다. 키는 중복되지 않는다고 가정한다.

• 탐색: 루트부터 찾는 키와 비교해 작으면 왼쪽, 크면 오른쪽으로 내려간다. 이분 탐색을 트리 모양으로 펼친 것이다.
• 삽입: 탐색이 실패한 자리(빈 자식)에 새 노드를 단다.
• 삭제: 지울 노드를 찾은 뒤 자식 수로 나뉜다.

세 연산 모두 루트에서 한 경로만 따라 내려가므로 O(높이)다. 그래서 문제가 BST를 준다면 O(n)보다 빠른, 한 경로만 따라 내려가는 풀이를 기대한다는 뜻이다. 최솟값은 맨 왼쪽, 최댓값은 맨 오른쪽 노드다.

높이는 넣는 순서가 정한다. 균형이 잡히면 O(log n)이지만, 1, 2, 3, 4, 5처럼 오름차순으로 넣으면 모든 노드가 오른쪽 자식만 가지는 편향 트리가 되어 O(n)까지 떨어진다. 내림차순이면 왼쪽으로만 뻗고, 지그재그(1, 5, 2, 4, 3)처럼 매번 남은 범위의 끝 값을 넣어도 높이가 n-1이 된다. 무작위 순서로 넣으면 기대 높이는 O(log n)이지만 보장은 없다. 이것이 BST의 한계이고, 균형 트리가 필요한 이유다.

BST인지 검증하기는 자주 나오는 함정이다. 각 노드를 자기 자식하고만 비교하면 틀린다. 루트 10의 왼쪽 서브트리 깊은 곳에 15가 있어도 부모-자식 비교는 통과하기 때문이다. 내려가면서 허용 범위 (low, high)를 함께 넘겨 왼쪽으로 갈 때 high를, 오른쪽으로 갈 때 low를 좁히거나, 중위 순회 결과가 엄격히 증가하는지 확인한다.

def is_bst(node, low=float('-inf'), high=float('inf')):
    if node is None:
        return True
    if not (low < node.val < high):
        return False
    return is_bst(node.left, low, node.val) and is_bst(node.right, node.val, high)

m-원 탐색 트리: 삼진 탐색 트리는 가능한가

같은 논리를 자식 3개로 넓힐 수 있다. 노드에 키 두 개 k1 < k2를 두고, 자식을 k1보다 작은 쪽·k1과 k2 사이·k2보다 큰 쪽 세 개로 나누면 3원 탐색 트리가 된다. 일반화하면 키 m-1개와 자식 m개를 두는 m-원 탐색 트리(m-way search tree) 이고, 여기에 균형 규칙을 더한 것이 2-3 트리와 B 트리다.

메모리 안에서는 비교 횟수가 오히려 늘어 이득이 없다. 노드 하나를 읽는 비용이 비교보다 훨씬 큰 디스크에서는 높이가 줄어드는 쪽이 이기므로, 노드에 키를 수백 개 담는 B 트리로 간다. 문자열 사전에서 「삼진 탐색 트리(ternary search tree)」라는 이름은 이것과 다른 구조다. 노드가 글자 하나를 갖고 작음·같음·큼 세 자식으로 다음 글자를 찾는 트라이의 변형을 가리킨다.

균형 이진 탐색 트리와 AVL

균형 트리(BBST, Balanced Binary Search Tree)는 삽입·삭제 때마다 높이가 O(log n)을 넘지 않도록 모양을 고치는 BST다. 균형을 정의하는 방식에 따라 여러 종류가 있다.

가장 먼저 제안된 것이 AVL 트리(Adelson-Velsky & Landis)다.

• 노드마다 균형 인수 BF = 왼쪽 서브트리 높이 − 오른쪽 서브트리 높이를 관리한다.
• 모든 노드의 BF는 -1, 0, +1 중 하나여야 한다.
• 삽입 뒤 새 노드에서 루트 쪽으로 올라가며 BF를 확인하다가 |BF| > 1인 첫 노드에서 회전(rotation) 으로 균형을 되찾는다.

flowchart LR
  subgraph before["LL 불균형"]
    direction TB
    A30["30"] --> A20["20"]
    A20 --> A10["10"]
  end
  subgraph after["오른쪽 회전 뒤"]
    direction TB
    B20["20"] --> B10["10"]
    B20 --> B30["30"]
  end
  before -->|"오른쪽 회전"| after

회전의 결과는 언제나 같다. 문제가 된 세 노드 중 값이 가운데인 노드가 부모가 되고, 나머지 둘이 좌우 자식이 된다.

구현

노드마다 자기 서브트리의 높이를 저장해 두면 BF를 O(1)에 계산할 수 있다. 새 노드의 높이는 1이고, 빈 자식의 높이는 0으로 친다. 회전할 때 옮겨 붙는 가운데 서브트리(T2)를 잊지 않는 것이 핵심이다.

def h(n): return n.height if n else 0
 
def rotate_right(z):          # LL: z의 왼쪽 자식 y가 새 루트
    y, t2 = z.left, z.left.right
    y.right, z.left = z, t2
    z.height = 1 + max(h(z.left), h(z.right))   # 아래쪽(z)부터 갱신
    y.height = 1 + max(h(y.left), h(y.right))
    return y                  # rotate_left는 left/right를 바꾼 대칭
 
def insert(node, key):
    if node is None:
        return Node(key)      # height = 1
    if key < node.key: node.left = insert(node.left, key)
    else:              node.right = insert(node.right, key)
    node.height = 1 + max(h(node.left), h(node.right))
    bf = h(node.left) - h(node.right)
    if bf > 1:                                   # 왼쪽이 무겁다
        if key > node.left.key:                  # LR → 먼저 왼쪽 자식을 왼쪽 회전
            node.left = rotate_left(node.left)
        return rotate_right(node)
    if bf < -1:                                  # 오른쪽이 무겁다
        if key < node.right.key:                 # RL
            node.right = rotate_right(node.right)
        return rotate_left(node)
    return node

재귀가 리프에서 루트로 되돌아오며 높이를 갱신하고 BF를 검사하므로, "새 노드에서 루트 쪽으로 올라가며 확인한다"는 규칙이 그대로 코드가 된다.

AVL은 균형 조건이 엄격해 탐색이 빠른 대신 삽입·삭제 때 회전이 잦다. 조건을 느슨하게 한 레드-블랙 트리는 회전이 적어 언어 표준 라이브러리의 정렬된 맵(C++ std::map, Java TreeMap)에 쓰인다. 디스크처럼 한 번 읽는 비용이 큰 곳에서는 한 노드에 키를 여러 개 담는 B 트리·B+ 트리를 쓴다(아래 절).

레드-블랙 트리

레드-블랙 트리는 노드에 빨강·검정 색을 칠하고 색 규칙으로 높이를 제한하는 균형 BST다.

가장 짧은 경로는 검정만, 가장 긴 경로는 검정·빨강이 번갈아 나오므로 가장 긴 경로가 가장 짧은 경로의 2배를 넘지 못한다. 그래서 높이가 O(log n)으로 묶인다.

새 노드는 빨강으로 삽입한다(검정 깊이를 깨지 않게). 부모도 빨강이면 Double Red가 되고, 삼촌(부모의 형제)의 색으로 처리가 갈린다.

삽입 전체는 O(log n)이고 회전은 최대 2번이다. AVL보다 덜 엄격하게 균형을 잡는 대신 수정 때 회전이 적다.

삭제도 먼저 BST 방식으로 지운다(자식이 둘이면 후계자 값을 옮기고 후계자를 지운다). 지운 노드가 빨강이면 규칙이 깨지지 않아 끝이다. 검정이면 그 경로의 검정 깊이가 1 줄어드므로, 그 자리에 「검정 하나가 모자란」 표시(double black)를 두고 형제의 색과 형제 자식의 색에 따라 색 바꾸기나 회전으로 모자란 검정을 채운다. 삭제도 O(log n)이고 회전은 최대 3번이다.

Java TreeMap·TreeSet, C++ std::map, 리눅스 커널의 스케줄러 실행 큐·가상 메모리 영역 관리가 레드-블랙 트리를 쓰고, Java HashMap도 충돌이 많은 버킷을 레드-블랙 트리로 바꾼다(해시 테이블).

레드-블랙 트리는 2-3-4 트리를 이진 노드로 옮겨 적은 것이다. 검정 노드 하나와 그 빨강 자식들(02개)을 묶으면 키 13개짜리 2-3-4 노드 하나가 된다. 「빨강 연속 금지」는 한 노드에 키가 넘치지 않게 하고, 「검정 깊이가 같다」는 2-3-4 트리의 모든 리프가 같은 깊이라는 규칙이다. 삽입 때 색 바꾸기는 넘친 2-3-4 노드를 쪼개 가운데 키를 위로 올리는 일과 같다.

다른 균형 트리가 있는데도 레드-블랙 트리가 범용 정렬 맵의 기본이 된 이유는 다음과 같다.

B 트리와 B+ 트리

B 트리는 노드 하나에 키를 여러 개 담는 균형 m-원 탐색 트리다. 차수 m인 B 트리는 다음 규칙을 지킨다.

• 노드는 자식을 최대 m개, 키를 최대 m-1개 가진다. 자식이 k개면 키는 k-1개다.
• 루트가 아닌 내부 노드는 자식을 최소 ⌈m/2⌉개 가진다. 노드가 반 이상 차 있어야 높이가 log_m n에 묶인다.
• 모든 리프가 같은 깊이에 있다.
• 삽입으로 노드가 넘치면 가운데 키를 부모로 올리며 둘로 쪼갠다. 쪼개짐이 루트까지 번지면 새 루트가 생겨 트리가 위로 자란다. 삭제로 노드가 모자라면 형제에게서 키를 빌리거나 형제와 합친다.

B+ 트리는 B 트리에서 데이터 위치와 리프 연결을 바꾼 변형이다.

DB가 B+ 트리를 쓰는 이유(페이지 단위 I/O, 높이 3~4)는 DB 내부 구조의 「왜 B+트리인가」에 있다.

다차원 탐색 트리: KD 트리, KDB 트리, R 트리

BST와 B 트리는 키가 한 축에서 정렬될 때 쓴다. 지도 위의 점, 「이 사각형 안의 가게」, 「가장 가까운 점」처럼 키가 2차원 이상이면 축을 나눠 공간을 쪼개는 트리를 쓴다.

공간을 겹치지 않게 자르면(KD, KDB) 한 점은 한 영역에만 속하고, 객체 단위로 묶으면(R) 영역이 겹치는 대신 크기 있는 객체를 쪼개지 않고 담는다.

트리 문제를 푸는 요령

경계 사례는 빈 트리, 노드 1개와 2개, 연결 리스트처럼 한쪽으로 뻗은 편향 트리다.

정리

• 트리 = 사이클 없는 연결 그래프. 노드 n개, 간선 n-1개
• 완전 이진 트리는 배열(2i, 2i+1)로, 모양이 자유로운 트리는 연결 구조로 저장한다.
• 중위 순회는 BST를 정렬 순서로 읽는다. 레벨 순회는 BFS다. 재귀 순회의 공간은 O(높이)다.
• BST 검증은 부모-자식 비교가 아니라 범위 (low, high)를 내려보내 한다.
• BST 연산은 O(높이)이므로 균형이 성능을 정한다. AVL은 BF를 -1~1로 유지하며 네 가지 회전으로 균형을 잡는다.
• 레드-블랙 트리는 2-3-4 트리를 이진 노드로 옮긴 것으로, 수정 때 회전이 상수 번이라 범용 정렬 맵의 기본이다.
• B+ 트리는 데이터를 리프에만 두고 리프를 이어 범위 조회와 디스크 I/O에 맞춘 B 트리다.

관련 노트: 최소 공통 조상 (LCA), 기초 자료구조(CS50), 힙과 우선순위 큐, 그래프의 기본, 재귀 함수, 비헤이비어 트리, 세그먼트 트리