[DATA STRUCTURE] RED BLACK TREE

Red-Black Tree 정의

이진탐색트리를 기반으로 하는 트리형식의 자료 구조이며, 동일한 노드의 개수일 대, depth를 최소화하여 시간 복잡도를 줄여주는 구조임

• 각 노드는 Red or Black의 색깔을 가짐
• Root node의 색깔은 Black임
• 각 Leaf node는 Black
• 어떤 노드의 색깔이 Red일 경우 두개의 자식 노드의 색깔은 모두 Black

---

Red-Black Tree 특징

• 이진탐색트리이므로 이진탐색트리의 특징을 가짐
• Root node 부터 Leaf node까지의 모든 경로 중 최소 경로와 최대 경로의 크기 비율은 2 보다 크지 않음 이러한 상태를 balanced 상태
• 이진탐색트리의 삽입, 삭제 과정에서 발생하는 문제점을 해결함 
• 노드의 child 가 없을 경우 child 를 가리키는 포인터는 NIL 값을 저장한다. 이러한 NIL들을 leaf node 로 간주

---

Red-Black Tree 삽입

1. 이진탐색트리의 특성을 유지하면서 노드를 삽입 후 삽입된 노드의 색깔을 RED 로 지정
2. Red 로 지정하는 이유는 Black-Height 변경을 최소화하기 위함
3. 삽입 결과 이진탐색트리의 특성 위배(violation)시 노드의 색깔을 조정하고, Black-Height가 위배되었다면 rotation 을 통해 height를 조정
4. 이러한 과정을 통해 RBT 의 동일한 height 에 존재하는 internal node 들의 Black-height 가 같아지게 되고 최소 경로와 최대 경로의 크기 비율이 2 미만으로 유지

Red-Black Tree 삭제

1. 삭제도 삽입과 마찬가지로 이진탐색트리의 특성을 유지하면서 해당 노드를 삭제
2. 삭제될 노드의 child 의 개수에 따라 rotation 방법이 달라짐
3. 만약 지워진 노드의 색깔이 Black 이라면 Black-Height 가 1 감소한 경로에 black node 가 1 개 추가되도록 rotation 하고 노드의 색깔을 조정
4. 지워진 노드의 색깔이 red 라면 Violation 이 발생하지 않으므로 RBT 가 그대로 유지