참고 https://zeddios.tistory.com/237

Red-Black Tree

Red-Black Tree는 Binary Search Tree의 균형잡힌 버전이다.

이진 탐색 트리에서 계속 부모보다 큰 값이 들어올 경우 다음 그림과 같이 한쪽으로 편향된 트리가 나올 수 있고, 따라서 O(h)만큼의 탐색시간이 소요될 수도 있다.

그래서 레드블랙트리의 조건에 따라 균형잡힌 이진 탐색 트리가 생성되고, 높이는 logn에 바운드 되기 때문에 search 연산은 O(logn)의 시간 복잡도를 가지게 된다.

현재 고안된 이진 탐색 트리 중 성능이 가장 좋다.

조건

1. 모든 노드는 red 또는 black 이다.
2. 루트 노트는 black 이다.
3. 모든 leaf(null leaf)는 블랙이다.
4. 노드가 red면 자식은 black이다. (no double red)
5. 각 노드에 대해 노드에서 하위 리프까지의 모든 경로에는 동일한 수의 검은 색 노드가 포함된다.

값을 추가하다 보면 다음과 같이 4번에 해당되는 double red 상황이 발생한다.

이를 해결해주기 위해

1. restructuring
2. recoloring

중에 하나의 전략을 사용한다.

w가 검정이면 restructuring,
w가 빨강이면 recoloring이 일어난다.

restructuring은 다음과 같이 일어난다.

Recoloring은 다음과 같이 일어난다.