Red Black Tree ?
위 사진과 같이 이진 탐색 트리(BST)에서는 오름차순 또는 내림 차순으로 Key 값이 삽입된다면 "Key: 1"을 찾는 과정에서 O(h) (h: Tree의 높이) 시간이 걸리게 된다.
이러한 상황에서 데이터 검색 속도가 빠르다는 BST의 장점이 의미가 없게 된다.
BST의 문제점을 보완하고자 나온 것이 균형 이진 탐색 트리이고 그 중 하나가 레드 블랙 트리(RBT)이다.
레드 블랙 트리 규칙
- 모든 Node의 색상은 Red or Black
- 루트 Node는 무조건 Black
- 모든 Leaf 노드(Nil 노드라고 한다)는 무조건 Black
- Red 노드의 자식 노드 양쪽은 언제나 Black
- 어떤 노드에서 Leaf 노드까지의 경로들은 모두 같은 수의 Black 노드를 포함하고 있다.
RBT는 BST와는 다르게 위의 규칙들을 모두 만족시키기 위해 삽입, 삭제 과정에서 트리를 재구성하는 과정을 한번 더 거친다.
그렇게 재구성된 트리에서의 탐색과정은 최악의 상황에서도 O(logN) 만큼의 시간복잡도를 가진다.
최악의 상황에서 RBT와 BST의 시간복잡도 비교
| 삽입 | 삭제 | 탐색 | |
|---|---|---|---|
| RBT | O(logN) | O(logN) | O(logN) |
| BST | O(logN) | O(logN) | O(N) |
트리의 균형을 맞추기 위한 과정
Fix-UP (Insert)
트리에 새로운 키를 삽입하는 과정에서 RBT의 규칙을 위반하는 경우가 생길 수 있다.
이를 해결하기 위해 Fix-UP 과정을 거치며 아래에 나오는 회전을 통해 이 과정을 수행할 수 있다.
회전 (Rotation)
1. Left Roatation
2. Right Rotation
RBT에 새로운 Key를 삽입하는 과정
단순하게 Key를 삽입하는 경우는 BST와 다를게 없다.
키가 들어갈 노드를 탐색한 후 왼쪽 자식으로 들어갈지 오른쪽 자식으로 들어갈지만 정해주면 끝난다.
하지만 RBT에서는 새로운 Key를 삽입할 때 먼저 해당 노드의 색상을 Red로 정한 후 삽입을 한다.
새로 삽입된 노드의 부모 색상이 Red인 경우 RBT의 규칙을 위반하기 때문에 Fix-UP 과정을 통해 색상을 다시 칠하고 트리의 균형을 맞춰주는 작업을 진행한다.
CASE 1: 삼촌 노드(부모 노드의 형제)의 색상이 Red일 때
CASE 2: 삼촌 노드의 색상이 Black일 때 (TRI한 모양)
CASE 3: 삼촌 노드의 색상이 Black일 때 (LINEAR한 모양)
아래 CASE에서 색상 변경이 필요한 노드를 Target 노드라고 부른다.
CASE 1 : 삼촌 노드의 색상이 Red일 때
- Target 노드의 조부모 노드(Grand Parent 노드)의 색상을 Red로 바꾼다.
- 삼촌 노드의 색상과 Target 노드의 부모 노드 색상을 Black으로 바꾼다.
- Target 노드를 현재 Target 노드의 조부모 노드로 갱신한다.
- 새로운 Target이 RBT의 규칙을 위반한다면 다시 Fix-UP 과정을 거친다.
CASE 2 : 삼촌 노드의 색상이 Black일 때 모양이 Tri
- Target 노드를 현재 Target 노드의 부모 노드로 갱신한다.
- Target 노드를 중심으로 left 회전을 한다.
- CASE 3 과정을 거친다.
CASE 3 : 삼촌 노드의 색상이 Black일 때 모양이 Linear
- Target 노드를 조부모 노드로 갱신 후 Right 회전을 한다.
- 회전 과정을 진행하기 전 Target 노드의 조부모 노드의 색상을 Red로 바꿔준다.
- 부모 노드의 색상은 Black으로 바꿔준다.
부모 노드가 왼쪽 자식일 때, 오른쪽 자식일 때 방향만 바꾸어서 똑같이 구현하면 된다.
설명좀요