[[분류:자료구조]]
[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가 블랙인 경우이다.
== 삭제 ==