[자료구조] red-black 트리

정의

레드블랙트리는 다음 조건을 만족하는 이진탐색트리다.

조건

1. 각 노드는 red 혹은 black이다.
2. 루트 노드는 black이다.
3. 모든 Leaf 노드(NIL 노드)는 black 노드다.(NIL노드: 트리의 각 leaf들이 공통적으로 가리키는 추상적인 노드. root의 부모도 NIL 노드)
4. red 노드의 자식들은 전부 black이다.(red 노드가 연속되어 등장하지 않는다)
5. 모든 노드에 대해서 그 노드로부터 자손인 리프노드에 이르는 모든 경로에는 동일한 개수의 black 노드가 존재한다.

레드블랙트리의 높이

루트노드로부터 NIL 노드를 만날 때까지의 높이를 측정한다.

• 노드 x의 높이 h(x)는 자신으로부터 리프노드까지의 가장 긴 경로에 포함된 정점의 개수이다.
• 노드 x의 블랙-높이 bh(x)는 x로부터 리프노드까지의 경로상의 블랙노드의 개수이다. (노드 x 자신은 포함하지 않음)

레드블랙트리의 높이에 관한 필요 조건

1. 높이가 h인 노드의 블랙-높이는 bh >= h/2 이다. (루트노드를 제외하면 전체 h의 절반이 블랙 노드이므로)

   1. 조건4에 의해 레드 노드는 연속될 수 없으므로 당연하다.

2. 노드 x를 루트로하는 임의의 서브트리는 적어도 $2^{bh(x)} - 1$개의 내부 노드를 포함한다. (수학적 귀납법)

3. n개의 내부노드를 가지는 레드블랙트리의 높이는 2log(n+1)이하이다.

노드의 형태를 유지하기 위한 연산: Left and Right Rotation

• 시간복잡도 $O(1)$
• 이진탐색트리의 특성을 유지

red-black 트리에서 insert-fixup

삽입과정에서 노드가 연속으로 red-red가 될 경우 조건에 위배되지 않게 바꿔야한다.
한번에 바뀌는 경우는 없고 반복문을 돌면서 고쳐나가는데 이때 반복문을 수행하면서 절대로 바뀌지 않는 것을 'Loop Invariant'라 한다.
red-red violation에서 loop Invariant는 다음과 같다.
p는 트리배열

1. 연속된 y와 z노드(둘 다 red노드)에서 z는 red노드
2. 오직 하나의 위반만이 존재
   • 조건2: z가 루트노드이면서 red이거나
   • 조건4: z와 그 부모 p[z]가 둘 다 red이거나.
     종료조건: 부모노드 p[z]가 black이되면 종료한다. 조건2가 위반일 경우 z를 블랙으로 바꿔주고 종료

6가지 경우의 수, case by case로 정복하기

case 1,2,3의 경우는 부모 노드가 할아버지의 왼쪽 자식일 경우를 전제로 한다.

1. z의 삼촌이 red일 경우
   • case1: 부모와 삼촌을 black으로 바꾸고 z는 2칸 위로 올라감(여기서 z는 코드로 표현한다면 노드를 가리키는 포인터)

   •  

     

     그림1

2. z의 삼촌이 black일 경우
   • case2: z가 오른쪽 자식인 경우, p[z]에 대해서 left-rotation한 후 원래 p[z]를 z로
   • case3: z가 왼쪽 자식인 경우, p[z]를 black, p[p[z]]를 red로 바꾸고 p[p[z]]에 대해서 right-rotation

   • 

3. case4,5,6은 case1,2,3이 p[z]가 p[p[z]]의 왼쪽자식인 경우의 반대로 p[z]가 p[p[z]]의 오른쪽 자식인 경우이므로 case 1,2,3과 대칭적임

Referece

Inflearn: '영리한 프로그래밍을 위한 알고리즘 강좌'