Binary Trees & AVL-Red-Black

1. Overview

이진 트리, AVL, 레드-블랙 트리(Binary Trees & AVL/Red-Black)는 배열의 O(n) 탐색 한계와 해시 테이블의 순서 부재를 단번에 극복하여, 데이터를 계층적으로 배치하고 탐색, 삽입, 삭제를 O(log n) 이하로 보장하는 자가 균형 트리(Self-Balancing Tree) 공학입니다.

학습자는 왼쪽 자식 ≤ 루트 ≤ 오른쪽 자식이라는 단순한 불변식(BST Property)이 이진 탐색트리(BST)를 만들고, 편향 입력(Skewed Input)이 이 트리를 O(n) 연결 리스트로 퇴화시키는 최악의 순간을 뜯어봅니다. 나아가 이 퇴화를 막기 위해 삽입/삭제 후 자동으로 균형을 맞추는 **AVL 트리(높이 균형)와 레드-블랙 트리(색깔 균형)**의 회전(Rotation) 역학을 해부하여, 리눅스 커널 스케줄러(CFS), Java TreeMap, C++ std::map이 모두 레드-블랙 트리를 채택한 이유를 통달하는 역량을 확보합니다.

2. Scope & Boundaries

In-Scope

• 이진 탐색트리 (BST): BST 불변식, 삽입/삭제/탐색 O(h), 중위순회(In-order) = 정렬 출력.
• 트리 순회 (Traversal): Pre-order, In-order, Post-order, BFS Level-order, Morris 순회(O(1) 공간).
• AVL 트리 (Height-Balanced): 균형 인수(Balance Factor), 4가지 회전(LL, LR, RL, RR), O(log n) 보장.
• 레드-블랙 트리 (Red-Black Tree): 5가지 레드-블랙 속성, 삽입/삭제 후 재채색(Recoloring)과 회전, O(log n) 보장.

Out-of-Scope

• B-트리와 B+트리: 디스크 블록 크기에 최적화된 데이터베이스 인덱스 트리 $\rightarrow$ 06-01. Database Index Internals 영역.
• 트라이(Trie) 트리: 문자열 접두사 탐색에 특화된 트리 $\rightarrow$ 04-02-04. Tries & Suffix Trees 영역.

Boundaries

• BST vs Hash Table: BST(std::map)는 O(log n) 탐색이지만 정렬된 순서(Ordered)를 보장하여 범위 탐색(Range Query, map.lower_bound(5))이 O(log n + k)에 가능합니다. 해시 테이블(std::unordered_map)은 O(1) 탐색이지만 순서 보장이 없어 범위 탐색이 O(n)으로 폭발합니다. 선택 기준은 순서/범위 질의 필요성입니다.

3. Counterexample

• 편향 BST의 퇴화 (Skewed BST Degeneration): "이진 탐색트리에 정렬된 데이터 [1,2,3,4,5]를 순서대로 삽입하면 O(log n) 탐색이 가능하겠지?"라는 착각. 오름차순으로 삽입된 BST는 모든 노드가 오른쪽 자식만 가지는 직선 형태(편향 트리, Skewed Tree)가 됩니다. 높이 h = n이 되어 탐색이 O(n) 연결 리스트와 동일해집니다. AVL/RB 트리 없는 순수 BST는 입력 순서에 따라 성능이 O(log n) ~ O(n)으로 천차만별입니다.
• AVL 과도 회전과 삽입 비용 (AVL over-rotation penalty): AVL 트리는 높이 차이가 1보다 커지는 즉시 회전을 강제합니다. 삽입이 매우 빈번하게 발생하는 서버 워크로드(예: 초당 100만 삽입)에서, 매번 균형 인수를 재계산하고 회전을 수행하는 오버헤드가 축적됩니다. 레드-블랙 트리는 색깔 속성으로 더 느슨한 균형(높이 최대 2log n)을 허용하여 삽입/삭제 시 회전 횟수가 최대 3번으로 제한되어, 삽입이 빈번한 실무에서 AVL보다 빠릅니다.

4. Prerequisites

• 재귀 (Recursion) (Basic): 트리 순회와 삽입/삭제 알고리즘이 모두 재귀로 구현됩니다. (04-03-01 Recursion)
• 이진 탐색 (Binary Search) (Basic): BST의 탐색 논리가 이진 탐색과 동일한 원리입니다. (04-01. Foundations)

5. Learning Map

6. Learning Topics

Basic

Core Topic 01: 왼쪽이 작고 오른쪽이 크다, BST 불변식과 편향의 위기 (BST Fundamentals)

