Binary Trees & AVL-Red-Black

1. Overview

이진 트리 및 AVL-Red-Black(Binary Trees & AVL-Red-Black, BTB)은 선형적인 나열을 넘어 '계층'을 통해 정보의 바다에서 원하는 데이터를 번개처럼 찾아내는 시스템의 '지능형 지도'입니다.

단순한 리스트는 데이터를 찾기 위해 끝까지 가야 할 수 있습니다. 학습자는 하나의 부모가 최대 두 개의 자식을 갖는 **이진 트리(Binary Tree)**의 물리 구조를 배웁니다. 특히, 한쪽으로 쏠린 트리가 리스트로 전락하는 것을 막기 위해 스스로 회전(Rotation)하고 색깔(Color)을 칠하며 균형을 유지하는 AVL 트리와 Red-Black 트리의 고차원 수리 논리를 익힙니다. 이를 통해 어떤 데이터가 들어오더라도 $O(\log n)$이라는 안정적인 검색 성능을 물리적으로 보장하는 설계 능력을 확보합니다.

2. Scope & Boundaries

In-Scope

• Binary Tree Structures: 완전(Complete), 포화(Full), 편향(Skewed) 트리의 물리 배치 차이
• Binary Search Tree (BST): 왼쪽은 작고 오른쪽은 큰 수리적 정렬 유지 규칙
• Self-Balancing Physics: AVL의 높이 균형 인수(Factor)와 Red-Black의 색상 기반 불변성 규칙
• Tree Traversals: 전위, 중위, 후위 및 레벨 순회(BFS)의 물리적 실행 경로

Out-of-Scope

• B-트리 및 B+트리와 같은 외부 저장소용 다원 트리 (04-02-XX 데이터베이스 영역으로 위임 가능하나 여기서는 기초 원리만)
• 허프만 코딩 등 응용 알고리즘 (04-04-02 노드에서 분담)

Boundaries

• BTB vs. Heaps: BTB가 '정렬된 검색'에 집중한다면, 힙(04-02-02)은 '최댓값/최솟값 즉시 추출'이라는 특수 목적에 집중하여 구분합니다.

3. Counterexample

• 단순히 "그림으로 그리는 트리"는 BTB 학습이 아닙니다. 왜 AVL 트리가 Red-Black 트리보다 읽기 작업에서 유리하고, Red-Black 트리가 삽입/삭제가 빈번한 환경에서 물리적으로 더 선호되는지 '회전 횟수'의 엄격한 상한선을 근거로 증명할 수 있어야 합니다. 또한, 균형을 맞추지 않은 BST가 최악의 경우 왜 배열과 다를 바 없는 **$O(n)$**으로 퇴화(Degeneracy)하는지 수리적으로 설명하지 못한다면 BTB의 존재 이유를 이해하지 못한 것입니다.

4. Prerequisites

• Linked Lists & Pointer Logic (Basic): 주소 연결과 노드 구조 이해가 필수입니다. (04-01-02 LPL)
• Recursion & Divide-and-Conquer (Recommended): 트리 탐색의 논리 기초 이해가 권장됩니다. (04-03-01 RDC)

5. Learning Map

1. The Branching Logic: 하나의 데이터가 두 갈래 길을 결정짓는 이진 분류의 물리를 배웁니다.
2. Search Efficiency: 트리의 깊이(Height)가 곧 검색 시간이 되는 수리적 관계를 인식합니다.
3. The Rotation Dance: 쏠린 쪽을 들어 올리고 반대쪽을 내리는 물리적 균형 복구 기술을 익힙니다.
4. Stable Hierarchy: 데이터의 파도 속에서도 중심을 잃지 않는 Red-Black 시스템을 완성합니다.

6. Learning Topics

Basic

Core: 이진 트리의 구조와 BST (Tree Fundamentals)

