레드-블랙 트리(Red_Black_Tree)

레드-블랙 트리

레드 블랙 트리는 자가 균형 이진 탐색 트리입니다.

탐색(Search) 연산의 시간 복잡도 O(logN)

 

레드 블랙 트리는 아래의 조건을 항상 만족해야 합니다.

1. 루트 노드는 블랙이다.
2. 모든 리프 노드는 블랙이다.
3. 노드가 레드이면 그 노드의 자식은 반드시 블랙이다. (No Double Red)
4. 루트 노드에서 임의의 리프 노드에 이르는 경로에서 만나는 블랙 노드의 수는 모두 같다

 

노드 삽입 과정

노드의 삽입은 항상 빨간색

단 루트노드 제외

첫 번째 노드 삽입

(루트 노드는 항상 블랙 노드)

2, 8 노드 삽입

노드 삽입은 항상 빨간색

3 노드 삽입

3번 조건 위배되는 상황 발생 (Double Red)

 

이중 레드 (Double Red) 문제 해결

Restructuring : 삼촌 노드가 검은색이라면 Restructuring을 수행

 

Recoloring  : 삼촌 노드가 빨간색이라면 Recoloring을 수행

 

Restructuring

삼촌 노드가 검은색이라면 Restructuring을 수행

 

현재 노드(N)와 부모 노드(P)가 Double Red 발생

1. 현재 노드와 부모 노드, 부모의 부모 노드(G)를 오름차순으로 정렬

2. 오름차순 정렬 결과에서 가운데 있는 노드를 부모 노드, 나머지 노드를 자식 노드로 지정

3. 가운데 있는 노드는 블랙, 두 자식 노드는 레드로 지정

마지막으로 기존 노드 4의 자식 노드 2는 그대로 딸려오게 된다.

 

Restructuring 자체의 시간복잡도는 O(1) ⇒ 노드 순서 결정, 트리 만드는 시간, 원래 노드의 구조 변환 시간 모두 상수 시간

삽입할 노드가 들어갈 위치를 찾아 해당 노드를 삽입한 뒤 Restructuring이 일어나므로 총 수행시간은 O(logN)

Recoloring

삼촌 노드가 빨간색이라면 Recoloring을 수행

 

1. 현재 삽입된 노드의 부모 노드와 삼촌 노드를 블랙으로 지정

2. 조상 노드를 레드로 지정

3. 조상 노드가 루트 노드가 아닐 경우 이중 레드 문제가 다시 발생될 수 있음

 

블랙 노드 4가 루트 노드가 아니라 다른 어떤 트리의 서브 트리였다면 블랙 노드 4는 레드 노드 4가 됨

레드 노드 4가 루트 노드가 아니므로 레드 노드 4의 또 다른 부모 노드가 있을 수 있고, 이 노드가 레드라면 이중 레드의 문제가 다시 발생

▼

 

최악의 경우 루트 노드까지 올라가면서 Recoloring 수행할 수 있음

 

▼

 

레드 노드 4의 부모 노드의 형제 노드 색깔이 블랙이면 Restructuring, 레드이면 Recoloring을 수행하면서 더 이상 이중 레드 문제가 발생되지 않을 때까지 반복

 

Recoloring 자체의 시간복잡도는 O(1)
Restructuring과 마찬가지로 새로운 노드를 삽입하고자 할 때 삽입할 위치를 먼저 찾아야 하므로 O(logN) 소요

 

---

해당 글은 레드 블랙 트리 PDF 파일을 토대로 개인 공부 목적으로 작성하였습니다.