> For the complete documentation index, see [llms.txt](https://byulseop-til.gitbook.io/sinheeseop_til/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://byulseop-til.gitbook.io/sinheeseop_til/cs-computer-science/datastructure/03_structure/tree/advancedtree_overview.md).

# AdvancedTree\_Overview

> **이 문서는 고급 트리들의 "간략 정리판"이다.**\
> 각 트리의 상세 내용(구현, 회전 연산 등)은 개별 문서로 분리 예정.

기본적인 이진 탐색 트리(BST)의 한계(편향성 등)를 극복하거나, 특정 목적(DB 인덱스, 문자열 검색)에 최적화된 고급 트리 구조들을 정리한다.

## 1. 자가 균형 이진 탐색 트리 (Self-Balancing BST)

일반적인 BST는 데이터가 정렬되어 들어오면 한쪽으로 쏠려서(Skewed) 검색 성능이 O(n)으로 떨어지는 치명적인 단점이 있다. 이를 해결하기 위해 **스스로 균형을 맞추는** 트리들이다. (항상 O(log n) 보장)

### 1) AVL 트리 (Adelson-Velsky and Landis)

* **특징** : 균형을 **매우 엄격하게** 맞춘다. (좌우 높이 차이가 1을 넘지 않음)
* **장점** : 조회가 매우 빠르다. (가장 균형 잡혀 있으니까)
* **단점** : 삽입/삭제 시 균형을 맞추기 위한 회전(Rotation) 연산이 자주 발생하여 느리다.
* **사용처 (Where)** : **데이터 변경이 거의 없고 검색만 주구장창 하는 시스템**
  * 예: 우편번호 검색 시스템, 사전 데이터베이스

### 2) 레드-블랙 트리 (Red-Black Tree)

* **특징** : AVL보다 **느슨하게** 균형을 맞춘다. (특정 규칙인 '색상'을 통해 관리)
* **장점** : AVL보다 검색은 약간 느리지만, **삽입/삭제가 훨씬 빠르다.** (회전을 덜 하니까)
* **사용처 (Where & Why)**
  * **Java Collection (`TreeMap`, `TreeSet`)** : 데이터의 삽입/삭제와 검색 빈도가 비슷하게 일어나는 범용적인 상황에서 가장 균형 잡힌 성능을 제공하기 때문.
  * **Java `HashMap` (Java 8+)** : 해시 충돌(Collision)이 발생하여 하나의 버킷에 데이터가 많이 쌓이면, 연결 리스트 대신 레드-블랙 트리를 사용하여 검색 성능을 O(n)에서 O(log n)으로 방어한다.
  * **Linux 커널 스케줄러 (CFS)** : 실행 중인 프로세스들을 관리할 때, 공정한 CPU 시간 분배를 위해 사용된다.

## 2. 다중 트리 (Multi-way Tree)

노드 하나에 데이터가 1개가 아니라 **여러 개** 들어갈 수 있고, 자식도 2개보다 많이 가질 수 있는 트리다.

### 1) 2-3-4 트리

* **특징** : 모든 리프 노드가 같은 깊이에 있다. (완벽한 균형)
* **의의** : 레드-블랙 트리의 이론적 모태가 되는 트리다. (4-노드를 쪼개면 레드-블랙 트리가 됨)

### 2) B-Tree (B-트리)

* **특징** : **"디스크 I/O를 줄이자"** 는 목적에서 탄생했다. 하나의 노드에 많은 데이터를 꽉꽉 눌러 담는다. (Block 단위 저장)
* **사용처 (Where & Why)**
  * **파일 시스템 (File System)** : 하드 디스크는 블록(Block) 단위로 데이터를 읽는다. B-Tree 노드 크기를 디스크 블록 크기와 일치시키면, 한 번의 I/O로 최대한 많은 정보를 읽어올 수 있어 효율적이다.
  * **구형 DB 인덱스** : 데이터 자체를 인덱스와 함께 저장해야 할 때 유리하다.

### 3) B+Tree (B+트리)

* **특징** : B-Tree의 개량형. **데이터는 오직 리프 노드에만 저장** 하고, 리프 노드끼리는 **연결 리스트** 로 연결된다.
* **사용처 (Where & Why)**
  * **현대 RDBMS 인덱스 (MySQL InnoDB 등)** :
    1. **범위 검색(Range Scan)** : `SELECT * FROM table WHERE age BETWEEN 20 AND 30` 같은 쿼리 시, 리프 노드에서 시작해 옆으로 쭉 훑으면 되므로 엄청나게 빠르다.
    2. **트리 높이 감소** : 내부 노드에는 키(Key)만 저장하므로, 한 노드에 더 많은 자식 포인터를 담을 수 있어 트리가 납작해진다. (디스크 접근 횟수 감소)

## 3. 특수 목적 트리

### 1) Trie (트라이 / 접두사 트리)

* **목적** : **문자열 검색** 최적화.
* **사용처 (Where & Why)**
  * **검색어 자동 완성** : "Ap"를 입력했을 때 "Apple", "App" 등을 빠르게 찾을 수 있다. 접두사(Prefix)를 공유하므로 공통된 글자를 따라가기만 하면 된다.
  * **IP 라우팅 테이블** : 가장 긴 접두사 일치(Longest Prefix Match)를 찾을 때 사용한다.

### 2) Heap (힙 / 완전 이진 트리)

* **목적** : **최대값/최소값** 을 O(1)에 찾아내기 위함.
* **사용처 (Where & Why)**
  * **우선순위 큐 (Priority Queue)** : "가장 급한 작업부터 처리해" 같은 로직 구현 시 필수.
  * **OS 작업 스케줄링** : 시스템 부하가 높을 때 우선순위가 높은 프로세스를 먼저 CPU에 할당하기 위해 사용.
  * **다익스트라 알고리즘** : 최단 경로 탐색 시 가장 가까운 노드를 반복적으로 선택할 때 사용.

## 4. 한눈에 비교하기

| 트리 종류              | 핵심 키워드           | 주요 용도                     |
| ------------------ | ---------------- | ------------------------- |
| **AVL Tree**       | 엄격한 균형           | 읽기 위주 데이터베이스              |
| **Red-Black Tree** | 범용성, 빠른 수정       | Java Collection, Linux 커널 |
| **B-Tree**         | 디스크 블록 최적화       | 파일 시스템                    |
| **B+Tree**         | **범위 검색**, 리프 연결 | **DB 인덱스 (MySQL)**        |
| **Trie**           | 접두사 공유           | 검색어 자동 완성                 |