Red-Black Tree

- 자가 균형 이진 트리(self-balancing binary tree) <- 이진 트리의 특수한 형태

- 이진 탐색 트리의 '자신이 가진 자료는 자신보다 오른쪽에 위치한 subtree가 가지고 있는 자료보다 작거나 같고, 자신보다 왼쪽에 위치한 subtree가 가지고 있는 모든 자료보다 크거나 같다' 라는 조건을 만족한다.

- 따라서 특정 값을 빠르게 찾아낼 수 있다.

 

- 트리에 n개의 원소가 있을 때 O(log n)의 시간복잡도로 삽입, 삭제, 검색을 할 수 있다.

- 리프 노드는 비어있고, 자료를 가지고 있지 않다.

 

- worst-case guarantees (최악의 경우에도 일정한 실행 시간을 보장함)

- 실시간 처리와 같은 실행시간이 중요한 경우에 유용하게 쓰인다.

- 특히 함수형 프로그래밍에서 유용하다. -> 연관 배열이나 집합(set)을 내부적으로 구현할 수 있다.

 

 

Red-Black Tree의 특성(Properties)

1. 노드는 레드 혹은 블랙 중의 하나이다.
2. 루트 노드는 블랙이다.
3. 모든 리프 노드들(NIL)은 블랙이다.
4. 레드 노드의 자식노드 양쪽은 언제나 모두 블랙이다. (즉, 레드 노드는 연달아 나타날 수 없으며, 블랙 노드만이 레드 노드의 부모 노드가 될 수 있다)
5. 어떤 노드로부터 시작되어 그에 속한 하위 리프 노드에 도달하는 모든 경로에는 리프 노드를 제외하면 모두 같은 개수의 블랙 노드가 있다.

4번 특성에 의하면

- 블랙 노드는 연속해서 나타나도 된다.

 

- 루트 노드부터 가장 먼 리프노드 경로까지의 거리 < (가장 가까운 리프노드 경로까지의 거리) * 2

  - 최단 경로는 모두 블랙 노드

  - 최장 경로는 블랙/레드 노드가 번갈아 나타나는 부분

  - 5번에 의하면, 블랙 노드의 수가 같기 때문이다.

 

   => 레드-블랙 트리는 개략적(roughly)으로 균형이 잡혀 있다(balanced)

   => 삽입, 삭제, 검색시 최악의 경우(worst-case)에서의 시간복잡도가 트리의 높이(또는 깊이)에 따라 결정된다

   => 보통의 이진 탐색 트리에 비해 효율적

 

Double Red를 해결하기

- 노드를 추가하면 무조건 레드 노드가 추가되는데, 그렇게 되면 4번 규칙(레드 노드가 번갈아서 나타나면 안됨)을 위배하게 된다.

이를 방지하기 위한 두가지 방법은 Restructuring, Recoloring이 있다.

 

Restructuring

- Uncle Node(Parent Node 옆)이 블랙 노드일 때

- 이 경우 Uncle Node는 Leaf Node인 null node(black)이 됨

- 말 그대로 구조를 바꾼다는 의미

- 8, 7, 6 노드 사이에 rotation을 해 준다.

- Restructuring 자체의 시간복잡도는 O(1)이지만, 삽입할 노드가 들어갈 위치를 찾아 해당 노드를 삽입한 뒤 Restructuring이 일어나므로 총 수행시간은 O(logn)

 

Recoloring

- Uncle Node(Parent Node 옆)이 블랙 노드일 때

- 4를 추가하게 되면 Double Red 발생하게 된다.

- Uncle Node(Parent Node 옆의 노드, 즉 '2' 노드)가 레드 노드이므로 색깔을 리버스해준다.

- 루트 노드는 블랙 노드여야 하므로 레드 -> 블랙으로 바꿔준다.

 

- Recoloring 자체의 시간복잡도는 O(1)이지만, 삽입할 노드가 들어갈 위치를 찾아 해당 노드를 삽입한 뒤 Recoloring이 일어나므로 총 수행시간은 O(logn)

 

 

참고--

 

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

Red/Black Tree Visualization

이 사이트에서 실제로 red-black tree를 만들어 볼 수 있다.

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

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

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

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

 

https://www.geeksforgeeks.org/red-black-tree-set-1-introduction-2/

Red-Black Tree | Set 1 (Introduction) - GeeksforGeeks

http://kocw-n.xcache.kinxcdn.com/data/document/2021/konyang/choijinmyung0121/7-4.pdf