레드-블랙 트리(Red-Black Tree, RB Tree)
트리(Tree)의 가장 큰 장점은 분기(branch)마다 데이터 탐색 범위를 대폭 줄여나간다는 것이다.
하지만 이 장점을 제대로 활용하기 위해서는 트리 자체가 균형을 이뤄야 한다.
즉, 편향된 트리는 메모리만 더 많이 사용할 뿐 $O(N)$ 속도로 탐색되기 때문이다.
이러한 문제점을 해결하기 위해 B Trees와 같이 자가 균형 트리(Self-Balanced Tree)들이 등장했다.
레드-블랙 트리(RB Tree)는 자가 균형 이진 탐색 트리(Self-Balanced Binary Search Tree)로 1978년 레오 귀바스(Leo J. Guibas)와 로버트 세지윅이 1972년 루돌프 바이어가 창안한 "대칭형 이진 B-트리"를 발전시켜 만들었다.
레드-블랙 트리는 복잡한 자료구조지만, 실 사용에서 효율적이고, 최악의 경우에도 상당히 우수한 실행 시간을 보인다.
트리에 N개의 원소가 있을 때 $O(log \ N)$의 시간 복잡도로 삽입, 삭제, 검색을 할 수 있다.
따라서 Seperate Chaining 뿐만 아니라 다양한 분야에서 활용된다.
조건
- 일반적인 이진 탐색 트리의 조건을 만족해야 한다.
- 루트 노드(Root Node) : 루트 노드의 색은 반드시 검정(Black)이다.
- 리프 노드(Leaf Node) : 리프 노드는 모두 검정(Black)이다.
- 여기서 리프 노드는 값이 없는 노드를 뜻하는 NIL이다. (null leaves, nil leaves라고도 한다)
- NIL을 생략하는 경우가 많아 마치 리프 노드가 빨간색처럼 보이지만, 조건을 만족하지 않는 것은 아니다.
- 내부 노드(Internal Node) : 빨강(Red) 내부 노드의 자식은 반드시 검정(Black)이다.
- 빨간색 노드가 연속으로 나올 수 없다. (No Double Red)
- 모든 리프 노드에서 루트 노드까지 가는 경로에서 검은색 노드의 수는 모두 같다. (Black Depth 동일)
- 한쪽에 치우쳐지는 것을 방지한다.
특성
- 새로운 노드는 빨간색을 전제로 시작한다.
- 조건에 맞는 트리를 구성하기 위해 재색칠, 회전 등이 일어난다.
- 루트 노드부터 가장 먼 리프 노드 경로까지의 거리가, 가장 가까운 리프 노드까지의 거리의 두 배보다 항상 작다.
- 즉, 개략적(roughly)으로 균형이 잡혀있다.
- 최단 경로가 모두 블랙 노드로만 구성되어 있다고 했을 때, 최장 경로는 블랙 노드와 레드 노드가 번갈아 나오는 것이 될 것이다. 조건 5에 따라 모든 경로에서 블랙 노드의 수가 같기 때문에 존재하는 모든 경로에 대해 최장 경로의 거리는 최단 경로의 거리의 두 배 이상이 될 수 없다.
- B-Tree나 AVL 트리만큼 엄격하게 균형을 유지하지는 않는다.
삽입
우선 기본적인 이진 탐색 트리 삽입 과정을 거친다.
아래는 8, 18, 5, 15, 17
순서대로 삽입을 진행하는 예제이다.
루트 노드는 반드시 검은색이어야 한다.
이진 탐색 트리 규칙에 의해 18은 8보다 크므로 오른쪽에 배치된다. 이때 새로운 노드는 빨간색을 전제로 삽입된다.
5는 8보다 작으므로 왼쪽에 배치된다.
15는 8보다 크므로 오른쪽 18보다 작으므로 왼쪽으로 이동해 배치됐다.
하지만, 조건 4(빨간색 내부 노드의 자식은 검은색)를 배반한다.
이럴 경우 레드 블랙 트리는 Restructuring 혹은 Recoloring을 수행한다.
1. 재구성, 회전(Restructuring)
마치 재구조화하는 과정이 회전하는 것처럼 보인다고 해서 회전이라고도 한다.
코드를 작성할 때에는 왼쪽/오른쪽에 따라 가져오는 포인터가 다르므로 각각 작성한다.
(코드에서는 좌회전/우회전으로 나눠서 작성하지만, 여기서는 포괄적으로 설명하기 위해 묶어서 재구성한다고 작성하였다.)
- Double Red가 발생한 자식 노드를 기준으로 부모 노드, 조부모 노드(부모의 부모) 총 3개의 노드를 정렬한다.
- 중앙값을 부모 노드로 지정하고, 부모 노드는 검은색, 자식 노드는 빨간색으로 변경.
- 기존 트리에 대입
아래는 Restructuring 예시이다.
2. 재색칠(Recoloring)
- 현재 삽입된 노드의 부모 노드와 삼촌 노드를 검은색으로 교체
- 조부모 노드를 빨간색으로 교체
- 계속해서 층별 노드의 색을 교체
- 이때, 조부모 노드가 루트 노드라면 다시 블랙으로 교체하여 루트 노드를 제외한 모든 노드의 색을 교체
아래는 Recoloring 예시이다.
만약, 위 트리가 전체 트리의 서브 트리라고 하면, 4를 빨간색으로 뒀을 것이다.
이때 4의 부모 노드가 빨간색이라면 Double Red가 발생하게 되므로 회전이나 재색칠을 통해 해결하면 된다.
재색칠을 통해 해결한다고 하면 최악의 경우 루트 노드까지 계속해서 색이 변경될 수 있다.
따라서, 재색칠의 시간 복잡도는 O(log N)이 된다.
회전과 재색칠을 선택하는 방법은 삼촌 노드(부모의 형제 노드)의 색을 보고 결정하면 된다.
삼촌 노드가 검은색이라면 회전(Restructuring), 빨간색이라면 재색칠(Recoloring)을 하면 된다.
case 2를 회전한다고 생각해보자. 이 경우 4도 빨간색, 2도 빨간색으로 다시 Double Red가 발생한다.
따라서 이 상황에서는 삼촌 노드가 빨간색이므로 재색칠을 수행한다.
재색칠 완료
17을 삽입했으나 Double Red 발생했다.
17의 삼촌 노드(NIL)는 검은색이므로 회전을 수행한다.
15 17 18로 정렬한 후,
17을 부모 노드(검은색) 15 18을 자식 노드(빨간색)로 변경한다.
삭제
삭제 역시 기본적인 이진 탐색 트리 규칙을 기반으로 수행된다.
다만, 삭제 후 무너진 규칙을 복구하는 절차를 밟는다.
위에서 레드 블랙 트리에 대한 전반적인 내용을 이해했다는 가정하에
이번에는 슈도 코드를 통해 삭제 과정을 살펴본다.
코드를 보면 크게 3가지 과정으로 나뉜다.
1. 삭제할 노드의 정보 저장
z는 삭제할 노드이고, y는 z를 대체할 노드이다.
우선 y에 z를 할당하고, y-original-color 변수에 삭제되는 노드(z == y)의 색을 저장한다.
아래 예를 보자. 삭제될 대상은 key = 35이다.
y = 35, y-original-color = black 이 들어간다.
대체될 노드가 정해지면 해당 색으로 노드를 색칠하기 위함이다.
2. 해당 노드의 자식 상황 판별 후, 대체될 노드 확정
자세하게 살펴보기 전 RB-TRANSPLANT와 TREE-MINIMUM 함수를 살펴보고 가자.
TRANSPLANT 함수는 삭제될 노드 u의 자리를 v로 대체하는 함수이다.
- u의 부모 노드가 NIL. 즉, u가 루트 노드 일 때
- 루트 노드를 v로 지정
- u가 부모 노드 기준 왼쪽 자식일 때
- u 자리를 v로 대체
- u가 부모 노드 기준 오른쪽 자식일 때
- u 자리를 v로 대체
마지막으로 v의 부모를 u의 부모로 설정해준다.
왜 서브 트리에서 최솟값을 구해야 하는 것일까?
그건 바로 대체할 적절한 노드를 찾기 위함이다.
위 그림에서 루트 노드(10)를 삭제한다고 가정해보자.
10을 대체할 수 있는 후보 노드는 5와 14가 될 것이다.
5는 삭제될 노드의 왼쪽 서브 트리에서 가장 오른쪽(최대) 값이고, 14는 오른쪽 서브 트리에서 가장 왼쪽(최소) 값이다.
둘 중 아무 노드로 대체해도 되지만 여기서는 최솟값인 14로 대체하는 것으로 진행한다.
이제 두 번째 과정을 자세히 살펴보자.
조건문 기준으로 나누면 아래 3가지와 같다.
- 대상 노드의 왼쪽 자식이 NIL 일 때
- 대상 노드의 오른쪽 자식을 x로 설정
- z자리에 z의 오른쪽 자식을 이식
- 아니라면, 대상 노드의 오른쪽 자식이 NIL 일 때
- 대상 노드의 왼쪽 자식을 x로 설정
- z자리에 z의 왼쪽 자식을 이식
- 둘 다 아니라면
- z의 오른쪽 자식 기준 서브 트리의 최솟값을 y로 선정
- y-original-color를 바뀐 y의 색으로 지정
- y의 오른쪽 자식을 x로 설정
- y의 부모가 z라면,
- y를 x의 부모로 설정
- y의 부모가 z가 아니라면,
- y자리에 y 오른쪽 자식을 이식
- z의 오른쪽 자식을 y의 오른쪽 자식으로 설정
- 바뀐 y의 오른쪽 자식 부모를 y로 설정
- z 자리에 y를 이식
- z 왼쪽 자식을 y의 왼쪽 자식으로 설정
- y를 바뀐 y의 왼쪽 자식의 부모로 설정
- y의 색을 기존 z 색으로 설정
여기까지 진행하면 삭제는 됐으나 트리의 균형이 맞지 않는 문제가 발생한다.
조건 5에 따라 Black Depth가 동일해야 하는데, 검은색 노드인 35를 삭제함으로써 Depth가 달라졌기 때문이다.
빨간색 노드를 삭제했더라면 이러한 경우는 발생하지 않는다.
이처럼 검은색 노드를 삭제해서 대체되는 노드를 검은색으로 칠했는데 대체되는 노드가 원래 검은색인 경우,
이를 이중 흑색 노드라고 한다.
이중 흑색 노드가 발생하면 Depth가 줄어든 것이기 때문에 다음과 같은 재조정이 필요하다.
3. 삭제 후 수정
1. x의 형제 노드를 w에 저장
2. 4가지 케이스에 따라 다음과 같이 처리. (이중 흑색 노드를 처리하는 과정이다.)
- case 1 : 형제 노드가 빨간색 노드인 경우
- 형제 노드를 검은색으로 변경(60이 검은색이 됨)
- x의 부모 노드 색을 빨간색으로 변경(50이 빨간색이 됨)
- x의 부모 노드 기준으로 좌회전(60이 루트 노드가 됨)
- x의 부모 노드의 오른쪽 자식을 w로 설정(55가 형제 노드가 됨)
- case 2 : 형제 노드의 왼쪽 자식과 오른쪽 자식이 모두 검은색 일 때(w = 55, w.left가 빨간색이므로 pass)
- 형제 노드를 빨간색으로 변경
- x를 x의 부모로 설정
- case 3 : 형제 노드의 왼쪽 자식이 빨간색, 오른쪽 자식이 검은색 일 때
- 형제 노드의 왼쪽 자식을 검은색으로 변경(53을 검은색으로 변경)
- 형제 노드를 빨간색으로 변경(55를 빨간색으로 변경)
- 형제 노드를 기준으로 우회전(50 → 53 → 55로 정렬)
- x의 부모 노드의 오른쪽 자식을 w로 설정(53을 w로 설정)
- case 4로 이동
- case 4 : 형제 노드가 검은색이거나, 형제 노드의 왼쪽 자식이 검은색, 오른쪽 자식이 빨간색일 때
- 형제 노드의 색을 x의 부모 노드 색으로 변경(53을 50의 색인 빨간색으로 변경)
- x의 부모 노드를 검은색으로 변경(50을 검은색으로 변경)
- 형제 노드의 오른쪽 자식을 검은색으로 변경(55를 검은색으로 변경)
- x의 부모 노드를 기준으로 좌회전(이중 흑색 노드인 NIL의 Black Depth가 증가)
- x를 루트 노드로 지정(반복문 탈출)
3. x가 루트 노드가 아니고, x의 색이 검은색이라면 위 과정을 반복
4. 반복문이 끝나면, x를 검은색으로 변경 (반복문을 수행하지 않아도 x를 검은색으로 칠한다.)
Ref.
https://zeddios.tistory.com/237
https://ko.wikipedia.org/wiki/%EB%A0%88%EB%93%9C-%EB%B8%94%EB%9E%99_%ED%8A%B8%EB%A6%AC
https://velog.io/@jakeseo_me/이것이-자바다-추가-정리-레드블랙-트리-정리
https://junboom.tistory.com/18
https://velog.io/@stthunderl/Red-Black-Tree-4-삭제deletion-delete-deletefixup
'Computer Science > Data Structure' 카테고리의 다른 글
| B Trees (B-Tree & B+ Tree & B* Tree) (0) | 2022.06.02 |
|---|---|
| 해시 테이블(Hash Table) (0) | 2022.06.01 |
| 그래프(Graph) (0) | 2022.05.31 |
| 트리(Tree) & 이진탐색트리(BST) & 힙(Heap) (0) | 2022.05.30 |
| 스택(Stack) & 큐(Queue) & 덱(Deque) (0) | 2022.05.27 |
댓글