레드 블랙 트리

레드 블랙 트리

1. 루트는 블랙이다.

2. 모든 리프는 블랙이다.

=> 레드 블랙 트리에서 리프는 맨 밑에 노드가 아닌 맨 밑에 숨겨진 자식 노드, 즉 존재하지 않는 NIL을 의미한다.

3. 노드가 레드이면 그 노드의 자식은 반드시 블랙이다.

=> 노드가 블랙이면 색은 상관없다.

4. 루트 노드에서 임의의 리프 노드에 이르는 경로에서 만나는 블랙 노드의 수는 모두 같다.

오른쪽 그림처럼 NIL에 갈 때 만나는 블랙 노드 개수가 모두 3개로 통일이다.

 

레드 블랙 트리 삽입

이진검색트리에서의 삽입과 같지만 삽입된 노드는 반드시 레드로 칠한다.

 

-부모가 블랙

문제 없다.

 

-부모가 레드

문제가 발생한다.

=> 삽입된 노드의 부모의 형제를 확인한다.

 

case1: 부모의 형제가 빨간색인 경우(recoloring)

부모와 부모의 형제가 모두 빨간색이면 부모와 부모의 형제를 검정색으로 바꾼다.

그리고 부모의 부모가 루트 노드가 아니면 빨간색으로 바꾼다.

 

case2: 부모의 형제가 검정색인 경우

-x가 p의 오른쪽 자식

이런 경우에는 p를 중심으로 왼쪽으로 회전한다. 

 

-x가 p의 왼쪽 자식

p^2를 중심으로 오른쪽으로 회전하고 p와 p^2의 색을 바꾼다.

 

-삽입 예시