[Reference] Red-Black Tree

Red-Black Tree는 자가 균형 이진 탐색 트리다.

조건

1. 모든 노드는 빨간색 혹은 검은색이다.
2. 루트 노드는 검은색이다.
3. 모든 리프 노드(NIL)들은 검은색이다.(NIL : null leaf, 자료를 갖지 않고 트리의 끝을 나타내는 노드)
4. 빨간색 노드의 자식은 검은색이다.(No Double Red : 빨간색 노드가 연속으로 나올 수 없다.)
5. 모든 리프 노드에서 Black Depth는 같다.(리프노드에서 루트 노드까지 가는 경로에서 만나는 검은색 노드의 개수가 같다.)

삽입 과정

새로운 노드를 삽입할 때 새로운 노드는 항상 빨간색으로 삽입한다.
이렇게 되면 빨간색 노드가 연속으로 2번 나타나서 4번 조건에 위배된다.

Double Red 문제를 해결하기 위해 2가지 전략을 사용한다.

• 새로 삽입할 노드 N(New)
• 부모 노드 P(Parent)
• 조상 노드 G(Grand Parent)
• 삼촌 노드 U(Uncle)

Restructuring

1. 새로운 노드(N), 부모 노드(P), 조상 노드(G)를 오름차순으로 정렬한다.
2. 셋 중에 중간 값을 부모로 만들고 나머지 둘을 자식으로 만든다.
3. 부모가 된 노드를 검은색으로 만들고 나머지 자식들을 빨간색으로 만든다.

• 새로운 노드 N과 부모 P, 조상 G를 오름차순으로 정렬한다.
• 중간값인 3을 부모 노드로 바꾸고 2, 5를 자식 노드로 바꾼다.
• 새로 부모가 된 3을 검은색으로 바꿔주고, 나머지 2, 5를 빨간색으로 변경해준다.
• 규칙 3을 만족하지 않는 것 처럼 보일 수 있지만, 값이 2인 노드는 자식 노드 NIL 2개를 가지고 있고 이것들이 검은색이라고 생각하면 된다.

Recoloring

1. 새로운 노드(N)의 부모(P)와 삼촌(U)을 검은색으로 바꾸고 조상(G)을 빨간색으로 바꾼다.
2. 조상(G)이 루트 노드라면 검은색으로 바꾼다.
3. 조상(G)을 빨간색으로 변경 후 Double Red가 발생하면 Restructuring 혹은 Recoloring을 진행한다.

• 부모 P와 삼촌 U를 검은색으로 바꾸고, 조상 G를 빨간색으로 변경한다.

• 루트 노드는 검은색이라는 조건을 지켜야 하므로, 루트 노드를 검은색으로 변경한다.
• 이렇게 하면 모든 조건이 지켜지면서 Double Red 문제가 해결된다.
  • 검은색 노드는 연속 2번 나와도 된다.