Search Trees (1)

 지난 글에서 Map and Hash 단원을 정리하면서 마지막에 남겨둔 문제가 하나 있었다: Sorted Map(sorted search table)은 binary search로 탐색이 O(log n)이지만, insert/delete는 배열을 shift해야 해서 여전히 O(n)이다.

 

 이 단원(Search Tree)은 이 문제를 해결하는 게 목표다. 큰 흐름은:

BST(Binary Search Tree) — 트리 구조로 정렬된 데이터를 표현하면 insert/delete에서 shifting이 필요 없다. 하지만 트리가 한쪽으로 치우치면 height가 O(n)이 될 수 있다 → AVL Tree — "양쪽 자식의 height 차이는 최대 1"이라는 규칙을 추가해서, height를 O(log n)으로 강제한다.

 

 이 글(1부)에서는 BST의 기본(정의, search, insert, delete)과 AVL Tree(height-balance property, insert/delete 시 rotation)를 다룬다. 2부에서는 Multi-way Search Tree, (2,4) Tree, Splay Tree, Red-Black Tree를 다룰 예정이다.

---

1. Binary Search Tree (BST) — 정의와 Search/Insert

1.1 재귀적 정의

BST는 다음 중 하나다:

• 빈 트리, 또는
• 다음을 만족하는 binary tree:
  • root가 key를 가진다
  • 왼쪽 subtree의 모든 key < root의 key
  • 오른쪽 subtree의 모든 key > root의 key
  • 왼쪽/오른쪽 subtree도 각각 BST다 (재귀적)

1.2 Inorder Traversal = 정렬된 순서

BST를 inorder(왼쪽 subtree → root → 오른쪽 subtree)로 순회하면 key들이 정렬된 순서로 나온다. 예를 들어 다음 트리:

          50
        /    \
      30      70
     /  \    /  \
    20  40  60  80

 

 이 트리의 inorder traversal은 20, 30, 40, 50, 60, 70, 80으로, 정렬된 순서 그대로다. 이게 바로 "BST가 Sorted Map을 구현한다"는 말의 의미다. 트리 구조 자체에 정렬 정보가 내재되어 있어서, 별도의 정렬 작업 없이도 inorder만 돌면 sorted sequence가 나온다.

1.3 TreeSearch — key 찾기

Algorithm TreeSearch(T, p, k):
    if k == p.key():
        return p                              # 찾음
    elif k < p.key() and T.left(p) is not None:
        return TreeSearch(T, T.left(p), k)    # 왼쪽으로
    elif k > p.key() and T.right(p) is not None:
        return TreeSearch(T, T.right(p), k)   # 오른쪽으로
    return p                                  # 못 찾음 — 마지막 위치 반환

 

가장 중요한 포인트: 못 찾았을 때 단순히 "실패"가 아니라, "마지막으로 방문한 위치 p를 반환"한다. 이 위치가 바로 "k가 있어야 할 자리"다. 이건 [1부](이전 글)에서 다룬 binary search의 inexact search(못 찾으면 들어갈 위치를 알려줌)와 정확히 같은 아이디어다 — 배열에서는 "인덱스"로, 트리에서는 "마지막 노드"로 위치를 알려준다는 차이뿐이다.

 

예를 들어 위 트리에서:

• TreeSearch(T, root, 40): 50→(40<50, 왼쪽)→30→(40>30, 오른쪽)→40 → 40에서 발견
• TreeSearch(T, root, 45): 50→30→40까지 같은 경로로 갔다가, 45>40인데 40의 오른쪽 자식이 없으므로 40에서 멈춤(못 찾음). 이 결과로부터 "45는 40의 오른쪽 자식으로 들어가야 한다"는 걸 알 수 있다 (45>40이므로 BST 속성상 오른쪽).

1.4 TreeInsert — (k,v) 삽입

Algorithm TreeInsert(T, k, v):
    p = TreeSearch(T, T.root(), k)
    if k == p.key():
        p의 value를 v로 갱신
    elif k < p.key():
        (k,v)를 p의 left child로 추가
    else:
        (k,v)를 p의 right child로 추가

 

"TreeSearch가 실패한 그 위치(p)에, 새 노드를 leaf로 붙인다"는 게 핵심이다. Insert는 항상 leaf 위치에 새 노드가 생긴다.

 

1.5 BST vs Sorted Array — 왜 BST가 더 나은가, 그리고 새로운 문제

