[자료구조] red-black tree

May 23, 24

red black tree

binary search tree의 단점(unbalanced)을 보완한 balanced(self-balancing) binary search tree이고, 다음 속성을 이용해 삽입, 검색, 제거를 모두 $log(n)$의 시간복잡도로 수행한다.

노드 색상 : 각 노드는 빨간색 또는 검은색
루트 속성 : 루트는 항상 검은색
리프 속성 : 모든 리프 노드(nil)는 검은색
Red 속성 : red 노드는 red 자식을 가질 수 없음(어떤 경로에서든 두 개의 연속된 red 노드는 불가)
Black 속성 : 노드에서 그 하위 리프 노드까지의 모든 경로에는 동일한 수의 블랙 노드가 있습니다.

이러한 속성은 루트에서 리프까지의 가장 긴 경로가 최단 경로의 두 배를 넘지 않도록 하여 트리의 균형과 효율적인 성능을 유지

연산의 종류

search

binary search tree와 동일

rotate

left rotate

$x$ 노드에 left rotate:

$y$를 $x$의 오른쪽 자식으로 설정
$y$ 의 왼쪽 하위 트리를 $x$ 의 오른쪽 하위 트리 로 이동
$x$ 및 $y$ 의 부모를 업데이트
$x$ 대신 $y$를 가리키도록 $x$ 의 부모를 업데이트
$y$ 의 왼쪽 자식을 $x$ 로 설정
$x$ 의 부모를 $y$ 로 업데이트

right rotate

$x$ 노드에 right rotate:

$y$를 $x$의 왼쪽 자식으로 설정
$y$의 오른쪽 하위 트리를 $x$의 왼쪽 하위 트리로 이동
$x$ 및 $y$의 부모를 업데이트
$x$ 대신 $y$를 가리키도록 $x$의 부모를 업데이트
$y$ 의 오른쪽 자식을 $x$로 설정
$x$ 의 부모를 $y$로 업데이트

insert

새로 삽입한 노드를 $Z$라고 한다. 새로 삽입한 노드는 빨간색으로 칠한다.

4가지 scenario가 있다.

$Z$가 root

검은색으로 recolor(red-black tree의 속성)
$Z$의 uncle(Z의 부모 노드의 형제 노드)이 빨간색 (uncle이 존재하지 않으면 black으로 침)
$Z$의 uncle이 검은색, $Z$와 $Z$의 부모, $Z$의 부모의 부모가 triangle
$Z$의 uncle이 검은색, $Z$와 $Z$의 부모, $Z$의 부모의 부모가 line

delete

transplant

$v$노드를 $u$노드의 자리로 옮기는 subtree를 이동시키는 역할을 하는 연산

delete

case 1

# case 1
if z.left == self.NIL:
    x = z.right 
    self.transplant(z, z.right)

case 2

# case 2
elif z.right == self.NIL:
    x = z.left
    self.transplant(z, z.left)

case 3

# case 3
else:
    y = self.minimum(z.right)
    y_orig_color = y.color
    x = y.right 
    
    if y.p == z:
        x.p = y
    else:
        self.transplant(y, y.right)
        y.right = z.right
        y.right.p = y
    
    self.transplant(z, y)
    y.left = z.left 
    y.left.p = y 
    y.color = z.color 

*after delete

if y_orig_color == BLACK:
    self.delete_fixup(x)

delete fix-up

type 1

# type 1
if w.color == RED:
    w.color = BLACK
    x.p.color = RED
    self.left_rotate(x.p)
    w = x.p.right

type 2

# type 2
if w.left.color == BLACK and w.right.color == BLACK:
    w.color = RED 
    x = x.p 

type 3

# type 3
if w.right.color == BLACK:
    w.left.color = BLACK
    w.color = RED
    self.right_rotate(w)
    w = x.p.right

type 4

# type 4
w.color = x.p.color 
x.p.color = BLACK 
w.right.color = BLACK 
self.left_rotate(x.p)
x = self.root

