레드-블랙 트리
자가 균형 이진 탐색 트리
- 균형의 의미?
가장 깊은 경우와 가장 얕은 경우가 기껏해야 2배 차이나는것
즉 루트부터 leaf까지의 모든 경로 중 최소 경로와 최대 경로의 크기 비율은 2보다 크지 않다는 것이다.
아래의 조건을 만족한다.
- 모든 노드는 빨간색 혹은 검은색이다.
- 루트 노드는 검은색이다.
- 모든 리프 노드(NIL)들은 검은색이다. (NIL : null leaf, 자료를 갖지 않고 트리의 끝을 나타내는 노드)
- 빨간색 노드의 자식은 검은색이다.
- No Double Red(빨간색 노드가 연속으로 나올 수 없다) - 모든 리프 노드에서 Black Depth는 같다.
- 리프노드에서 루트 노드까지 가는 경로에서 만나는 검은색 노드의 개수가 같다.
[black depth]
- 어떤 노드에서 root까지 가는 경로에 있는 black 노드들의 수.
- 보통 leaf에서 시작해야 의미가 있고, red-black tree에서는 어떤 leaf node에서 시작하던지 root까지 가는 경로에서 만나는 black 노드들의 수는 같다.
[높이]
n개의 노드들이 있는 red-black tree에서의 높이는 O(logn)이다.
→ 정확히 왼쪽, 오른쪽으로 개수가 n/2씩으로 반반 나뉘어지지는 않지만, balanced이므로 O(logn)로 bound된다는 사실만 알자.
-> Search, Insert, Delete에 대한 시간복잡도 또한 O(logN)
레드-블랙트리 삽입 과정
레드-블랙 트리에 새로운 노드를 삽입할 때 새로운 노드는 항상 빨간색으로 삽입한다.
이렇게 되면 'No Double Red' 조건이 위배되는 상황이 발생한다. 즉, 빨간색 노드가 연속으로 2번 나타날 수 있다(Double Red)
레드 블랙 트리는 이러한 Double Red 문제를 해결하기 위해 2가지 전략을 사용한다.
(앞으로 새로 삽입할 노드를 N(New), 부모 노드를 P(Parent), 조상 노드를 G(Grand Parent), 삼촌 노드를 U(Uncle)라고 하자. 즉, 삼촌 노드 : 부모의 형제)
Double Red가 발생했을 때
- 삼촌 노드가 검은색이라면 -> Restructuring을 수행
- 삼촌 노드가 빨간색이라면 -> Recoloring을 수행
Restructuring
Restructuring 과정
- 새로운 노드(N), 부모 노드(P), 조상 노드(G)를 오름차순으로 정렬한다.
- 셋 중 중간값을 부모로 만들고 나머지 둘을 자식으로 만든다.
- 새로 부모가 된 노드를 검은색으로 만들고 나머지 자식들을 빨간색으로 만든다.
Double Red가 발생했는데 삼촌 노드가 검은색이다. 따라서 Restructuring을 수행한다.
먼저 새로운 노드 N과 부모 P, 조상 G를 오름차순으로 정렬한다. 그러면 3이 중간값이 된다.
중간값인 3을 부모 노드로 바꾸고 나머지 2와 5를 자식 노드로 바꾼다.
당연히 원래 5의 자식 노드였던 7은 딸려가게 된다.
마지막으로 새롭게 부모가 된 3을 검은색으로 바꿔주고 나머지 두 자식인 2, 5의 색을 빨간색으로 바꿔주면 Double Red 문제가 해결된다!
여기서 많이들 헷갈리는 게 완성된 트리가 '모든 리프 노드는 검은색' 규칙을 만족하지 않는 것처럼 보일 수 있다.
이는 값이 2인 노드는 자식 노드 NIL 2개를 가지고 있고 그 NIL들이 검은색이라고 생각하면 된다.
Recoloring
Recoloring 과정
- 새로운 노드(N)의 부모(P)와 삼촌(U)을 검은색으로 바꾸고 조상(G)을 빨간색으로 바꾼다.
1-1. 조상(G)이 루트 노드라면 검은색으로 바꾼다.
1-2. 조상(G)을 빨간색으로 바꿨을 때 또다시 Double Red가 발생한다면 또다시 Restructuring 혹은 Recoloring을 진행해서 Double Red 문제가 발생하지 않을 때까지 반복한다.
Double Red가 발생했는데 삼촌 노드가 빨간색이다. 따라서 Recoloring을 수행한다.
먼저 부모(P)와 삼촌(U)을 검은색으로 바꾸고, 조상(G)을 빨간색으로 바꾼다.
하지만 루트 노드는 검은색이라는 조건을 지켜야 하므로, 루트 노드를 검은색으로 바꾼다.
이렇게 하면 모든 조건이 지켜지면서 Double Red 문제가 해결된다.
검은색 노드는 2번 나와도 되냐고 묻는다면 Yes이다.
빨간색 노드가 2번 나오면 안 되는 것이다.
Recoloring은 간단해 보이지만 문제는 조상 노드(G)가 루트 노드가 아니면서, 조상 노드(G)가 또다시 Double Red 문제가 발생하는 경우이다.
이 경우를 살펴보자.
위와 같은 상황을 가정하자. 왼쪽 트리에서 Recoloring을 진행하면 오른쪽 트리가 된다.
이때 조상 노드(G)가 또다시 Double Red가 발생하게 된다.
Double Red 문제가 발생한 "값이 5인 노드"를 기준으로 다시 한번 살펴보자.
해당 노드의 삼촌(U)이 빨간색이므로 다시 Recoloring을 진행해주면 Double Red 문제를 해결할 수 있다!
만약 해당 노드의 삼촌(U)가 검은색이었다면 Restructuring을 진행해주면 된다.
레드-블랙 트리 예제
레드-블랙 트리에 순서대로 8, 7, 9, 3, 6, 4, 5, 12를 삽입한 후의 상태를 그리시오.
"삼촌 노드가 없는데??"라고 생각할 수 있다.
맨 위의 [그림 1]을 보면 모든 리프 노드들은 검은색 NIL 노드인 것을 확인할 수 있다.
즉, 좀 비어있는 것처럼 보이면 그냥 검은색 노드가 있다고 생각하면 편하다.
따라서 Restructuring을 진행하면 된다.
시뮬레이터 사이트
눈으로 직접 확인해보고 싶다면 아래 사이트를 참고하자.
레드 블랙 트리에 원소를 삽입하는 과정을 확인할 수 있다.
https://www.cs.usfca.edu/~galles/visualization/RedBlack.html
