[알고리즘] 레드-블랙 트리 이해하기(개념, 삽입 과정)

레드-블랙 트리

자가 균형 이진 탐색 트리(self-balancing binary search tree)로 균형을 유지하기 위해 특정 규칙을 따르는 자료구조입니다.

평균적인 시간복잡도는 탐색, 저장, 삭제 모두 O(log N)입니다.

자가 균형 이진 탐색 트리(self-balancing binary search tree)

 

트리에서 노드의 삽입과 삭제 같은 연산이 일어날 때 자동으로 균형 트리를 유지하는 이진 탐색 트리

 

출처: 위키피디아

 

레드-블랙 트리의 특정 규칙은 다음과 같습니다.

 

1. 각 노드는 레드(빨간색) 또는 블랙(검은색)이다.
2. 루트 노드는 항상 블랙이다.
3. 모든 리프 노드(NIL: null leaf, 자료를 갖지않고 트리의 끝을 나타내는 노드) 는 블랙이다.
4. 레드 노드는 연속해서 두 개 이상 존재할 수 없다. 즉, 레드 노드의 자식 노드는 모두 블랙이어야 한다.
5. 모든 경로에서 루트 노드부터 리프 노드까지의 블랙 노드의 수는 동일해야 한다. 이를 블랙 높이(black depth)라고 한다. 

레드-블랙트리 삽입

레드블랙트리는 삽입 시 항상 레드로 삽입합니다. 이때 항상 레드로 삽입하게 되면 상위 노드가 레드이고, 삽입한 하위 노드도 레드이기 때문에 빨간색 노드가 연달아 두 개가 생기는 현상이 발생합니다. 이것을 Double Red라고 합니다.

Double Red가 발생하면  4번조건을 위반하게 됩니다.

 

레드-블랙트리는 Double Red를 해결하기 위해 2가지 전략을 사용하게 됩니다.

 

조상노드를 G, 부모노드를 P, 삼촌노드를 U, 새로 삽입한 노드를 N이라고 할 때,

삼촌노드가 블랙이면 Restructuring

삼촌노드가 레드면 Recoloring을 진행합니다.

 

 

Restructuring

Restructuring의 과정은 아래와 같습니다.

 

1. N, P, G를 오름차순 정렬합니다.

2. 중간값을 부모로 만들고 나머지 둘을 자식으로 만듭니다.

3. 새 부모가 된 노드는 블랙, 나머지 자식은 레드로 만듭니다.

 

Restructuring 예시

 

 

Recoloring

1. N의 부모P와 U를 검은색으로 바꾸고 G를 빨간색으로 바꿉니다.
2. G가 루트 노드라면 검은색으로 바꿉니다.
3. G를 빨간색으로 바꿨을 때 또다시 Double Red가 발생한다면 다시 Restructuring / Recoloring을 진행해서 같은 문제가 발생하지 않을 때까지 반복합니다.

 

Recoloring 예시

 

 

 

 

 

 

시뮬레이터

시뮬레이터를 통해 직접 눈으로 확인해볼수도 있습니다.

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

Red/Black Tree Visualization

 

 

[참고]

https://ko.wikipedia.org/wiki/%EB%A0%88%EB%93%9C-%EB%B8%94%EB%9E%99_%ED%8A%B8%EB%A6%AC

레드-블랙 트리 - 위키백과, 우리 모두의 백과사전

https://code-lab1.tistory.com/62

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

https://velog.io/@kku64r/rbtree

[자료구조] 레드블랙트리란?