Sorted array에서 binary search는 O(log n)이지만 insert/delete는 shifting 때문에 O(n)이었다. BST에서는:

• Search: O(h) (h = tree의 height)
• Insert: TreeSearch로 위치 찾기(O(h)) + 그 자리에 노드 하나 붙이기(O(1)) = O(h), shifting 없음!

h가 O(log n)이라면 둘 다 O(log n)이 되어 array보다 훨씬 좋아진다.

하지만 h가 항상 O(log n)인 건 아니다. 위 트리에 45, 46, 47, 48, 49를 순서대로 계속 삽입하면:

          50
        /      \
      30        70
     /  \      /  \
    20  40    60   80
          \
           45
            \
             46
              \
               47
                \
                 48
                  \
                   49

 원래 height는 2였는데, 5개를 더 넣었을 뿐인데 49는 root에서 7단계나 떨어진 곳에 있다. 계속 큰 값을 넣으면 이 "꼬리"가 계속 길어져서 height = O(n)이 될 수 있다. 이 경우 search/insert는 O(h)=O(n)이 되어, sorted array의 문제로 회귀한다. 이게 AVL Tree가 필요한 이유다.

---

2. BST — Delete

2.1 Easy Case: 자식이 0개 또는 1개

• 자식 0개 (leaf): 그냥 제거.
• 자식 1개: 노드 p를 제거하고, 그 자리를 p의 자식으로 대체한다 (부모-자식 연결을 한 단계 건너뛰기).

   parent                    parent
     |          삭제 후         |
     X          ───────►       Y
    /
   Y  (X의 유일한 자식)

 이 두 경우가 "쉬운" 이유는, BST 속성이 자동으로 유지되기 때문이다. 자식이 하나뿐이면, 그 자식(과 서브트리)을 그대로 끌어올려도 대소 관계가 깨지지 않는다.

 

2.2 Hard Case: 자식이 2개

자식이 2개면 "어느 자식을 끌어올릴지" 정할 수 없다. 대신, BST 속성을 유지하면서 p를 대체할 수 있는 값을 찾는다:

• Predecessor (왼쪽 subtree의 최댓값), 또는
• Successor (오른쪽 subtree의 최솟값)

이 중 하나를 p의 자리에 복사하고, 그 다음 원래 그 값이 있던 노드를 삭제한다.

 

 왜 이게 항상 Easy Case로 환원되는가? Predecessor(왼쪽 subtree의 최댓값)는 오른쪽 자식을 절대 가질 수 없다. 만약 오른쪽 자식이 있다면, BST 속성("오른쪽 subtree는 더 크다")에 따라 그 자식이 더 큰 값이 되어버려서 "내가 최댓값"이라는 전제와 모순된다. (단, 왼쪽 자식은 가질 수 있다 — 왼쪽 자식은 더 작은 값이므로 "최댓값"이라는 전제와 모순되지 않는다.)

 

결론: predecessor는 자식이 최대 1개(왼쪽만 가능) → 항상 Easy Case. Successor도 대칭적으로(왼쪽 자식 없음) 동일하게 성립한다.

 

2.3 직접 따라가보는 예제

다음 트리에서 40(자식 2개: 35, 45)을 삭제해보자:

          50
        /    \
      30      70
     /  \    /  \
    20  40  60  80
       /  \
      35  45

 

Predecessor(35)로 대체하는 경우: 40의 자리에 35를 복사하고, 원래 35(leaf, Easy Case)를 제거. 원래 40의 오른쪽 자식이었던 45는 그대로 남아서, 새 "35" 노드의 오른쪽 자식이 된다:

          50
        /    \
      30      70
     /  \    /  \
    20  35  60  80
         \
          45

 

 

Successor(45)로 대체하는 경우: 40의 자리에 45를 복사하고, 원래 45(leaf, Easy Case)를 제거. 원래 40의 왼쪽 자식이었던 35는 그대로 남아서, 새 "45" 노드의 왼쪽 자식이 된다:

          50
        /    \
      30      70
     /  \    /  \
    20  45  60  80
       /
      35

 

 두 결과를 비교하면: predecessor를 쓰면 "원래 그 자리의 오른쪽 자식(45)"이 남고, successor를 쓰면 "원래 그 자리의 왼쪽 자식(35)"이 남는다 — 대칭적인 구조다. 둘 다 유효한 BST이고, 어느 쪽을 써도 상관없다.

---

3. AVL Tree — Height-Balance Property

3.1 Height의 재정의

AVL에서는 height를 "edge 개수" 대신 "node 개수"로 정의한다:

• leaf의 height = 1
• "null child"(자식 없는 자리)의 height = 0
• 일반 노드의 height = 1 + max(왼쪽 자식 height, 오른쪽 자식 height)

 

3.2 Height-Balance Property

T의 모든 위치 p에 대해, p의 두 자식의 height 차이가 최대 1이다.

 

 이 속성을 만족하는 BST를 AVL Tree라고 한다. Balance Factor(BF) = 왼쪽 자식 height − 오른쪽 자식 height로 정의하면, AVL tree에서는 모든 노드의 BF가 -1, 0, +1 중 하나여야 한다.

참고: height-balance property를 만족한다고 해서 트리가 "완벽하게 꽉 찬(full)" 모양일 필요는 없다. 이 느슨한 조건만으로도 height가 O(log n)임이 보장된다(증명은 강의 범위 밖).

 

3.3 직접 계산해보는 예제

다음 트리가 AVL인지 확인해보자:

          50
        /    \
      30      70
     /  \       \
    20  40       80
                 /
                75

 

Step 1: Height 계산 (bottom-up)

• Leaf들(20, 40, 75)의 height = 1
• 80: 왼쪽 자식 없음(0), 오른쪽 75(1) → height = 1+max(0,1) = 2
• 30: 왼쪽 20(1), 오른쪽 40(1) → height = 1+max(1,1) = 2
• 70: 왼쪽 없음(0), 오른쪽 80(2) → height = 1+max(0,2) = 3
• 50: 왼쪽 30(2), 오른쪽 70(3) → height = 1+max(2,3) = 4

              50 (h=4)
            /        \
        30 (h=2)    70 (h=3)
        /    \           \
   20(h=1) 40(h=1)      80 (h=2)
                          /
                        75 (h=1)

 

Step 2: Balance Factor 계산

노드	BF (왼쪽-오른쪽)	AVL 조건(-1~+1) 만족?
50	2-3 = -1	✓
30	1-1 = 0	✓
70	0-2 = -2	❌
80	1-0 = 1	✓
leaf들	0	✓

70에서 BF=-2로 위반! → 이 트리는 AVL이 아니다.

 

 여기서 흔히 빠지는 함정: height를 계산하는 것과 "AVL인지 확인하는 것"은 별개의 단계다. Height 계산이 다 맞아도, 각 노드의 balance factor를 따로 계산해서 -1~+1 범위를 확인해야 한다. (특히 70처럼 자식이 하나뿐인 노드 — 왼쪽이 없어서 height=0, 오른쪽 자식의 height가 2 이상이면 바로 BF=±2가 될 수 있으니 주의.)

---

4. AVL Tree — Insert & Rotation (Trinode Restructuring)

4.1 AVL Insert의 전체 흐름

1. 일반 BST처럼 leaf 위치에 새 노드를 삽입한다
2. 새로 삽입된 위치에서 root까지 거슬러 올라가며, balance factor가 ±2가 되는 첫 번째 노드를 찾는다 → 이 노드를 z라고 한다
3. z를 trinode restructuring(rotation)으로 고친다

4.2 x, y, z 정하기

• z = 위반을 발견한 노드
• y = z의 두 자식 중 height가 더 큰 자식
• x = y의 두 자식 중 height가 더 큰 자식 (같으면, z 쪽에서 본 것과 같은 방향의 자식을 선택)

4.3 통일된 알고리즘 — case 구분 없이 한 번에!

교과서적으로 "LL, LR, RL, RR" 4가지 케이스를 외워야 할 것 같지만, 사실 하나의 절차로 처리 가능하다:

1. x, y, z를 key 값 기준으로 정렬해서 (a, b, c)라고 하자 (a<b<c, inorder 순서)
2. b가 새로운 subtree의 root가 된다
3. a는 b의 왼쪽 자식, c는 b의 오른쪽 자식이 된다
4. 원래 x,y,z에 직접 안 달려있던 4개의 subtree(T1~T4)도 inorder 순서대로 a의 왼쪽/오른쪽, c의 왼쪽/오른쪽에 붙인다

case 구분(single/double rotation, LL/LR/RL/RR)을 전혀 신경 쓸 필요 없이, "x,y,z를 정렬해서 가운데를 root로"라는 한 가지 규칙만 적용하면 끝이다.

