이곳은 개발을 위한 베타 사이트 입니다.
기여내역은 언제든 초기화될 수 있으며, 예기치 못한 오류가 발생할 수 있습니다.
기여내역은 언제든 초기화될 수 있으며, 예기치 못한 오류가 발생할 수 있습니다.
레드-블랙 트리
덤프버전 :
분류
1. 개요[편집]
레드-블랙 트리는 자가 균형 이진 탐색 트리의 일종이다.
2. 특성[편집]
레드-블랙 트리의 각 노드는 레드 또는 블랙의 색상을 가지고 있다. 구현의 용이성을 위해, 모든 노드는 자식이 없는 부분에 NIL이라는 가상적인 노드를 자식으로 갖는다고 가정한다. NIL은 블랙이다.
이진 탐색 트리에 다음의 조건을 추가하면 레드-블랙 트리가 된다.
- 노드는 레드 또는 블랙이다.
- 루트 노드는 블랙이다.
- 모든 리프 노드는 블랙이다.
- 레드 노드의 자식은 모두 블랙이다. (루트로부터 리프 노드까지의 경로에 레드 노드가 연이어 올 수 없다.)
- 어떤 노드에서 리프 노드까지의 모든 경로에는 같은 수의 블랙 노드가 있다.
위 조건으로부터, 루트로부터 가장 긴 경로가 가장 짧은 경로의 길이의 두 배를 넘지 않는다. 이를 개략적으로 균형이 잡혀 있다(roughly balanced)고 한다.
3. 시간 복잡도[편집]
삽입, 탐색, 삭제 모두 최악의 경우 O(log n)의 시간 복잡도를 갖는다.
기존 이진탐색트리에서 삽입과 삭제에서 최악의 경우 O(n)의 시간 복잡도를 갖는것을 보완하기 위해 AVL트리가 만들어지고,
그 AVL트리를 더 보완하기 위해 레드-블랙트리가 개발되었다.
4. 삽입[편집]
일반적인 이진 탐색 트리에 삽입하는 것처럼 한 후, 새 노드(N)을 레드로 칠한다.
이때 4가지 경우로 나뉜다.
- N이 루트 노드이다.
- N의 부모 노드(P)가 블랙이다.
- P가 레드이고 N의 삼촌(U)이 레드이다.
- P가 레드이고 U가 블랙이다.
4.1. 경우 1[편집]
N이 루트 노드인 경우이다.
조건 2[A] 를 만족시키기 위해 N을 검은색으로 칠한다.
N이 루트 노드이므로 루트로부터 리프 노드까지의 모든 경로에 블랙 노드가 하나 추가되어, 조건 5[B] 는 위반되지 않는다.
4.2. 경우 2[편집]
P가 블랙인 경우이다.
이때 트리는 모든 조건을 만족한다.
4.3. 경우 3[편집]
P가 레드이고 U가 레드인 경우이다.
4.4. 경우 4[편집]
P가 레드이고 U가 블랙인 경우이다.