Red-Black Tree (2) 정리 - 이해하기

참고 자료
(위키백과 - 우리 모두의 백과사전, ALGORITHMS - 토마스코멘,찰스 레이서손)
https://ko.wikipedia.org/w/index.php?title=%EB%A0%88%EB%93%9C-%EB%B8%94%EB%9E%99_%ED%8A%B8%EB%A6%AC&action=edit§ion=2

레드 블랙 트리(red-black tree)

• 레드 블랙트리는 이진 검색 트리로서, 각 노드당 한 비트의 추가 기억 공간을 가진다. 이 비트는 노드의 색깔 (Red or Black)을 나타낸다. 레드블랙 트리는 루트에서 리프까지의 경로에 나타내는 노드의 색깔을 제한함으로써 그러한 경로 중 어떠한 것도 다른 것보다 두 배 이상 길지 않음을 보장하게 되는데, 이로써 트리는 근사적 균형을 이룬 트리가 된다.

장점

레드-블랙 트리는 자료의 삽입과 삭제, 검색에서 최악의 경우에도 일정한 실행 시간을 보장한다.

• 레드 블랙트리는 실 사용에 효율적이고, 최악의 경우에도 상당히 우수한 실행 시간을 보인다. n 개의 노드가 있을 때 O(log n)의 시간복잡도로 삽입, 삭제, 검색을 할 수있다.
• AVL 트리는 레드-블랙 트리보다 더 엄격하게 균형이 잡혀 있기 때문에, 삽입과 삭제를 할 때 최악의 경우에는 더 많은 회전(rotation)이 필요하다.
                        단순 이진 탐색 트리
  
                        레드-블랙 트리

(위의 그림을 보면, 레드-블랙 트리가 효율적인 것을 볼 수 있다. 두개의 트리는 각각의 트리에 1,2,3,4,5,6,7 순서로 입력했을 때의 트리의 형태이다. 최악의 경우인 7을 탐색 할 때, 확연한 차이를 보인다.)

++ 레드-블랙 트리는 값이 입력되면, 레드-블랙 트리의 특성에 만족시키도록 스스로 균형을 잡아가는 과정을 거친다.

레드-블랙 트리(Red-Black Tree)의 특성(조건)

다음의 레드블랙 특성을 만족하는 이진 검색 트리를 레드-블랙 트리라고 한다.

1. 모든 노드는 적색이거나 흑색이다.
2. 루트는 흑색이다.
3. 모든 리프(NIL)는 흑색이다.
4. 노드가 적색이면 그 노드의 자식은 모두 흑색이다.
5. 각 노드로부터 그 노드의 자손인 리프로 가는 경로들은 모두 같은 수의 흑색 노드를 포함한다.

5가지 특성에서 주의할 것은 다음과 같다.

• 레드-블랙 트리의 리프노드는 일반적인 트리의 리프노드와 다르다.
  -> 레드-블랙트리는 사실 각각의 단말의 노드에 리프(NIL)노드가 붙어있는 형태라고 생각.

• 어떤 노드를 선택하던, 선택된 노드에서 리프(NIL)에 도달하는 모든 경로에서 마주치는 흑색노드의 개수는 동일하다. (자신, NIL 제외)
  예) 4번 노드에서 리프로 가는 모든 경로를 살펴보면,
  -> 4 - 3(흑) - NIL
  -> 4 - 6(흑) - 5 - NIL
  -> 4 - 6(흑) - 7 - NIL
  ---------> 모두 흑색노드를 한번 마주친다. --> *흑색높이(black height) = 1
• 적색 노드는 연달아 나타날 수 없으며, 흑색 노드만이 적색 노드의 부모 노드가 될 수 있다.
• 4번 특성에 의해, 최단 경로는 모두 블랙 노드로만 구성되어 있다고 했을 때, 최장 경로는 블랙 노드와 레드 노드가 번갈아 나오는 것이 될 것이다. 5번 속성에 따라서, 모든 경로에서 블랙 노드의 수가 같다고 했기 때문에 존재하는 모든 경로에 대해 최장 경로의 거리는 최단 경로의 거리의 두 배 이상이 될 수 없다.

정리 해보면, 단순 이진탐색트리에서 추가된 레드-블랙 트리의 5가지 특성을 바탕으로, 이를 만족시키기 위해 트리가 스스로 균형을 잡는 과정을 거친다. 따라서 단순 이진탐색 트리에 비해 효율적인 것이다. (height 가 낮아짐.)

.