4.4 Insert는 "Global Fix" — 왜 한 번만 고치면 끝인가

핵심 성질: insertion으로 인한 불균형은 항상 "더 큰 쪽 자식이 더 커져서" 생긴다. Trinode restructuring을 하면, 그 subtree의 height가 정확히 1만큼 줄어들어서 삽입 전의 원래 height로 복원된다. z의 부모 입장에서는 "z의 height가 삽입 전과 똑같다"고 보이므로, 부모는 전혀 영향을 받지 않는다 → 추가 확인 불필요. 이게 "global fix"다.

4.5 예제 1 — Single Rotation (LL case)

      30
     /  \
   20    40

여기에 10을 삽입하면:

        30
       /  \
     20    40
    /
  10

• h(10)=1, h(20)=1+max(1,0)=2, h(40)=1, h(30)=1+max(2,1)=3
• BF(20)=1-0=1, BF(30)=2-1=1 → 아직 AVL ✓

여기에 5를 또 삽입하면:

          30
         /  \
       20    40
      /
    10
   /
  5

• h(5)=1, h(10)=1+max(1,0)=2, h(20)=1+max(2,0)=3, h(30)=1+max(3,1)=4
• BF(10)=1-0=1✓, BF(20)=2-0=2 ❌ → z=20!
• (참고: BF(30)=3-1=2도 위반이지만, 삽입 위치(5)에서 climb up하며 만나는 첫 번째 위반이 z이므로 z=20)

z=20의 자식 중 height 큰 쪽 → y=10 (height=2). y=10의 자식 중 height 큰 쪽 → x=5 (height=1).

x=5 < y=10 < z=20 → a=5, b=10, c=20. b=10이 새 root, a=5가 왼쪽, c=20이 오른쪽 (T1~T4 모두 비어있음):

     10
    /  \
   5    20

이걸 30의 왼쪽 자식 자리에 다시 연결:

          30
         /  \
       10    40
      /  \
     5    20

새 height: h(10)=2, h(30)=1+max(2,1)=3. BF(30)=2-1=1로 위반이 사라졌다! z=20만 고쳤는데 30의 불균형(이전엔 BF=2)도 자동으로 해결됨 — global fix의 실제 예시다.

4.6 예제 2 — Double Rotation (RL case)

다시 처음 트리에서 시작:

      30
     /  \
   20    40

여기에 25를 삽입(20<25<30이므로 20의 오른쪽 자식):

        30
       /  \
     20    40
       \
       25

BF(20)=0-1=-1✓, BF(30)=2-1=1✓ → 아직 AVL.

여기에 22를 또 삽입(20<22<25, 25의 왼쪽 자식):

          30
         /  \
       20    40
         \
         25
        /
      22

• h(22)=1, h(25)=1+max(1,0)=2, h(20)=1+max(0,2)=3, h(30)=1+max(3,1)=4
• BF(20)=0-2=-2 ❌ → z=20

z=20의 자식 중 height 큰 쪽(유일한 자식) → y=25. y=25의 자식 중 height 큰 쪽(유일한 자식) → x=22.

z=20 < x=22 < y=25 → a=20, b=22, c=25. (이번엔 (a,b,c)=(z,x,y) 순서 — chunk 4-1의 single rotation 때와는 x,y,z의 상대적 위치가 다르다. 이게 "double rotation"이라고 불리는 케이스다.)

b=22가 새 root, a=20이 왼쪽, c=25가 오른쪽 (T1~T4 모두 비어있음):

       22
      /  \
    20    25

30의 왼쪽 자식 자리에 연결:

          30
         /  \
       22    40
      /  \
    20    25

BF(30)=2-1=1, BF(22)=1-1=0 → 다시 AVL ✓.

두 예제의 비교: 예제 1은 (a,b,c)=(x,y,z) (single rotation), 예제 2는 (a,b,c)=(z,x,y) (double rotation)였다. 하지만 "x,y,z를 key 순서로 정렬해서 가운데를 root로"라는 알고리즘은 완전히 동일했다. 굳이 "이건 LL이네, 이건 RL이네"를 판단할 필요 없이, 그냥 세 노드를 정렬하면 끝이다.

 

---

5. AVL Tree — Delete & Performance

5.1 Delete는 왜 "Local Fix"인가

