WEEK05

레드 블랙 트리 (RB-Tree)

기존의 이진 트리 속성에서 색(레드, 블랙)이라는 속성을 추가하여
최악의 상황이라도 O(logN)을 유지.

숫자 등의 비교 가능한 자료를 정리하는 데 쓰이는 자료 구조

어떤 노드에 자식이 없다면 그 노드를 리프 노드라고 부른다.

모든 노드에 대해서 오른쪽에 위치한 부분트리가 가지고 있는 모든 자료보다 작거나 같고,
자신보다 왼쪽에 위치한 부분트리가 가지고 있는 모든 자료보다 크거나 같다 라는 조건을 만족.

• 원칙

1. 노드는 레드 혹은 블랙 중의 하나이다.
2. 루트 노드는 블랙이다.
3. NIL은 블랙이다.
4. 레드 노드의 자식노드 양쪽은 언제나 모두 블랙이다. (즉, 레드 노드는 연달아 나타날 수 없으며, 블랙 노드만이 레드 노드의 부모 노드가 될 수 있다)
5. 어떤 노드에서 리프노드까지 도달하는 과정에서 거쳐간 블랙노드의 수는 항상 같다. (자기 자신은 포함하지 않는다.)

h = 트리의 높이
bh = 리프 노드까지 가는 동안의 블랙의 개수.

참고 : https://ferrante.tistory.com/46