레드 블랙 트리(Red Black Tree)란?

자가 균형 이진 탐색 트리로서, 트리에 N개의 원소가 있을 때, O(logN)의 시간 복잡도로 삽입, 삭제, 검색을 할 수

있는 자료 구조를 의미합니다. 함수형 프로그래밍에서 쓰이는 연관 배열이나 집합 등을 레드 블랙 트리로 구현해

놓은 경우가 많습니다.

레드 블랙 트리의 특징

---

이진 탐색 트리의 경우, 최악의 경우 트리의 높이만큼의 검색 시간이 소요됩니다. 하지만 레드 블랙 트리에서는

특정 조건을 바탕으로 스스로 균형 잡힌 트리를 유지함으로써 항상 O(logN)의 시간복잡도를 갖습니다.

이때, 조건이란 아래와 같습니다.

1. 노드의 색깔은 레드 혹은 블랙 중의 하나이다.
2. 루트 노드의 색깔은 항상 블랙이다.
3. 레드 노드의 자식 노드의 색깔은 항상 블랙이다.
4. 모든 리프 노드의 색깔은 항상 블랙이다.
5. 특정 노드에서 그에 속한 하위 리프 노드에 도달하는 모든 경로에는 같은 수의 블랙 노드가 있다.

그리고 이 조건을 충족하기 위해 Restructing, Recoloring 두 가지 전략이 필요합니다.

Restructing

1. 나(z)와 내 부모(v), 내 부모의 부모(Grand Parent)를 오름차순으로 정렬
2. 무조건 가운데 있는 값을 부모로 만들고 나머지 둘을 자식으로 만든다.
3. 올라간 가운데 있는 값을 블랙으로 만들고 그 두 자식들을 레드로 만든다.

Recoloring

1. 현재 삽입된 노드(z)의 부모와 그 형제(w)를 블랙으로 하고 내 부모의 부모를 레드로 한다.
2. 내 부모의 부모가 루트 노드가 아니었을 시 더블 레드가 다시 발생 할 수 있다.