13. Red-Black Trees

높이가 h인 이진 탐색 트리는 모든 기본적인 동적 집합 연산을 O(h) 시간에 할 수 있지만, 트리의 균형이 깨질 경우 성능은 연결 리스트보다 더 좋지 않은 수준이 될 수 있다. 적-흑 트리는 높이를 자동으로 조절함으로써 모든 기본적인 동적 집합 연산이 O(\lg n) 시간 내에 됨을 보장한다.

13.1. Properties of red-black trees

적-흑 트리는 노드마다 색깔 (적색 또는 흑색)을 저장하는 한 개의 비트를 따로 두는 이진 탐색 트리이다. 루트에서 리프까지의 모든 경로간에 색깔 제한을 둠으로써, 적-흑 트리는 다른 경로보다 2배 이상의 길이를 가지는 경로가 없도록 하여 트리가 근사적으로 균형을 맞추도록 보장한다. 트리의 각 노드들은 자식이나 부모가 없을 때에는 NIL 노드로 연결된다. 리프들은 NIL 노드들로만 구성되며 키가 있는 노드들은 내부 노드의 역할만 한다. 적-흑 트리는 다음의 적-흑 특성을 만족해야 한다:

  1. 모든 노드는 적색이거나 흑색이다.
  2. 루트는 흑색이다.
  3. 모든 리프(NIL)은 흑색이다.
  4. 노드가 적색이면 그 노드의 모든 자식들은 흑색이다.
  5. 모든 노드에 대해, 그 노드의 후손이 되는 리프까지의 모든 단순 경로는 같은 수의 흑색 노드를 가진다.

공간 절약을 위해 모든 NIL은 T.nil 하나로 통일한다. 노드에 대해 노드로부터 리프까지의 경로 중 그 노드를 제외한 흑색 노드의 개수를 흑색 높이라 정의하고 bh(x)로 쓴다. 적-흑 트리의 흑색 높이는 그 트리의 루트의 흑색 높이로 정의한다. 이 때 다음의 성립한다.

Lemma. n개의 내부 노드를 가진 적-흑 트리의 높이는 최대 2 \lg (n + 1)이다.

그러므로 적-흑 트리에서는 모든 기본 동적 집합 연산이 O(\lg n) 시간 안에 된다. 적-흑 특성을 유지하기 위해서 트리의 삽입/삭제 연산은 특별한 과정이 필요한데, 뒤에서 이를 다룬다.

13.2. Rotations

TREE-INSERT, TREE-DELETE는 트리의 구조를 바꾸기 때문에 적-흑 특성을 깬다. 때문에 트리 회전을 통해 적-흑 특성을 다시 유지시켜줘야 한다. 좌회전을 노드 x에 대해 수행할 경우 x의 우측 자식은 T.nil이 아니라 가정한다. 마찬가지로, 우회전을 노드 x에 대해 수행할 경우 x의 좌측 자식은 T.nil이 아니라 가정한다. 유사코드는 다음과 같다.

LEFT-ROTATE(T, x)
y = x.right // set y
x.right = y.left // turn y's left subtree into x's right subtree
if y.left ≠ T.nil
    y.left.p = x
y.p = x.p // link x.parent to y
if x.p == T.nil
    T.root = y
elseif x == x.p.left
    x.p.left = y
else
    x.p.right = y
y.left = x // put x on y's left
x.p = y

LEFT-ROTATE와 RIGHT-ROTATE는 모두 O(1) 시간에 수행된다.

13.3. Insertion

적-흑 트리에 노드를 O(\lg n) 시간에 삽입하면서 적-흑 특성을 유지하기 위해서는 조금 다른 삽입 과정이 필요하다.

RB-INSERT(T, z)
y = T.nil
x = T.root
while x ≠ T.nil
    y = x
    if z.key < x.key
        x = x.left
    else
        x = x.right
z.p = y
if y == T.nil
    T.root = z
elseif z.key < y.key
    y.left = z
else
    y.right = z
z.left = T.nil
z.right = T.nil
z.color = RED
RB-INSERT-FIXUP(T, z)

TREE-INSERT와 RB-INSERT는 4가지가 다르다. 첫째로, NIL 대신 T.nil을 쓴다. 둘째로, z.left와 z.right는 T.nil로 세팅된다. 셋째로, z의 색은 적색으로 칠해진다. 넷째로, RB-INSERT-FIXUP으로 적-흑 특성을 유지한다.

RB-INSERT-FIXUP(T, z)
while z.p.color == RED
    if z.p == z.p.p.left
        y = z.p.p.right
        if y.color == RED
           z.p.color = BLACK
           y.color = BLACK
           z.p.p.color = RED
           z = z.p.p
        else if z = z.p.right
               z = z.p
               LEFT-ROTATE(T, z)
           z.p.color = BLACK
           z.p.p.color = RED
           RIGHT-ROTATE(T, z.p.p)
    else
        y = z.p.p.left
        if y.color == RED
           z.p.color = BLACK
           y.color = BLACK
           z.p.p.color = RED
           z = z.p.p
        else if z = z.p.left
               z = z.p
               RIGHT-ROTATE(T, z)
           z.p.color = BLACK
           z.p.p.color = RED
           LEFT-ROTATE(T, z.p.p)
