Red-black tree

이 트리는 이진 탐색 트리의 일종으로, 트리의 균형을 유지하기 위해서 노드에 색상을 부여하고, 필수로 준수해야 하는 규칙을 추가한 트리다. 실제 라이브러리 코드에서 레드블랙트리를 사용하는 언어는 다음과 같다.

• C++ : set, map
• Java : TreeMap, TreeSet
• C# : SortedSet, SortedDictionary
  

Properties

---

다음과 같은 조건이 무조건 성립해야 한다.

1. 모든 노드는 red, 혹은 black의 속성을 가진다.
2. root 노드는 black이다.
3. red 노드는 red노드를 자식으로 가질 수 없다. 따라서 red노드의 자식은 무조건 black이다.
4. 노드 하나를 골랐을 때, 그 노드의 밑에 있는 모든 leaf노드로 가기 위해서는 모두 같은 수의 black노드를 거쳐야 한다.
5. 모든 NIL 노드는 black이다.

이러한 속성을 만족한다 했을 때, root -> leaf 로 가는 경로를 보면

• 가장 짧은 길이를 $N$ 이라고 하자. 이 경로는 black노드로만 이루어져 있을 것이다.
• 가장 긴 경로는 법칙 4번에 의해서 black, red, black, red . . . 의 경로를 거쳐야 하며, 이 때 black의 개수는 $N$개이므로 전체 길이는 $(2N-1)$ 이다.

따라서 가장 긴 경로가 가장 짧은 경로의 2배 이상이 될 수 없어. 트리의 과한 불균형을 막을 수 있다.