레드-블랙 트리

이 문서는 Red-Black Tree(으)로 검색해도 들어올 수 있습니다.
[접기]

목차



1. 개요


레드-블랙 트리는 각각의 노드가 레드블랙 속성을 가지고 있는 이진 탐색 트리이다.



2. 특성


레드-블랙 트리는 다음의 조건을 만족해야 유용한 레드-블랙 트리가 된다.
  1. 노드는 레드 혹을 블랙 중의 하나이다.
  2. 모든 리프 노드는 블랙이다.
  3. 레드 노드의 자식 노드는 둘 다 블랙이다.
  4. 어떤 노드에서 시작해 리프 노드에 도달하는 모든 경로에는 같은 개수의 블랙 노드가 있다.
  5. 루트 노드는 블랙이다.

3. 용어



4. 장점


레드-블랙 트리는 최대 $ \log_2 {n} + 1 $의 깊이를 가지므로, 이진 탐색 트리가 한 쪽으로 치우지면 최대 $ O(N) $의 시간복잡도를 가질 수 있다는 단점을 해결할 수 있다. 이 때문에 자료의 삽입과 삭제, 검색에서 최악의 경우에도 $ O(\log {n}) $을 보장한다. C++ STL의 {{{set}}}과 같은 구조들도 내부적으로 레드-블랙 트리를 사용한다.

5. 동작


5.1. 회전



이진 트리의 특성은 유지되지만, {{{x}}}와 {{{y}}}가 내부 노드인 경우에만 회전시킬 수 있다. 그렇지 않으면 {{{null}}} 노드가 자식을 갖게 되기 때문이다.


분류 알고리즘