[ 알고리즘 ] 레드-블랙 트리 (Red-Black Tree)

이진 탐색 트리의 단점

이전에 공부했던 이진 탐색 트리는 검색, 삽입, 삭제 모두 O( h )의 시간복잡도를 보였다.

h = 트리의 높이를 의미하며, 평균적으로 O( log n )이라고 할 수 있다.

하지만 최악의 경우?

이진 탐색 트리는 일반 이진트리 구조이다. 일반 이진트리는 2개 이하의 자식을 가지고 있다는 조건을 가졌을 뿐, Complete 이진트리처럼 균형 잡힌 트리 모양을 보장하지 않는다.

만약 입력 데이터가 [ 1, 2, 3, 4 ] 순으로 들어온다면 아래의 그림과 같이 한쪽으로 치우친 Skewed Tree 모양이 되어, 노드 n개일 때 O( n )의 시간복잡도를 보일 수 있다.

 

한쪽으로 치우친 Skewed Tree

 

이진 트리에 1부터 N까지 랜덤한 숫자가 들어온다면 평균적으로 트리의 높이가 log n이라고 증명되어 있다. logn이라는 높이가 매우 훌륭하다. 하지만 최악의 경우를 보완하기 위해 트리의 삽입, 삭제 연산에서 한쪽으로 치우치지 않도록 균형을 잡아주기 위한 이진트리가 여러 가지가 있다. 그 중 레드-블랙 트리에 대해 공부해보자.

 레드-블랙 트리 (Red-Black Tree) 

- 이진 탐색 트리의 일종

- 균형잡힌 트리 : 높이가 log n

- 삽입(INSERT), 삭제(DELETE) 알고리즘을 수정하여 최악의 경우에도 O(log n)이 유지되도록 해준다.

 

 특징 

- 각 노드는 하나의 키(key), 왼쪽 자식(left), 오른쪽 자식(right), 그리고 부모 노드(p)의 주소를 저장

- 자식 노드가 존재하지 않을 경우 "자식이 없다"라고 하지 않고, NIL노드라고 부르는 특수한 노드가 있다고 가정

- 따라서 모든 리프노드는 NIL노드

- 루트의 부모도 NIL노드라고 가정

- 노드들은 내부 노드와 NIL노드로 분류

- 실제로 NIL노드를 구현하는 것은 아니고, 가상으로 개념만 도입한 것

 조건 

① 각 노드는 Red 노드 혹은 Black 노드

② 루트노드는 Black 노드

③ 모든 리프 노드(즉, NIL 노드)는 Black노드

④ Red 노드의 자식 노드들은 전부 Black (즉, Red노드는 연속되어 등장하지 않음)

⑤ 모든 노드에 대해서 그 노드로부터 자손인 리프 노드에 이르는 모든 경로에 동일한 개수의 Black노드가 존재함

 레드-블랙 트리의 높이 

 

노드 x의 높이 h( x )란?

- 자신으로부터 리프노드까지의 포함된 에지의 개수 중 최댓값

 

노드 x의 블랙-높이 bh( x )란?

- x로부터 리프(NIL) 노드까지 경로에서 블랙 노드의 개수 (노드 x 본인 불포함, NIL노드 포함)

- ⑤번 조건에 의해 항상 동일

 

높이가 h인 노드의 블랙-높이(bh)는?

- bh ≥ h/2

- Red노드는 연속으로 올 수 없다는 것을 생각해 보아라.

 

노드 x를 루트로 하는 서브 트리의 내부 노드 갯수는?

- 최소 2^bh( x ) - 1 개를 포함

- ④ , ⑤번 조건을 고려하여 생각해 보세요.

 

n개의 내부노드를 가지는 레드-블랙 트리의 높이는?

- 2log2(n+1) 이하

- n ≥ 2^bh - 1 ≥ 2^h/2 - 1

 Left and Right Rotation 

- 시간복잡도 O(1) -> 루프도 없고, 연결을 끊어주고 변경해주면 되기 때문

- 회전해도 이진탐색트리의 특성을 유지

- 회전한다고 레드블랙 트리로 유지되는 것은 보장 X

Right Rotation

왼쪽 자식이 있을 경우

루트노드가 되는 노드의 오른쪽 자식이 기존의 루트 노드의 왼쪽 자식이 됨

 

Left Rotation

오른쪽 자식이 있을 경우

루트노드가 되는 노드의 왼쪽 자식이 기존의 루트 노드의 오른쪽 자식이 됨