Code

from collections import deque

BLACK = True
RED = False

class Node:
    def __init__(self, key):
        self.key = key
        self.p = None # parent
        self.color = RED
        self.left = None
        self.right = None

    def print_color(self):
        if self.color == BLACK:
            return '(b)'
        return '(r)'


class RedBlackTree:
    def __init__(self):
        self.NIL = Node(99999) # arbitrary value
        self.NIL.color = BLACK
        self.NIL.left = None
        self.NIL.right = None
        self.root = self.NIL

    # O(1)
    def left_rotate(self, x):
        y = x.right
        x.right = y.left 

        if y.left != self.NIL:
            y.left.p = x
        
        y.p = x.p 

        if x.p is None:
            self.root = y
        elif x == x.p.left:
            x.p.left = y
        else:
            x.p.right = y 

        y.left = x 
        x.p = y

    # O(1)
    def right_rotate(self, x):
        y = x.left 
        x.left = y.right 

        if y.right != self.NIL:
            y.right.p = x

        y.p = x.p 

        if x.p is None:
            self.root = y 
        elif x == x.p.right:
            x.p.right = y 
        else:
            x.p.left = y 

        y.right = x 
        x.p = y

    # O(logn) total
    def insert(self, key):
        z = Node(key)
        z.left = self.NIL
        z.right = self.NIL

        y = None 
        x = self.root
        
        while x != self.NIL:
            y = x
            if z.key < x.key:
                x = x.left 
            else:
                x = x.right 
        
        z.p = y 
        if y == None:
            self.root = z 
        elif z.key < y.key: 
            y.left = z 
        else:
            y.right = z

        self.insert_fixup(z)

    # O(logn)
    def insert_fixup(self, z):
        while z.p and 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 
                        self.left_rotate(z)
                    z.p.color = BLACK
                    z.p.p.color = RED 
                    self.right_rotate(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 
                        self.right_rotate(z)
                    z.p.color = BLACK
                    z.p.p.color = RED 
                    self.left_rotate(z.p.p)
            if z == self.root:
                break
        self.root.color = BLACK

    # O(logn) total
    def delete(self, k):
        z = self.search(k)

        if z == self.NIL:
            return "Key not found!"

        y = z
        y_orig_color = y.color 
        
        # case 1
        if z.left == self.NIL:
            x = z.right 
            self.transplant(z, z.right)
        # case 2
        elif z.right == self.NIL:
            x = z.left
            self.transplant(z, z.left)
        # case 3
        else:
            y = self.minimum(z.right)
            y_orig_color = y.color
            x = y.right 
            
            if y.p == z:
                x.p = y
            else:
                self.transplant(y, y.right)
                y.right = z.right
                y.right.p = y
            
            self.transplant(z, y)
            y.left = z.left 
            y.left.p = y 
            y.color = z.color 
        
        if y_orig_color == BLACK:
            self.delete_fixup(x)

    # O(logn)
    def delete_fixup(self, x):
        while x != self.root and x.color == BLACK:
            if x == x.p.left:
                w = x.p.right
                # type 1
                if w.color == RED:
                    w.color = BLACK
                    x.p.color = RED
                    self.left_rotate(x.p)
                    w = x.p.right
                # type 2
                if w.left.color == BLACK and w.right.color == BLACK:
                    w.color = RED 
                    x = x.p 
                else:
                    # type 3
                    if w.right.color == BLACK:
                        w.left.color = BLACK
                        w.color = RED
                        self.right_rotate(w)
                        w = x.p.right
                    # type 4
                    w.color = x.p.color 
                    x.p.color = BLACK 
                    w.right.color = BLACK 
                    self.left_rotate(x.p)
                    x = self.root
            else:
                w = x.p.left
                # type 1
                if w.color == RED:
                    w.color = BLACK
                    x.p.color = RED
                    self.right_rotate(x.p)
                    w = x.p.left
                # type 2
                if w.right.color == BLACK and w.left.color == BLACK:
                    w.color = RED 
                    x = x.p 
                else:
                    # type 3
                    if w.left.color == BLACK:
                        w.right.color = BLACK
                        w.color = RED
                        self.left_rotate(w)
                        w = x.p.left
                    # type 4
                    w.color = x.p.color 
                    x.p.color = BLACK 
                    w.left.color = BLACK 
                    self.right_rotate(x.p)
                    x = self.root
        x.color = BLACK

    # O(1)
    def transplant(self, u, v):
        if u.p == None:
            self.root = v
        elif u == u.p.left:
            u.p.left = v 
        else:
            u.p.right = v
        v.p = u.p 

    # O(h) = O(logn) for RB trees
    def minimum(self, x):
        while x.left != self.NIL:
            x = x.left
        return x

    # O(h) = O(logn) for RB trees
    def search(self, k):
        x = self.root
        while x != self.NIL and k != x.key:
            if k < x.key:
                x = x.left
            else:
                x = x.right
        return x

    # simple level-order tree traversal
    def print_tree(self, print_color=False):
        queue = deque()
        queue.append(self.root)

        while(queue):
            node = queue.popleft()

            if print_color:
                print(f'{node.key}{node.print_color()}', end=' ')
            else:
                print(node.key, end=' ')

            # don't add NIL nodes
            if node.left != self.NIL:
                queue.append(node.left)
            if node.right != self.NIL:
                queue.append(node.right)


def make_larger_tree():
    RB = RedBlackTree()
    RB.insert(8)
    RB.insert(5)
    RB.insert(15)
    RB.insert(12)
    RB.insert(19)
    RB.insert(9)
    RB.insert(13)
    RB.insert(23)
    return RB


# ignoring color, just demonstrating rotation
def rotations_video():    
    print('\n-- ROTATIONS VIDEO --')
    RB = RedBlackTree()
    RB.insert(5)
    RB.insert(2)
    RB.insert(10)
    RB.insert(8)
    RB.insert(12)
    RB.insert(6)
    RB.insert(9)
    RB.print_tree()

    print('\n\n-- After left rotation --')
    five = RB.search(5)
    RB.left_rotate(five)
    RB.print_tree()

    print('\n\n-- After right rotation --')
    ten = RB.search(10)
    RB.right_rotate(ten)
    RB.print_tree()


def insertions_video():
    RB = RedBlackTree()

    print('\n\n-- INSERTIONS VIDEO, after case 0 --')
    RB.insert(15)
    RB.print_tree(True)

    print('\n\n-- Insert 5 --')
    RB.insert(5)
    RB.print_tree(True)

    print('\n\n-- Insert 1 (case 3) --')
    RB.insert(1)
    RB.print_tree(True)

    print('\n\n-- Move to larger tree --')
    RB = make_larger_tree()
    RB.print_tree(True)

    print('\n\n-- Insert 10 (case 1, 2, and 3) --')
    RB.insert(10)
    RB.print_tree(True)


def deletions_video():
    print('\n\n-- DELETIONS VIDEO --')
    RB = make_larger_tree()
    RB.insert(10)
    RB.print_tree(True)

    print('\n\n-- Delete 19 (case 1) --')
    RB.delete(19)
    RB.print_tree(True)

    print('\n\n-- Insert 1 --')
    RB.insert(1)
    RB.print_tree(True)

    print('\n\n-- Delete 5 (case 2) --')
    RB.delete(5)
    RB.print_tree(True)

    print('\n\n-- Delete 12 (case 3) --')
    RB.delete(12)
    RB.print_tree(True)


def main():
    # https://youtu.be/95s3ndZRGbk
    rotations_video()

    # https://youtu.be/A3JZinzkMpk
    insertions_video()

    # https://youtu.be/lU99loSvD8s | https://youtu.be/iw8N1_keEWA
    deletions_video()

main()

reference: