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

🟩 일종의 자기 균형 이진 탐색 트리

이진 탐색 트리의 조회는 O(logn) 시간이 걸리게 되는데, 문제는 균형이 무너질 경우 O(n)까지 시간이 증가할 수 있다는 것이다. 

👉 레드-블랙 트리의 가장 큰 특징은 삽입, 삭제 동안 트리의 모양이 "균형 잡히도록" 각 노드들은 red or black 색상을 가진다는 것이다. 검색, 삽입, 삭제 시 최악의 경우에서도 모두 O(logn)이 보장되는 자료구조

 

🌟 예1. map

map은 중복을 허용하지 않는 (key, value) 쌍으로 이루어진 트리

map의 내부 구현은 검색, 삽입, 삭제가  O(logn)으로 동작하는 레드-블랙 트리로 구성되어 있다.

 

🟩 성질

리프 노드는 따로 key나 data를 포함하지 않으며, 실제 코드에서도 구현되지 않는 "완전 가상의 노드" 👉 null 값을 갖는다.

black height : 루트 노드에서 리프 노드까지 경로에 있는 검은 노드의 개수

 

1. 각 노드는 레드 or 블랙

2. 루트 노드, 리프 노드는 모두 블랙

3. 레드 노드의 자식은 모두 블랙

4. 블랙 노드의 자식은 상관 없음

5. 루 노드에서 모든 리프 노드까지의 경로에 대해서 거치는 블랙 노드의 숫자는 같다.

 

 

🟩 어떤 두 리프 노드의 레벨 차이가 2배를 넘지 않는 균형 탐색 트리

성질3 👉 루트 노드에서 리프 노드의 경로 상에는 '빨강 노드의 개수 < 검정 노드의 개수'

성질4 👉 루트 노드에서 리프 노드의 경로 상에는 동일한 개수의 검정 노드가 존재

 

🟩 사실상 이진 탐색트리

탐색 연산은 이진 탐색 트리와 동일

삽입 연산은 회전과 색깔 변경과 같은 추가 연산 필요

 

🟩 탐색

이진 탐색 트리의 탐색 방법과 동일

 

🟩 삽입

 

탐색이 실패한 null 노드에 빨강 노드를 추가하고, 두 자식 노드를 null로 만든다.

빨강 노드가 연달아 나타나서 성질3을 만족하지 못한다.

👉 루트 노드 쪽으로 올라가면서 노드의 구조와 색깔을 조정해서 성질을 만족시켜야 한다.

 

🌟 빨강 노드가 연달아 나타나는 경우에 적용하는 규칙

<규칙1> 부모 노드의 형제 노드가 빨강인 경우

👉 부모 노드, 부모 노드의 형제 노드, 부모 노드의 부모 노드의 색깔을 모두 변경

 

<규칙2> 부모 노드의 형제 노드가 검정이고, 현재 노드의 키값이 부모 노드와 부모 노드의 부모 노드 키값의 사이인 경우

👉 현재 노드와 부모 노드를 회전시킴

 

<규칙3> 부모 노드의 형제 노드가 검정이고, 현재 노드의 키값보다 부모 노드와 부모 노드의 부모 노드의 키값이 큰/작은 경우

👉 부모 노드와 부모 노드의 부모 노드를 회전시키고 색깔을 변경

 

부모 노드가 형제 노드를 가지지 않는 경우

👉 부모 노드의 부모 노드가 null 노드를 왼쪽 혹은 오른쪽 자식으로 가지고 있는 경우이다.

이 때 null 노드 또한 검정 노드이므로, restructing 수행 (규칙2 or 규칙3)

 

 

🟩 시간복잡도

O(logn)

 

🟩 장점

삽입/삭제 작업시 균형을 맞추기 위한 작업 횟수가 적다.

각 노드 당 색깔을 표현하는 데 단 1bit의 저장공간만 필요하다.

cf. AVL 트리 : 조회 시 더 빠른 성능 지원

 

🟩 2-3-4트리를 이진 탐색 트리로 표현한 것

빨강 노드를 부모 노드와 묶어서 하나의 노드로 표현