• Why to Learn: 관계형 DB의 B+트리 인덱스부터 파일 시스템의 디렉토리 탐색까지, 계층 구조 탐색의 근원인 BST의 불변식(Invariant)과 그것이 무너지는 퇴화 시나리오를 장악하기 위함입니다.
• What to Learn:
  • Concepts: BST 불변식(Left subtree ≤ root ≤ Right subtree), 탐색/삽입/삭제 O(h), 후계자(In-order Successor) 삭제 알고리즘.
  • Skills: 최솟값/최댓값 탐색(leftmost/rightmost), 범위 탐색(Range Query).
  • Tools: 트리 시각화 도구, Online BST Visualization.
• How to Learn:
  • 1단계: 노드 {value, left, right} 구조로 [5, 3, 7, 1, 4, 6, 8] 삽입 후 트리 모양을 그려보고, search(4) 시 5→3→4 경로로 3번 비교 만에 찾아가는 O(log n) 탐색 역학을 해부합니다.
  • 2단계: 삭제 연산의 3가지 케이스: (1) 리프 노드: 그냥 삭제, (2) 자식 1개: 자식으로 대체, (3) 자식 2개: In-order 후계자(오른쪽 서브트리 최솟값)로 대체하는 후계자 알고리즘을 뜯어봅니다.
• Implement: 파이썬 BST 클래스. insert(v), search(v), delete(v), inorder() 구현. inorder() 결과가 항상 정렬된 순서임을 [5,3,7,1,4] 삽입 후 [1,3,4,5,7] 출력으로 증명. 편향 입력 [1,2,3,4,5] 삽입 후 트리 높이가 5(n)가 되어 search가 5번 비교를 요구함을 확인.

Recommended

Core Topic 02: 네 가지 방향의 회전과 균형의 수학, AVL 트리 (AVL Height Balance)

• Why to Learn: 편향 BST의 O(n) 퇴화를 박살 내기 위해 매 삽입/삭제 후 균형 인수를 추적하고, 4가지 회전으로 항상 높이를 O(log n) 이하로 유지하는 최초의 자가 균형 트리를 장악하기 위함입니다.
• What to Learn:
  • Concepts: 균형 인수(Balance Factor = Height(Left) - Height(Right)), LL/LR/RL/RR 4가지 불균형 케이스, 우회전(Right Rotation), 좌회전(Left Rotation).
  • Skills: 삽입 후 BF 역추적(Bottom-up), 이중 회전(LR = 좌회전+우회전).
  • Tools: AVL Tree Visualizer.
• How to Learn:
  • 1단계: LL 케이스(우회전): 왼쪽 자식의 왼쪽에 노드가 삽입되어 BF=+2가 될 때, 불균형 노드 A를 기준으로 우회전하면, A의 왼쪽 자식 B가 새 루트가 되고 A가 B의 오른쪽 자식이 되는 회전을 해부합니다.
  • 2단계: LR 케이스(이중 회전): 왼쪽 자식의 오른쪽에 삽입될 때, 먼저 왼쪽 자식을 좌회전한 뒤 루트를 우회전하는 이중 회전의 필요성을 뜯어봅니다.
• Implement: 파이썬 AVLTree 클래스. _height(node), _balance_factor(node), _rotate_right(node), _rotate_left(node) 구현. 편향 입력 [1,2,3,4,5] 삽입 시 AVL이 자동으로 균형을 맞춰 높이가 3(log₂5≈2.3)으로 유지됨을 트리 출력으로 증명.

Practical

Core Topic 03: 색깔로 균형을 맞추는 완화된 법칙, 레드-블랙 트리 (Red-Black Tree)

• Why to Learn: 실제 산업에서 가장 널리 쓰이는 트리가 AVL이 아닌 레드-블랙 트리인 이유(삽입/삭제 시 회전 횟수 최소화, 상수 3회 제한)와, 리눅스 CFS/Java TreeMap/C++ map의 공통 심장을 장악하기 위함입니다.
• What to Learn:
  • Concepts: 5가지 RB 속성(루트=검정, 리프=NIL, 빨강 자식은 검정, 모든 경로 검정 높이 동일, 새 삽입=빨강), 재채색(Recoloring), 회전 3케이스.
  • Skills: 삽입 후 Uncle 노드 색에 따른 Case 1/2/3 분기, 삭제 후 Double Black 해소.
  • Tools: 리눅스 커널 include/linux/rbtree.h.
