📌 Red-Black-Tree

각 노드가 레드, 블랙의 색상 속성을 가지고 있는 이진 트리이다.

스스로 균형을 잡는 트리이기 때문에 BST의 불균형 이진트리 단점을 개선할 수 있고,
이러한 특성 때문에 자가 균형 이진 탐색 트리라고도 한다.

➡️ O(n) -> O(log n)
레드-블랙 트리는 최악의 경우에도 삽입/삭제/탐색 = O(log n)을 보장한다.

• 이때 이진탐색트리처럼 왼쪽 서브트리는 부모노드 보다 작은 값들을
• 오른쪽 서브트리는 부모노드보다 큰 값들을 보장하지만
• 리프노드들은 자료를 가지고 있지 않은 즉, 비어있는 상태이다.

🔲 Red-Black-Tree 조건

1. 모든 노드는 레드 혹은 블랙 중의 하나의 특성을 가진다.
2. 루트 노드는 항상 블랙이다.
3. 모든 리프 노드들(NULL LEAF)은 블랙이다.
4. 레드 노드의 모든 자식 노드들은 언제나 블랙이기 때문에 레드 노드는 연속할 수 없다.
5. 어떤 노드로부터 시작해서 그에 속한 하위 리프 노드에 도달하는 모든 경로에는 리프 노드를 제외하면 모두 같은 개수의 블랙 노드가 있다.

💭 조건 살펴보기

3️⃣ 모든 리프 노드들(NULL LEAF)은 블랙이다.

🍃 nil node

아무 데이터도 갖고 있지 않음을 나타내는 특수한 "검정색"노드이고
이 노드는 자식노드가 존재하지 않는 경우를 표시하기 위해 사용한다.

즉, RBT에서 모든 끝 노드(자식 노드가 존재하지 않는)들은 Nil node이며
이로 인해서 RBT 3번 조건이 성립한다.

---

4️⃣ 레드 노드의 모든 자식 노드들은 언제나 블랙이기 때문에 레드 노드는 연속할 수 없다.

---

5️⃣ 임의의 노드에서 자손인 nil 노드들에 도달하는 모든 경로에는 모두 같은 개수의 블랙 노드가 있다(자기자신은 카운트에서 제외).

✔️ Case 1 (왼쪽 트리 그림)

임의의 선택된 노드 : 70
해당 노드에서 시작해서 도달할 수 있는 모든 nil 노드에 대해서 블랙노드를 2개씩 가지고 있다.

✔️ Case 2 (오른쪽 트리 그림)

임의의 선택된 노드 : 40
해당 노드에서 시작해서 도달할 수 있는 모든 nil 노드에 대해서 블랙 노드를 1개씩 가지고 있다.

💡 point

5번 규칙에서 자기 자신은 카운트에서 제외하기 때문에
Case 1, Case 2 처럼 임의의 시작 노드가 블랙 노드, 레드 노드인 것은 이 규칙에서 영향을 끼치지 못한다.

⚫️ Black-height

위에서 계산했던 것 처럼 임의의 시작 노드에서 도달할 수 있는
nil 노드까지의 경로에서 포함되는 black_node 의 개수를 의미한다.
"bh(x) = 노드 x를 제외하고 x의 어떤 자손 NIL까지 가는 경로에 존재하는 블랙 노드의 개수(=모든 경로 동일). NIL은 블랙으로 계산한다.”

➡️ 이 개념이 성립하려면 5번 규칙이 선행되어야 한다.

• 5번 규칙이 선행되지 않으면 임의의 시작 노드에 대해 nil 노드별로
  Black-height가 일정하지 않기 때문에 의미가 없다.

⁉️ Red-Black-Tree 특성

⭐️ 중요한 특성

루트 노드부터 가장 먼 잎노드 경로까지의 거리 < 가장 가까운 잎노드 경로까지의 거리 * 2

☑️ 최단, 최장 경로

1. 레드-블랙 트리에서 "최단 경로"와 "최장 경로"의 의미

✔️ 최단 경로
루트 노드부터 어떤 리프(NIL) 노드까지 가는 가장 짧은 경로를 말한다.
레드 노드를 추가하면 경로가 길어지기 때문에 "모든 노드가 블랙"인 경우가 최단입니다.
(이 경우가 가능한 최단 거리라는 것이지 실제 트리의 최단 경로에 레드가 포함되면 안된다는 말은 아니다.)

✔️ 최장 경로
루트 노드부터 리프(NIL)까지 가는 가장 긴 경로를 말한다.
네 번째 속성(레드 노드가 연속 불가) 때문에,
최장 경로는 블랙과 레드가 번갈아 나오는 경로가 됩니다.

☑️ 거리의 한계

2. 왜 두 배보다 길 수 없는지

• 다섯 번째 속성으로 인해서 모든 경로의 블랙 노드 개수는 동일하다는 것을 알았다.
  즉, 최단 경로는 블랙 노드만 → 블랙 개수 = bh (black height) 라고 하자

• 최장 경로는 네 번째 속성에 의해 각 블랙 노드 사이에 레드 노드를 하나씩 끼운 경우인데
  그렇다면 레드 노드는 -> 레드 개수 = (최대 bh개 - 1)가 될 수 밖에 없다.
  ➡️ R ≤ B