• Why to Learn: 데이터를 정렬된 상태로 유지하면서도 배열보다 빠르게 삽입/삭제하기 위해서입니다.
• What to Learn:
  • Root, Leaf, Internal Nodes: 트리를 구성하는 물리적 계급과 역할
  • BST Property: 왼쪽 자식 < 부모 < 오른쪽 자식의 수리적 수평 유지
  • Searching Physics: 루트에서 시작해 절반씩 후보를 제거하는 여정
• How to Learn:
  • 수동으로 10개의 무작위 숫자를 BST에 삽입하며 트리의 모양이 어떻게 변하는지 종이에 기록 실습
  • 중위 순회(In-order Traversal)를 수행했을 때 데이터가 왜 자동으로 정렬되어 나오는지 물리적 증명
• Implement: 데이터의 삽입, 삭제, 검색 기능을 가진 기본 Binary Search Tree

Recommended

Core: AVL 트리의 엄격한 균형 (Height Balancing)

• Why to Learn: 트리의 높이를 항상 $\log n$으로 묶어두어 지연 시간의 상한을 물리적으로 고정하기 위함입니다.
• What to Learn:
  • Balance Factor (BF): 왼쪽과 오른쪽 하위 트리의 높이 차이 계산
  • Single/Double Rotation: $LL, RR, LR, RL$ 불균형 상황에 따른 물리적 회전 알고리즘
  • Rebalancing 시점: 삽입/삭제 후 루트까지 다시 올라가며 균형을 검사하는 연鎖(Chain) 과정
• How to Learn:
  • 특정 노드 삽입 시 BF가 2가 되는 지점을 찾고, 회전을 통해 다시 0이나 1로 돌아오는 과정을 단계별 시각화 실습
  • AVL 트리의 높이가 $n$개 노드일 때 왜 항상 $1.44 \log n$을 넘지 않는지 상한선 분석
• Implement: 자체적으로 높이를 계산하고 회전을 수행하는 자가 균형 AVL 클래스

Practical

Core: Red-Black 트리의 실용적 균형 (Color Constraints)

• Why to Learn: AVL보다 회전 횟수가 적어 현대의 수많은 언어 라이브러리(Java TreeMap, C++ map)의 표준 물리 엔진으로 쓰이기 때문입니다.
• What to Learn:
  • RB Rules: Root Black, Leaf Black, Red cannot have Red child 등 5가지 불변성
  • Recoloring vs Rotation: 단순 색칠로 끝낼 것인가, 물리적 위치를 바꿀 것인가의 판단 기준
  • Black Height: 모든 경로의 검은 노드 수가 같아야 한다는 물리적 균형의 실체
• How to Learn:
  • 복잡한 삽입 상황(Uncle is Red/Black)에 따른 대응 케이스를 표로 정리하고 암기 없이 유도 실습
  • Red-Black 트리가 AVL보다 '조금 덜 균형적'이지만 왜 전체 성능은 더 잘 나올 수 있는지 트레이드-오프 연구
• Implement: Red-Black 트리의 노드 구조와 기본 삽입(Insert Fixup) 로직

Advanced

Core: 트리 기반 공간 분할과 최적화 (Advanced Trees)

• Why to Learn: 텍스트, 이미지, 지도 데이터 등 특수 형태의 데이터를 물리적으로 빠르게 처리하기 위해서입니다.
• What to Learn:
  • Segment Tree: 특정 범위의 합이나 최솟값을 $O(\log n)$에 구하는 구간 물리학
  • Cartesian Tree: 중위 순회 결과와 힙(Heap) 특성을 동시에 만족하는 하이브리드 구조
  • Cache-aware Trees: 메모리 페이지 단위에 맞춰 노드 크기를 조절하는 하드웨어 친화적 설계
• How to Learn:
  • 세그먼트 트리를 이용해 수백만 번의 범위 쿼리를 처리할 때의 성능 이점 측정 실습
  • 트리의 노드를 포인터가 아닌 배열(Implicit Tree)로 관리할 때의 캐시 지역성 변화 분석
• Implement: 대규모 데이터셋에 대한 범위 합(Range Sum)을 빠르게 구하는 세그먼트 트리

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의 쓰기 안정성 중 서비스 성격에 맞는 구조를 제안할 수 있는 가?