Insert의 경우: 불균형은 "더 큰 쪽 자식이 더 커져서" 생긴다. Restructuring하면 height가 정확히 1 감소해서 원래 height로 복원된다 → 부모는 영향 없음 → 한 번이면 끝(global fix).

 

Delete의 경우: 불균형은 "더 작은 쪽 자식이 더 작아져서" 생긴다. z의 height(=1+max(왼쪽,오른쪽))는 삭제 전과 같을 수도 있다 (더 작은 쪽이 더 작아진 거라 max값엔 영향 없을 수 있음). 그런데 restructuring을 하면, 이번엔 z의 height가 삭제 전보다 1 줄어들 수 있다. 만약 z의 height가 줄어들고, z가 자기 부모의 "더 크거나 같은 height 쪽" 자식이었다면 → 부모의 height도 줄고, 부모도 새롭게 불균형해질 수 있다.

 

 그래서 delete는 z를 고친 후에도 계속 위로 올라가면서 또 다른 불균형이 있는지 확인해야 한다 — 이게 local fix다. 최악의 경우 root까지 O(log n)번의 restructuring이 필요할 수 있다 (각각은 O(1)이므로 전체는 여전히 O(log n)).

	Insert	Delete
불균형 발생 원인	더 큰 쪽이 더 커짐	더 작은 쪽이 더 작아짐
Restructuring 효과	height를 원래대로 복원	height가 추가로 감소할 수 있음
추가 조상 확인 필요?	❌ (1번이면 끝)	✅ (여러 번 필요할 수 있음)
최대 restructuring 횟수	1번	O(log n)번

 x, y, z를 찾는 방법은 insert와 동일하되, z는 "삭제된 위치에서부터 climb up하며 만나는 첫 번째 불균형 노드"이다. restructuring(a/b/c 알고리즘) 자체는 완전히 동일하다.

 

5.2 직접 따라가보는 Delete 예제

다음 AVL tree에서 40을 삭제해보자:

              50 (h=4)
            /        \
        30 (h=3)    70 (h=2)
        /    \       /   \
   20(h=2)  40(h=1) 60(h=1) 80(h=1)
     /
   10(h=1)

40은 leaf이므로 그냥 제거(Easy Case):

              50
            /        \
          30          70
          /            /   \
       20            60    80
        /
      10

climb up하며 확인: 30의 새 height = 1+max(h(20)=2, 오른쪽없음=0) = 3 (height는 삭제 전과 동일, 왼쪽이 이미 더 컸으니까). 하지만 BF(30) = 2-0 = 2 ❌ → z=30

y = 30의 자식 중 height 큰 쪽 → 20(h=2). x = 20의 자식 중 height 큰 쪽 → 10(h=1).

x=10 < y=20 < z=30 → a=10, b=20, c=30. b=20이 새 root:

     20
    /  \
   10   30

50의 왼쪽 자식 자리에 연결:

              50
            /    \
          20      70
         /  \    /   \
       10   30  60   80

새 height: h(20)=2, h(70)=2, h(50)=1+max(2,2)=3. 50의 height가 4→3으로 감소했다!

여기서 50은 root라서 "부모 없음 → 끝"이지만, 만약 50이 더 큰 트리의 일부였다면, height가 줄어든 게 50의 부모의 balance factor에 영향을 줘서 거기서 또 불균형이 생길 수 있다. 그럼 그 부모에서 또 한 번 a/b/c restructuring을 해야 한다 — 이게 "여러 번 반복될 수 있다"는 local fix의 의미다.

 

5.3 AVL Tree 전체 성능

AVL tree의 height는 항상 O(log n)으로 보장되므로, BST의 모든 연산(O(h))이 그대로 O(log n)이 된다:

Operation	Running Time
k in T	O(log n)
T[k] = v	O(log n)
T.delete(p), del T[k]	O(log n)
T.find_position(k)	O(log n)
T.first(), T.last(), T.find_min(), T.find_max()	O(log n)
T.before(p), T.after(p)	O(log n)
T.find_lt(k), find_le(k), find_gt(k), find_ge(k)	O(log n)
T.find_range(start, stop)	O(s + log n)
iter(T), reversed(T)	O(n)

 

 Map and Hash에서 sorted search table이 O(n)이었던 insert/delete가 드디어 O(log n)이 됐다. 동시에 sorted map의 모든 장점(find_min, find_range 등)도 그대로 유지된다.