레드블랙트리 Red-Black Tree
이전 이진검색트리에서, 평균 수행시간이 O(log n)이라 했다. 그러나 트리의 균형이 나쁘다면 최악의 경우 n에 비례한 시간이 걸린다. 이를 보완하기 위한 '균형 잡힌 이진트리'가 바로 레드블랙트리다.
이진검색트리에 몇 가지 조건을 추가해서 균형 잡힌 트리가 되도록 한다. 트리의 높이, 검색/삽입/삭제 연산이 모두 O(log n)의 시간이 걸린다.
레드블랙트리는 모든 노드에 빨강 혹은 검정을 칠하되 다음과 같은 특성을 만족해야 한다.
- 루트는 블랙이다.
- 모든 리프(NIL, Null값과 같다)는 블랙이다.
- 노드가 레드면 그 노드의 자식은 반드시 블랙이다.
- 루트 노드에서 임의의 리프노드에 이르는 경로에서 만나는 블랙 노드의 수는 모두 같다.
참고로 레드블랙트리의 리프노드는 일반적인 리프 노드가 아니라 NIL 포인터가 NIL 노드를 가리키는 것으로 본다.
레드블랙트리의 연산
기본적으로 검색, 삽입, 삭제 모두 이진검색트리와 동일하다. 여기서 이진검색트리와 다른 점은 삽입과 삭제로 인해 이진트리의 균형이 깨지지 않으면 그대로 연산을 완료하되, 만약 깨진다면 균형을 바로 잡는 작업을 실행하여 레드블랙트리의 특성을 만족시킨다.
레드블랙트리 삽입
비어있는 트리에 처음 삽입되는 노드가 아니라면 무조건 새로 삽입하는 노드는 빨강으로 칠한다.
이 노드를 x, 이 노드의 부모노드를 p라고 하자.
레드블랙트리의 특성에 의하여, p가 검정이면 아무 문제 없으나 빨강이면 특성 3번이 깨진다. 따라서 해결해야 한다.
여기서 전제가 3가지 있다. p의 부모노드 p^2는 반드시 검정이어야 한다. 그리고 x의 형제 노드는 반드시 검정이다. 마지막으로, q의 자식 노드 중 하나인 s가 있다고 가정했을 때, 이 s의 색상에 따라 두 가지 경우로 나눈다.
- case 1 : s가 빨강인 경우
색상만 변경하면 된다. 그러나 p^2가 빨강이면 이를 x로 삼아서 재귀적으로 문제를 해결해야 한다. 재귀문제가 발생할 수도 있기 때문이다.
- case 2-1 : s가 블랙이고 x가 p의 오른쪽 자식일 경우
회전시키고 마무리로 색변경을 해준다.
- case 2-2 : s가 검정이고 x가 p의 왼쪽 자식인 경우
회전하고 색상을 변경한다.
실제 예를 들며 배우자. 다음 레드블랙트리에 1을 삽입하다고 가정해보자.
삽입을 하는 대상인 노드는 빨강이다. 이렇게 되면 레드블랙트리의 조건이 깨진다.
case 2-2인 경우이기 때문에 회전 후 색상변경을 해주면 다음과 같다.
레드블랙트리 삭제
기본적으로 이진검색트리의 삭제 방법을 쓰되 필요한 경우 색상을 조정한다.
삭제 노드는 다음과 같이 3가지로 나눠 처리할 수 있다.
- 삭제노드가 빨강이면 간단히 삭제된다. 자식노드도 하나다.
- 삭제노드가 검정이라도 유일한 자식이 검정이면 간단히 삭제된다.
- 삭제노드가 검정이고 유일한 자식도 검정이면 간단히 삭제할 수 없다. (실제로 자식노드가 모두 NIL인 경우에 해당한다.)
다음 같은 경우엔 m을 제거한 후에도 레드블랙특성 4번(루트 노드에서 임의의 리프노드에 이르는 경로에서 만나는 블랙 노드의 수는 모두 같다)에 위반한다.
따라서 m를 제거하고도 x의 주변 상황에 따라 처리방법이 달라진다.
삭제노드가 검정이고 유일한 자식노드로 검정이면 m을 삭제한 후 상황은 몇 가지로 나뉜다.
각 경우에 따라 처리하면 다음과 같다.
case 2-1은 앞서 언급했던 recursive problem이 발생하므로 p를 노드 x로 해 재귀적으로 다시 처리한다.
결국 레드블랙트리는 균형 잡힌 이진검색트리로써 O(log n) 시간이 보장된다.
'공부한 기록 > 알고리즘' 카테고리의 다른 글
| 알고리즘(11) - 해시테이블 Hash table (0) | 2023.04.18 |
|---|---|
| 알고리즘(10) - 검색트리 - B-Tree, 다차원 검색트리(KD-Tree) (0) | 2023.04.06 |
| 알고리즘(8) - 검색트리 ( search tree ) (0) | 2023.04.03 |
| 알고리즘(7) - 선택 알고리즘 Selection algorithm (0) | 2023.03.29 |
| 알고리즘(6) - 특수 정렬(계수 정렬, 기수 정렬) (0) | 2023.03.23 |