• How to Learn:
  • 1단계: 삽입 Case 1(Uncle=Red): 새 빨강 노드의 Uncle이 빨강이면, 부모와 Uncle을 검정으로, 할아버지를 빨강으로 재채색(Recoloring)하고 할아버지로 문제를 올려(Propagate)보내는 재귀 해소를 해부합니다.
  • 2단계: 삽입 Case 2/3(Uncle=Black): Uncle이 검정이면 회전이 필요. Case 2(삽입점이 지그재그)는 부모 회전으로 Case 3으로 변환, Case 3는 할아버지 회전과 재채색으로 해소하는 최대 3회전 보장을 뜯어봅니다.
• Implement: 파이썬 RedBlackTree 완전 구현(또는 C++ std::map 내부 원리 분석). 임의 입력 100개 삽입 후 check_rb_properties() 함수로 5가지 속성 모두 만족 여부 자동 검증. height(tree) <= 2 * log₂(n+1) 임을 수치로 증명.

Advanced

Core Topic 04: 모리스 순회와 메모리 절약, O(1) 공간 트리 순회 (Morris Traversal)

• Why to Learn: 트리 순회 시 일반 재귀가 O(h) 스택 공간을 쓰는 한계를 부수고, 트리의 NULL 포인터(Threaded Tree)를 임시 링크로 활용하여 추가 공간 없이 O(n) 시간 + O(1) 공간으로 순회하는 임베디드/메모리 제약 환경의 필수 기법을 장악하기 위해서입니다.
• What to Learn:
  • Concepts: Morris In-order Traversal, 스레드 트리(Threaded Tree), 선행자(In-order Predecessor) 연결/복구.
  • Skills: NULL 포인터를 임시 링크로 재활용하는 상태 머신(State Machine) 관리.
  • Tools: 메모리 제약 임베디드 환경 트리 처리.
• How to Learn:
  • 1단계: 현재 노드 cur의 In-order 선행자(왼쪽 서브트리의 최우단 노드)를 찾습니다. 선행자의 right == NULL이면 right = cur로 임시 링크를 걸고 cur = cur.left 이동. right == cur이면 이미 방문했다는 신호이므로 링크를 복구(right = NULL)하고 현재 노드를 출력 후 cur = cur.right 이동하는 Morris In-order 상태 머신을 해부합니다.
  • 2단계: 원본 트리가 완전히 복구(링크 원상 복귀)되어 Morris 순회 후 트리 구조가 변하지 않음을 증명합니다.
• Implement: 파이썬 morris_inorder(root) 함수. 100개 노드 BST에 대해 Morris 순회 결과가 일반 재귀 In-order와 동일함을 assert로 검증. tracemalloc으로 두 방법의 메모리 사용량 비교: Morris는 스택 프레임 없이 O(1) 추가 메모리임을 수치로 증명.

7. Terminology

8. References

Primary

• [P2] SWEBOK v4.0 - Software Engineering Foundations / Data Structures (Non-linear) — Tree structures.
• [P1] CS2023 - AL/Fundamental Data Structures (Non-linear) — Core requirements.

Secondary

• [Introduction to Algorithms (CLRS)] Cormen — AVL and Red-Black proofs.
• [Algorithms] Robert Sedgewick — Left-Leaning Red-Black Trees (LLRB).

Industry

• [Oracle: Java TreeMap Implementation] — Real-world RB Tree case.
• [GNU C++ Library: stl_tree.h] — Industry standard tree implementation.

9. Final Checklist

Primary

• '이진 탐색 트리(BST)'에서 왼쪽 자식 노드보다 큰 값을 가진 노드가 부모가 될 수 없는 이유를 설명 가능한가? (P1)
• 트리의 균형이 깨져 '편향 트리(Skewed Tree)'가 될 때의 시간 복잡도 변화($O(\log n) \to O(n)$)를 입증할 수 있는 가? (P1)

Secondary

• AVL 트리의 '높이 균형'이 왜 $O(\log n)$ 검색을 보장하는 물리적 근거가 되는지 수리적으로 소통 가능한가?
• Red-Black 트리의 삽입 시, 'Neighboring Nodes'의 색상이 왜 물리적 회전 여부를 결정짓는지 도출할 수 있는 가?

Industry

• 리눅스 커널의 VMA(가상 메모리 영역) 관리에 왜 Red-Black 트리가 물리적으로 채택되었는지 그 효율성을 분석할 수 있는 가? (SFIA)
• 대용량 맵(Map) 자료구조 설계 시, AVL의 읽기 속도와 Red-Black의 쓰기 안정성 중 서비스 성격에 맞는 구조를 제안할 수 있는 가?