T.root.color = BLACK

RB-INSERT-FIXUP이 불릴 때 적-흑 특성 중 어떤 것이 위반된 상태인가? 특성 1은 유지된다. 특성 3도 유지된다. 새로 삽입된 적색 노드의 자식들은 T.nil이기 때문이다. 특성 5도 유지된다. z가 흑색 감시자 노드를 대체하고, z는 흑색 자식을 갖는 적색 노드이기 때문이다. 그러므로 위반되었을 가능성이 있는 특성은 특성 2, 4인데, 이는 모두 z가 적색으로 칠해졌기 때문에 발생한다. 특성 2는 z가 루트일 때 위반되며, 특성 4는 z의 부모가 루트일 때 위반된다.

RB-INSERT-FIXUP에서 while 루프는 루프 내 반복마다 다음의 루프 불변 조건을 갖는다.

  • z는 적색이다.
  • z.p가 루트이면, z.p는 흑색이다.
  • 위반되는 적-흑 특성은 특성 2나 4 중 하나이다. 특성 2가 위반될 때는 z가 적색이고 루트일 때이며, 특성 4가 위반될 때는 z와 z.p가 모두 적색일 때이다.

RB-INSERT-FIXUP은 적-흑 특성을 올바르게 회복한다.

RB-INSERT의 수행 시간은 얼마인가? 노드가 n개인 적-흑 트리의 높이는 O(\lg n)이므로, RB-INSERT-FIXUP을 제외한 RB-INSERT의 수행 시간은 O(\lg n)이다. RB-INSERT-FIXUP의 경우, while 루프문은 case 2/3이 수행될 때는 종료되고, case 1이 수행될 때는 z가 2층 위로 올라간다. 그러므로 while 문이 수행되는 횟수는 최대 O(\lg n)이다. 그러므로 RB-INSERT의 수행 시간은 O(\lg n)이다.

13.4. Deletion

TRANSPLANT의 적-흑 트리 버전은 다음과 같다.

RB-TRANSPLANT(T, u, v)
if u.p == T.nil
    T.root = v
elseif u == u.p.left
    u.p.left = v
else
    u.p.right = v
v.p = u.p

RB-TRANSPLANT는 TRANSPLANT와 2가지 차이가 있다. NIL 대신 T.nil을 쓰고, v.p = u.p가 조건 없이 수행된다.

RB-DELETE는 다음과 같다.

RB-DELETE(T, z)
y = z
y-original-color = y.color
if z.left == T.nil
    x = z.right
    RB-TRANSPLANT(T, z, z.right)
elseif z.right == T.nil
    x = z.left
    RB-TRANSPLANT(T, z, z.left)
else
    y = TREE-MINIMUM(z.right)
    y-original-color = y.color
    x = y.right
    if y.p == z
        x.p = y
    else
        RB-TRANSPLANT(T, y, y.right)
        y.right = z.right
        y.right.p = y
    RB-TRANSPLANT(T, z, y)
    y.left = z.left
    y.left.p = y
    y.color = z.color
if y-original-color == BLACK
    RB-DELETE-FIXUP(T, x)

RB-DELETE-FIXUP은 다음과 같다.

RB-DELETE-FIXUP(T, x)
while x ≠ T.root and x.color == BLACK
    if x == x.p.left
        w = x.p.right
        if w.color == RED
            w.color = BLACK
            x.p.color = RED
            LEFT-ROTATE(T, x.p)
            w = x.p.right
        if w.left.color == BLACK and w.right.color == BLACK
            w.color = RED
            x = x.p
        else
            if w.right.color == BLACK
                w.left.color = BLACK
                w.color = RED
                RIGHT-ROTATE(T, w)
                w = x.p.right
            w.color = x.p.color
            x.p.color = BLACK
            w.right.color = BLACK
            LEFT-ROTATE(T, x.p)
            x = T.root
    else
        w = x.p.left
        if w.color == RED
            w.color = BLACK
            x.p.color = RED
            RIGHT-ROTATE(T, x.p)
            w = x.p.left
        if w.left.color == BLACK and w.right.color == BLACK
            w.color = RED
            x = x.p
        else
            if w.left.color == BLACK
                w.right.color = BLACK
                w.color = RED
                LEFT-ROTATE(T, w)
                w = x.p.left
            w.color = x.p.color
            x.p.color = BLACK
            w.left.color = BLACK
            RIGHT-ROTATE(T, x.p)
            x = T.root
x.color = BLACK

RB-DELTE의 수행 시간은 얼마인가? n개 노드를 가진 적-흑 트리의 높이는 O(\lg n)이므로, RB-DELETE-FIXUP을 제외한 RB-DELETE의 수행 시간은 O(\lg n)이다. RB-DELETE-FIXUP에서, case 1/3/4는 상수 횟수만큼의 색깔 변경과 최대 3번까지의 트리 회전 이후에 루프를 종료시킨다. case 2는 루프를 반복시키고 노드 x를 한 층 올린다. 그러므로 루프가 반복될 수 있는 횟수는 최대 O(\lg n)이다. 그러므로 RB-DELETE의 수행 시간은 O(\lg n)이다.

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Google photo

Google의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

%s에 연결하는 중