[자료구조] 레드-블랙 트리(Red-Black Tree)란? | 레드-블랙 트리 쉽게 이해하기

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

레드-블랙트리
[그림 1] 레드-블랙트리 (출처 : 위키피디아)

레드-블랙 트리는 자가 균형 이진 탐색 트리이다. 레드-블랙 트리는 다음과 같은 조건들을 만족한다.

1. 모든 노드는 빨간색 혹은 검은색이다.
2. 루트 노드는 검은색이다.
3. 모든 리프 노드(NIL)들은 검은색이다. (NIL : null leaf, 자료를 갖지 않고 트리의 끝을 나타내는 노드)
4. 빨간색 노드의 자식은 검은색이다.
   == No Double Red(빨간색 노드가 연속으로 나올 수 없다)
5. 모든 리프 노드에서 Black Depth는 같다.
   == 리프노드에서 루트 노드까지 가는 경로에서 만나는 검은색 노드의 개수가 같다.

트리 관련 용어를 잘 모르겠다면 다음 포스팅을 참고하자.

 

[자료구조] 트리(Tree)의 개념 | 이진 트리, 전 이진 트리, 완전 이진트리, 포화 이진 트리, 이진 탐

트리(Tree)의 개념 트리는 노드로 이루어진 자료구조로 스택이나 큐와 같은 선형 구조가 아닌 비선형 자료구조이다. 트리는 계층적 관계를 표현하는 자료구조이다. 트리는 다음과 같은 특징들을

code-lab1.tistory.com

 

 

[자료구조] 이진탐색트리(Binary Search Tree)의 개념, 이해 | C언어 이진탐색트리 구현

