문서 보기문서 편집수정 내역 레드-블랙 트리 (덤프버전으로 되돌리기) [[분류:자료구조]] [include(틀:이론 컴퓨터 과학)] [목차] == 개요 == 레드-블랙 트리는 자가 균형 이진 탐색 [[트리(그래프)|트리]]의 일종이다. == 특성 == 레드-블랙 트리의 각 노드는 레드 또는 블랙의 색상을 가지고 있다. 구현의 용이성을 위해, 모든 노드는 자식이 없는 부분에 NIL이라는 가상적인 노드를 자식으로 갖는다고 가정한다. NIL은 블랙이다. 이진 탐색 트리에 다음의 조건을 추가하면 레드-블랙 트리가 된다. 1. 노드는 레드 또는 블랙이다. 1. 루트 노드는 블랙이다. 1. 모든 리프 노드는 블랙이다. 1. 레드 노드의 자식은 모두 블랙이다. (루트로부터 리프 노드까지의 경로에 레드 노드가 연이어 올 수 없다.) 1. 어떤 노드에서 리프 노드까지의 모든 경로에는 같은 수의 블랙 노드가 있다. 위 조건으로부터, 루트로부터 가장 긴 경로가 가장 짧은 경로의 길이의 두 배를 넘지 않는다. 이를 개략적으로 균형이 잡혀 있다(roughly balanced)고 한다. == 시간 복잡도 == 삽입, 탐색, 삭제 모두 최악의 경우 O(log n)의 시간 복잡도를 갖는다. 기존 이진탐색트리에서 삽입과 삭제에서 최악의 경우 O(n)의 시간 복잡도를 갖는것을 보완하기 위해 AVL트리가 만들어지고, 그 AVL트리를 더 보완하기 위해 레드-블랙트리가 개발되었다. == 삽입 == 일반적인 이진 탐색 트리에 삽입하는 것처럼 한 후, 새 노드(N)을 레드로 칠한다. 이때 4가지 경우로 나뉜다. 1. N이 루트 노드이다. 1. N의 부모 노드(P)가 블랙이다. 1. P가 레드이고 N의 삼촌(U)이 레드이다. 1. P가 레드이고 U가 블랙이다. === 경우 1 === N이 루트 노드인 경우이다. 조건 2[*A 루트 노드는 블랙이다.]를 만족시키기 위해 N을 검은색으로 칠한다. N이 루트 노드이므로 루트로부터 리프 노드까지의 모든 경로에 블랙 노드가 하나 추가되어, 조건 5[*B 어떤 노드에서 리프 노드까지의 모든 경로에는 같은 수의 블랙 노드가 있다.]는 위반되지 않는다. === 경우 2 === P가 블랙인 경우이다. 이때 트리는 모든 조건을 만족한다. === 경우 3 === P가 레드이고 U가 레드인 경우이다. === 경우 4 === P가 레드이고 U가 블랙인 경우이다. == 삭제 ==캡챠되돌리기