레드-블랙 트리

1. 개요[편집]

---

레드-블랙 트리는 자가 균형 이진 탐색 트리의 일종이다.

2. 특성[편집]

---

레드-블랙 트리의 각 노드는 레드 또는 블랙의 색상을 가지고 있다. 구현의 용이성을 위해, 모든 노드는 자식이 없는 부분에 NIL이라는 가상적인 노드를 자식으로 갖는다고 가정한다. NIL은 블랙이다.
이진 탐색 트리에 다음의 조건을 추가하면 레드-블랙 트리가 된다.

1. 노드는 레드 또는 블랙이다.
2. 루트 노드는 블랙이다.
3. 모든 리프 노드는 블랙이다.
4. 레드 노드의 자식은 모두 블랙이다. (루트로부터 리프 노드까지의 경로에 레드 노드가 연이어 올 수 없다.)
5. 어떤 노드에서 리프 노드까지의 모든 경로에는 같은 수의 블랙 노드가 있다.

위 조건으로부터, 루트로부터 가장 긴 경로가 가장 짧은 경로의 길이의 두 배를 넘지 않는다. 이를 개략적으로 균형이 잡혀 있다(roughly balanced)고 한다.

3. 시간 복잡도[편집]

---

삽입, 탐색, 삭제 모두 최악의 경우 O(log n)의 시간 복잡도를 갖는다.
기존 이진탐색트리에서 삽입과 삭제에서 최악의 경우 O(n)의 시간 복잡도를 갖는것을 보완하기 위해 AVL트리가 만들어지고,
그 AVL트리를 더 보완하기 위해 레드-블랙트리가 개발되었다.

4. 삽입[편집]

---

일반적인 이진 탐색 트리에 삽입하는 것처럼 한 후, 새 노드(N)을 레드로 칠한다.
이때 4가지 경우로 나뉜다.

1. N이 루트 노드이다.
2. N의 부모 노드(P)가 블랙이다.
3. P가 레드이고 N의 삼촌(U)이 레드이다.
4. P가 레드이고 U가 블랙이다.

4.1. 경우 1[편집]

---

N이 루트 노드인 경우이다.
조건 2[A]를 만족시키기 위해 N을 검은색으로 칠한다.
N이 루트 노드이므로 루트로부터 리프 노드까지의 모든 경로에 블랙 노드가 하나 추가되어, 조건 5[B]는 위반되지 않는다.

4.2. 경우 2[편집]

---

P가 블랙인 경우이다.
이때 트리는 모든 조건을 만족한다.

4.3. 경우 3[편집]

---

P가 레드이고 U가 레드인 경우이다.

4.4. 경우 4[편집]

---

P가 레드이고 U가 블랙인 경우이다.

5. 삭제[편집]

---