[자료구조] 레드블랙트리

Red Black Tree

• Red Black Tree는 가장 유명하고 많이 사용되는 균형이진 탐색트리입니다.

• Red Black Tree는 Search, Insert, Delete 에 O(log n)의 시간 복잡도가 소요됩니다.

• 동일한 노드의 개수일 때, depth 를 최소화하여 시간 복잡도를 줄이는 것이 핵심 아이디어입니다.

Red Black Tree 특성

1. 각 노드는 Red 또는 Black이라는 색깔을 갖습니다.

2. Root node 의 색깔은 Black입니다.

3. 모든 리프노드들(NIL)은 Black입니다.

4. 어떤 노드의 색깔이 Red라면 두 개의 children 의 색깔은 모두 Black 입니다.

5. 각 노드에 대해서 노드로부터 descendant leaves 까지의 단순 경로는 모두 같은 수의 Black nodes 들을 포함하고 있습니다.

Red Black Tree O(log n) 증명

$v:$ 임의의 노드
$h(v):$ v의 높이
$bh(v):$ v -> Leaf node의 경로상에 존재하는 Black색깔을 갖는 노드 수

• $v$의 서브트리 내부노드 개수 $\ge$ $2^{bh(v)}-1$

  BaseCase: $h(v) = 0, bh(v) =0$

  Hypothesis: $h(v) \le k$, $v$의 서브트리 내부노드 개수 $\ge$ $2^{bh(v)}-1$

  Induction

  $h(v) = k+1$ 성립함 증명

  • $h(w),h(z) \le k$ ($v$의 자식노드를 각각 $w$,$z$라 명명)
  • $v$의 서브트리 내부 노드 개수 $\ge$ $2^{bh(w)} - 1 + 2^{bh(z)} - 1 +1$
  • $bh(w),bh(z) = \begin{cases} bh(v)\\bh(v)-1\end{cases}$ $\iff$ $bh(w),bh(z) \ge bh(v)-1$
  • $v$의 서브트리 내부노드 개수 $\ge$ $2^{bh(v)} -1 = 2\times2^{bh(v)-1}-1$

• $bh(r)$ $\ge$ $h/2$, $r=$루트 노드

  • r의 서브트리의 내부노드 개수 $\ge$ $2^{bh(r)} - 1= 2^{h/2} -1 (\because 4번특성)$

  • $n \ge 2^{h/2}-1$, n: 노드의 수

  • $2log2(n+1) \ge h$

  $\therefore\ h=o(log2n)$