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

Ouroboros·2023년 11월 8일

자료구조

목록 보기

11/13

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

Red-Black Tree는 일종의 자기 균형 이진 탐색 트리이다. .즉 자기 스스로 균형을 잡는 이진 탐색 트리라는 뜻이다. RB Tree의 가장 큰 특징은 삽입, 삭제 동안 트리의 모양이 “균형 잡히도록" 각 노드들은 red 나 black 색상을 가진다는 것이다.
따라서 검색, 삽입, 삭제 시 모두 O(logN)이 보장되는 자료 구조이다.

1. 조건

각 노드는 레드 or 블랙이다.
루트 노드와 모든 NIL 노드들은 항상 블랙이다. (NIL : null leaf, 자료를 갖지 않고 트리의 끝을 나타내는 노드)
레드 노드는 자식으로 레드 노드가 있으면 안된다. 레드 노드의 자식은 모두 블랙이다.
블랙 노드의 자식은 아무거나 상관없다.
루트 노드에서 모든 리프 노드까지의 경로에 대해서 거치는 블랙 노드의 숫자는 같다.

2. 용어정리

1) NIL node (leaf)
자료를 갖지 않고 트리의 끝을 나타내는 노드이다.
그림에서 사각형으로 된 리프 노드가 NIL node이다. 이 노드는 따로 key나 data를 포함하지 않으며 실제 코드에서도 구현하지 않는 "완전 가상의 노드"이다.

2) internal nodes
internal nodes는 NIL이 아닌 나머지 노드들이다.

3) black height
black height는 루트 노드에서부터 리프 노드까지 경로에 있는 검은 노드의 개수이다.

2. 사용예

1) map in C++ STL

C++의 map은 중복을 허용하지 않는 (key, value) 쌍으로 이루어진 트리이다.
map의 내부 구현은 RB Tree로 구성되어있다.

이진 탐색 트리에는 RB Tree 이외에도 대표적으로 AVL tree가 있다. 하지만 트리의 균형을 다시 잡는 작업이 RB Tree는 O(1), AVL tree는 O(log N)에 동작하기 때문에 현재 RB Tree를 사용하고 있다.

2) TreeMap in Java 8~

TreeMap을 RB Tree로 구현하였다. 그 결과 조회의 시간 복잡도가 O(N) → O(log N)이 되었다.

3) Linux kernel에서의 Completely Fair Scheduler(CFS), epoll

삽입

레드-블랙 트리에 새로운 노드를 삽입할 때 새로운 노드는 항상 빨간색으로 삽입한다.
이렇게 되면 3번 조건이 위배되는 상황이 발생한다. 즉, 빨간색 노드가 연속으로 2번 나타날 수 있다. Double Red 상태가 되었기 때문에 일종의 기술이 필요하다.
레드 블랙 트리는 이러한 Double Red 문제를 해결하기 위해 2가지 전략을 사용한다.

이때 사용하는 기술은 현재 삽입된 노드(3)의 삼촌 노드(부모의 형제, 7)의 색깔에 따라 나뉜다.

만약 삼촌 노드가 검정이면 Restructing, 빨간색이면 Recoloring 기술을 사용해야 한다.

1. Restructing

(사진출처 : https://suhwanc.tistory.com/197)

Restructing 과정

1) 삽입된 노드와 그 부모, 그 조부모 노드를 오름차순으로 정렬합니다.
-> (삽입노드-부모-조부모) 노드는 오름차순 정렬 시 5,6,7이 되며 가운데 값은 6이다.

2) 가운데 값을 부모로 만든 뒤, 나머지 둘을 자식으로 만들어줍니다.
-> 6을 부모노드로 만든다!

3) 이때 부모는 검은색 노드, 두 자식들은 빨간색 노드로 만듭니다.
->

** 원래 트리에서 3은 5의 왼쪽 자식이다. 그래서 그대로 다시 붙여주면 된다.

이 작업은 다른 서브 트리에 영향을 미치지 않게 된다. 조정하는 것 자체의 시간 복잡도 역시 O(1)이다.
다만, 노드 삽입 과정에서 O(log N) 시간이 걸리기 때문에 총 시간 복잡도는 O(log N)이 된다.

2. Recoloring

Recoloring 과정

새로운 노드(N)의 부모(P)와 삼촌(U)을 검은색으로 바꾸고 조상(G)을 빨간색으로 바꾼다.

1-1. 조상(G)이 루트 노드라면 검은색으로 바꾼다.

새로운 노드(N,3)의 부모(P,2)와 삼촌(U,7)을 검은색으로 바꾸고 조상(G)을 빨간색으로 바꾼다.
루트 노드(G,5)는 검은색이어야 하므로, 루트 노드를 검은색으로 바꾼다.
**검은색 노드는 2번 나와도 상관없다!

1-2. 조상 노드(G)가 루트 노드가 아니면서, 조상 노드(G)가 또다시 Double Red 문제가 발생하는 경우

-> 조상(G)을 빨간색으로 바꿨을 때 또다시 Double Red가 발생한다면 또다시 Restructuring 혹은 Recoloring을 진행해서 Double Red 문제가 발생하지 않을 때까지 반복한다.

새로운 노드(N,3)의 부모(P,2)와 삼촌(U,7)을 검은색으로 바꾼다.
조상 노드(G,5)가 9값을 가진 노드와 또다시 Double Red가 발생하게 된다.

Double Red가 발생했으므로 '값이 5인 노드'를 기준으로 다시 한번 살펴보자.
해당 노드의 삼촌(U,14)이 빨간색이므로 다시 Recoloring(삼촌노드와 부모노드를 검은색으로 바꾸어줌)을 진행해주어 Double Red 문제를 해결한다.
만약 해당 노드의 삼촌(U,14)가 검은색이었다면 Restructuring(삽입노드-부모-조부모를 정렬하여 가운데 값(부모가 된 값)을 블랙으로 나머지값을 레드로 바꾸어줌)을 진행해주면 된다.