9. Advanced..

Advanced Tree

데이터의 삽입, 삭제, 탐색 연산을 O(log n) 시간 안에 수행하도록 균형을 유지하는 것이 핵심

---

1. Red-Black Tree

이진 탐색 트리(BST)의 한 종류로, 트리의 높이를 균형 있게 유지하기 위해 노드에 색깔 정보(빨강/검정) 를 추가한 구조

즉, 삽입이나 삭제 시 트리가 한쪽으로 치우치지 않게 색깔 변경과 회전(rotation) 을 수행해 항상 log n 높이를 보장함

장점	단점
트리의 균형을 유지하므로 항상 빠른 검색 성능 보장 삽입, 삭제 시 회전이 많지 않아 AVL보다 구현이 단순	완전한 균형은 아니므로 AVL보다 탐색은 약간 느릴 수 있음

 

 - Red-Black Tree의 규칙

모든 노드는 red 또는 black 색을 가진다.
다음의 다섯 가지 성질을 항상 만족해야 한다.

1. 각 노드는 빨강 또는 검정이다.
2. 루트 노드는 항상 검정이다.
3. 모든 리프(NIL) 노드는 검정이다.
4. 빨강 노드의 자식은 반드시 검정이다.
   → 즉, 빨강 노드는 연속으로 나올 수 없다.
5. 임의의 노드에서 리프까지 가는 모든 경로에는 동일한 수의 검정 노드가 있다.
   → 이를 “black-height”라고 한다.

이 규칙들을 통해 트리의 높이는

2 * log2(n + 1) 이하로 제한되어, 균형이 보장된다.

 

 - Insertion

1. 일단 BST 규칙에 따라 삽입
   → 새 노드는 항상 빨강(red) 으로 삽입된다.
2. Red-Black 속성 위반 검사
   삽입 후, 위의 다섯 규칙 중 위반된 것이 있으면 수정한다.
3. 색 변환 & 회전 수행
   • Case 1: 삽입된 노드의 삼촌이 빨강 → 부모·삼촌을 검정, 할아버지를 빨강으로 바꿈
   • Case 2: 삼촌이 검정이고, 삽입된 노드가 오른쪽 자식 → 왼쪽 회전
   • Case 3: 삼촌이 검정이고, 삽입된 노드가 왼쪽 자식 → 오른쪽 회전

→ 회전(rotation)을 통해 트리의 균형을 유지한다.

 

 - Deletion

1. BST 삭제 규칙으로 우선 노드를 삭제.
2. 삭제로 인해 Red-Black 속성이 깨질 수 있으므로,
   “double black” 상태를 해결하기 위해 색상 변경, 형제 노드 색상 검사, 회전을 수행한다.

 - 시간 복잡도

탐색, 삽입, 삭제 모두 O(log n)

 

- 활용 예시

• Linux 커널의 프로세스 관리 (CFS Scheduler)
• C++ STL의 std::map, std::set
• Java의 TreeMap, TreeSet

---

2. B-Tree

B-Tree는 이진 트리의 일반화 버전으로, 하나의 노드가 여러 개의 키(key)와 자식(child)을 가질 수 있다.

디스크 접근(입출력)이 많은 환경(예: 데이터베이스, 파일시스템)에서

탐색 효율을 극대화하기 위해 설계된 균형 다진 탐색 트리 (Balanced m-ary Search Tree)

장점	단점
디스크 접근 횟수 최소화 (I/O 효율적) 높이가 매우 낮음, 대용량 데이터에 적합 균형 자동 유지	각 노드가 커서 메모리 관리가 복잡 단순한 메모리 내 탐색에는 오히려 비효율적

 

- 구조

B-Tree의 차수(degree) = 한 노드가 가질 수 있는 최대 자식 수 (m)

• 각 노드는 최대 m개의 자식, m−1개의 키를 가질 수 있음
• 모든 리프 노드는 같은 깊이에 존재
• 루트 노드는 최소 2개 이상 자식을 가질 수 있음 (특수 경우 제외)
• 노드의 키들은 항상 오름차순 정렬되어 있음

 

 - Search

1. 현재 노드의 키를 이진 탐색으로 탐색
2. 키가 존재하면 반환, 없으면 해당 구간의 자식 노드로 이동
3. 리프에 도달할 때까지 반복

→ 시간복잡도: O(logₘ n) (트리의 높이가 매우 낮음)

 

- Insertion

1. 새로운 키를 삽입할 리프 노드를 찾음.
2. 해당 노드가 꽉 차 있지 않으면 바로 삽입.
3. 꽉 차 있다면 노드 분할(split) 발생
   • 중간 키를 부모로 올리고
   • 왼쪽/오른쪽 노드로 나누어 저장
4. 부모도 꽉 차 있으면 위로 계속 분할을 전파

→ 루트가 분할될 수도 있다 (트리의 높이가 1 증가)

 

- Deletion

1. 삭제할 키가 리프 노드에 있으면 바로 삭제
2. 내부 노드에 있으면,
   → 전임자(predecessor) 혹은 **후임자(successor)**로 교체
3. 삭제 후, 최소 키 수 조건을 위반하면
   → 병합(merge) 또는 재분배(redistribute) 수행

 

 

- 활용 예시

• 데이터베이스 인덱스 (MySQL, PostgreSQL 등)
• 파일 시스템 (NTFS, HFS+, EXT4)

---

Red-Black Tree vs B-Tree 비교

항목	Red-Black Tree	B-Tree
구조	이진 탐색 트리	다진 탐색 트리 (m-ary)
균형 유지	색상 + 회전으로 유지	노드 분할·병합으로 유지
목적	메모리 내 효율적 탐색	디스크 기반 I/O 최소화
높이	약 log₂n	약 logₘn (더 낮음)
삽입/삭제	회전 필요 (빠름)	분할/병합 필요 (느림)
사용 예	STL map, TreeSet	DB 인덱스, 파일시스템