추가. Red-black 트리 (레드블랙트리)

레드-블랙 트리

개요

자가 균형 이진 탐색 트리. 다음과 같은 조건을 만족.

1. 모든 노드는 빨간색 혹은 검은색.
2. 루트 노드는 검은색.
3. 모든 리프 노드(NIL)는 검은색.
4. 빨간색 노드의 자식은 검은색. (No Double Red)
5. 모든 리프 노드에서 Black Depth는 같음.

---

삽입 과정

1. 새로운 노드는 항상 빨간색으로 삽입.
2. 삽입 후 Double Red 문제 발생 가능.
3. 해결 방법:
   • 삼촌 노드가 검은색: Restructuring 수행.
   • 삼촌 노드가 빨간색: Recoloring 수행.

---

Restructuring (재구축)

1. 새로운 노드(N), 부모 노드(P), 조상 노드(G)를 오름차순으로 정렬.
2. 중간값을 부모 노드로 설정, 나머지 둘을 자식 노드로 변경.
3. 새 부모 노드를 검은색으로, 자식들을 빨간색으로 변경.

예제

초기 상태:        재구축 후:
    G (검)           P (검)
   / \              /   \
  P  U(검)        N(빨) G(빨)
 /
N(빨)

---

Recoloring (재색칠)

1. 부모(P)와 삼촌(U)을 검은색으로 변경.
2. 조상(G)을 빨간색으로 변경.
3. 조상이 루트라면 검은색으로 유지.
4. 조상이 Double Red를 유발하면 다시 Restructuring 또는 Recoloring 수행.

예제

초기 상태:        재색칠 후:
    G (검)          G (빨)
   / \            /   \
  P(빨) U(빨)    P(검) U(검)
 /
N(빨)

---

예제 삽입 수행

삽입 순서: 8, 7, 9, 3, 6, 4, 5, 12

초기 상태:       최종 상태:
      8(검)          6(검)
     /   \         /     \
   4(빨)  9(검)  3(검)   8(검)
  /   \         /   \      \
 3(검) 6(검)   NIL 5(빨)  12(검)
        /
      5(빨)

---

레드-블랙 트리 시뮬레이터

레드-블랙 트리의 삽입 과정을 시각적으로 확인 가능.

🔗 레드-블랙 트리 시뮬레이터