이진탐색트리(Binary Search Tree)이란? 이진탐색트리란 다음과 같은 특징을 갖는 이진트리를 말한다. ( #이진트리 - 각 노드의 자식 노드가 최대 2개인 트리) 1. 각 노드에 중복되지 않는 키(key)가 있다

code-lab1.tistory.com

 

레드-블랙 트리 삽입 과정

위 설명만 보고는 레드-블랙 트리가 무엇인지 감이 쉽게 오지 않을 것이다.

레드-블랙 트리를 쉽게 이해하려면, 예시를 들어 이해하는 게 가장 쉽다.

 

Double-Red
[그림 2] Double Red 발생

레드-블랙 트리에 새로운 노드를 삽입할 때 새로운 노드는 항상 빨간색으로 삽입한다. 

이렇게 되면 4번 조건이 위배되는 상황이 발생한다. 즉, 빨간색 노드가 연속으로 2번 나타날 수 있다(Double Red)

 

레드 블랙 트리는 이러한 Double Red 문제를 해결하기 위해 2가지 전략을 사용한다.

Solution of Double Red
[그림 3] Double Red 해결법

앞으로 새로 삽입할 노드를 N(New), 부모 노드를 P(Parent), 조상 노드를 G(Grand Parent), 삼촌 노드를 U(Uncle)라고 하자. 즉, 삼촌 노드는 말 그대로 부모의 형제라고 생각하면 된다. 

 

Double Red가 발생했을 때 

  • 삼촌 노드가 검은색이라면 -> Restructuring을 수행하면 된다.
  • 삼촌 노드가 빨간색이라면 -> Recoloring을 수행하면 된다.

Restructuring

Restructuring은 다음 과정을 거친다.

1. 새로운 노드(N), 부모 노드(P), 조상 노드(G)를 오름차순으로 정렬한다.
2. 셋 중 중간값을 부모로 만들고 나머지 둘을 자식으로 만든다.
3. 새로 부모가 된 노드를 검은색으로 만들고 나머지 자식들을 빨간색으로 만든다.

역시 이해가 쉽지 않을 것이다. 예시를 보자.

Restructuring 1step
[그림 4] Restructuring 1단계

위와 같은 상황을 가정하자. Double Red가 발생했는데 삼촌 노드가 검은색이다. 따라서 Restructuring을 수행한다.

먼저 새로운 노드 N과 부모 P, 조상 G를 오름차순으로 정렬한다. 그러면 3이 중간값이 된다.

Restructuring 2step
[그림 5] Restructuring 2단계

따라서 중간값인 3을 부모 노드로 바꾸고 나머지 2와 5를 자식 노드로 바꾼다.

당연히 원래 5의 자식 노드였던 7은 딸려가게 된다. 

Restructuring 3step
[그림 6] Restructuring 3단계

마지막으로 새롭게 부모가 된 3을 검은색으로 바꿔주고 나머지 두 자식인 2, 5의 색을 빨간색으로 바꿔주면 Double Red 문제가 해결된다!!

여기서 많이들 헷갈리는 게 완성된 트리가 규칙 3(모든 리프 노드는 검은색)을 만족하지 않는 것처럼 보일 수 있다. 값이 2인 노드는 자식 노드 NIL 2개를 가지고 있고 그 NIL들이 검은색이라고 생각하면 된다.

Recoloring

Recoloring은 다음과 같은 과정을 거친다.

1. 새로운 노드(N)의 부모(P)와 삼촌(U)을 검은색으로 바꾸고 조상(G)을 빨간색으로 바꾼다.
   1-1. 조상(G)이 루트 노드라면 검은색으로 바꾼다.
   1-2. 조상(G)을 빨간색으로 바꿨을 때 또다시 Double Red가 발생한다면 또다시 Restructuring 혹은 Recoloring을 진행해서 Double Red 문제가 발생하지 않을 때까지 반복한다.

역시 이해가 쉽지 않다. 예시를 보자.

Recoloring step1
[그림 7] Recoloring 1단계

위와 같은 상황을 가정하자. Double Red가 발생했는데 삼촌 노드가 빨간색이다. 따라서 Recoloring을 수행한다.

먼저 부모(P)와 삼촌(U)을 검은색으로 바꾸고, 조상(G)을 빨간색으로 바꾼다.

Recoloring step2
[그림 8] Recoloring 2단계

하지만 루트 노드는 검은색이라는 조건을 지켜야 하므로, 루트 노드를 검은색으로 바꾼다.

이렇게 하면 모든 조건이 지켜지면서 Double Red 문제가 해결된다.

검은색 노드는 2번 나와도 되냐고 묻는다면 Yes이다. 빨간색 노드가 2번 나오면 안 되는 것이다. 

 

Recoloring은 간단해 보이지만 문제는 조상 노드(G)가 루트 노드가 아니면서, 조상 노드(G)가 또다시 Double Red 문제가 발생하는 경우이다.

Recoloring step1
[그림 9] Recoloring

위와 같은 상황을 가정하자. 왼쪽 트리에서 Recoloring을 진행하면 오른쪽 트리가 된다.

이때 조상 노드(G)가 또다시 Double Red가 발생하게 된다.

 

Recoloring step2
[그림 10] Recoloring

Double Red 문제가 발생한 "값이 5인 노드"를 기준으로 다시 한번 살펴보자.

해당 노드의 삼촌(U)이 빨간색이므로 다시 Recoloring을 진행해주면 Double Red 문제를 해결할 수 있다!

만약 해당 노드의 삼촌(U)가 검은색이었다면 Restructuring을 진행해주면 된다.

레드-블랙 트리 예제

제대로 이해했는지 확인해보기 위해 아래와 같은 예제를 수행해보자!

 

Q. 레드-블랙 트리에 순서대로 8, 7, 9, 3, 6, 4, 5, 12를 삽입한 후의 상태를 그리시오.

 

 

답은 아래와 같다!

 

 

 

test
[그림 11] 예제 풀이

그리기 힘들어서 아이패드로 그렸다.

가끔 헷갈리는 사람들이 "삼촌 노드가 없는데??"라고 생각할 수 있다. 

맨 위의 [그림 1]을 보면 모든 리프 노드들은 검은색 NIL 노드인 것을 확인할 수 있다. 

즉, 좀 비어있는 것처럼 보이면 그냥 검은색 노드가 있다고 생각하면 편하다. 

 

예를 들어 위 예제에서 6을 삽입하고 Double Red가 발생한 상황을 보자.

6의 부모인 3은 보이는데, 삼촌이 안 보인다. 이때 삼촌은 NIL 노드(검은색)이다.

따라서 Restructuring을 진행하면 된다.

레드-블랙 트리 시뮬레이터

눈으로 직접 확인해보고 싶다면 아래 사이트를 참고하자.

레드 블랙 트리에 원소를 삽입하는 과정을 확인할 수 있다.

 

https://www.cs.usfca.edu/~galles/visualization/RedBlack.html

 

Red/Black Tree Visualization

 

www.cs.usfca.edu


 

반응형

댓글

Designed by JB FACTORY