[CLRS] [13-2] Red-Black Tree

1. Red-Black Tree?

- Red-Black Tree는 균형 이진 탐색 트리(BBST)의 한 종류로, 삽입과 삭제 연산 후에도 트리가 균형상태를 유지

- 이진 탐색 트리의 시간복잡도를 O(log n)으로 보장함

- 각 노드에 색깔 속성을 추가하여, BBST를 만족하도록 트리를 유지함

- 현재 포스팅에선 RB-Tree을 구현하진 않을 것이고, 그 다음 포스팅 LLRB Tree을 설명할 때 그때 구현하고자 한다.

2. RBTree의 특징

I) 노드는 Red or Black이다.

II) Root Node는 항상 Black이다.

III) Red 노드의 자식 노드는 모두 Black이다.

--> No Double Red

IV) 모든 leaf node는 모드 Black이다.

V) Root에서 left node까지의 Black의 수는 모두 같다.

 

 

3. Insert

- 현 포스팅에선 삽입 메소드만 생각하기로 하자.

- 삭제 메소드도 삽입 메소드와 마찬가지로 생각하면 되기에 하나만 제대로 알면 된다.

- 우선 RB-Tree에 삽입을 할 때, 중요한 점은 RBTree의 특징을 위반하지 않게 삽입을 해야한다는 것이다.

- 이에 대해 자세히 알아보자. (삽입할 때의 노드의 색은 무조건 빨강이다.)

3.1. Recoloring

- Recoloring은 다음과 같은 절차를 거친다.

"""

1. 삽입하고자 하는 노드의 부모와 삼촌의 노드 색이 둘다 Red라면, 부모와 삼촌 노드를 Black으로 바꾼다.

그 후 조상 노드를 Red으로 바꾼다.

 

예외)

- 조상 노드가 root node라면 그 조상노드는 검정색으로 바꾼다.

- 조상노드를 Red로 변경했을 때, Double Red가 발생한다면 Restructure or Recoloring을 진행

"""

 

3.2. Restructure

- Restructure은 다음과 같은 절차를 거친다.

'''

1. 삽입하고자 하는 노드, 부모노드, 조상노드를 오름차순으로 정렬한다.

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

3. 새로 부모가 된 노드를 검은색으로 만들고 나머지 자식들을 빨간색으로 만든다.

 

cf)

- AVL에서 했던 Restructure과 유사한 것이라고 생각하면 편하다.

'''

 

4. Reference

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

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