9. 레드 블랙 트리

1. 레드 블랙 트리

- 이진 검색 트리에서 계속해서 높은 값을 넣을경우 트리의 균형이 망가진다

- 최악의경우 Big-O(n)의 시간을 가지게된다

- 이러한 일을 방지하기 위해서 rebalance를 해줘야하고 레드 블랙 트리는 rebalance를 해주는 트리 중 하나 이다

2. 레드 블랙 트리 의 조건

- 각 노드는 Red or Black 이라는 색깔을 갖는다

- Root Node의 색은 Black이다

- null node를 포함한 각 leaf node는 black 이다

- 어떠한 노드의 색이 red라면 children의 색은 모두 black이다 = 빨간색 노드는 연속해서 나올 수 없다

- root node에서 어떠한 리프 노드 사이에는 똑같은 black 노드의 수를 가진다

3. 레드 블랙 트리 의 삽입

- 이진 검색 트리의 특성을 유지하면서 노드를 삽입하고 삽인된 노드의 색은 RED로 지정한다.

- Red로 지정하는 이유는 Black-Height변견을 최소화하기 위함이다

- 레드 블랙 트리에서 삽입의 경우는 5 가지

- Rotate

- Right Rotate

- 좌측에 있던 자식노드를 부모 노드로 변경한 뒤, 왼쪽 자식노드의 오른쪽 자식노드를 부모의 왼쪽 자식으로 연결한다.

- Left Rotate

- 우측에 있던 자식 노드를 부모 노드로 변경한 뒤, 오른쪽 자식노드의 왼쪽 자식 노드를 부모의 오른쪽 자식으로 연결한다.

- LL (1)

- 부모 노드(90) 에서 자식 노드( 80) L, 할아버지 노드(100)에서 부모 노드(90)의 방향 L

- Right rotate 진행

- RR (2)

- LL의 반대

- Left Rotate 실행

- LR (3)

- 부모 노드(110)에서 자식 노드(105)의 방향 L, 할아버지 노드(100)에서 부모 노드(110)로 방향 R 

- Right rotate 실행

- Left rotate 실행

- RL (4)

- LR의 반대 

- Recolor(5)

- 삼촌 노드(부모 노드의 형제)와 부모 노드 둘다 Red라면 삼촌 노드와 부모 노드의 색을 Black으로 만들고 할아버지 노드를 Red로 만든다.(할아버지 노드가 Root Node라면 Black)

3. 레드 블랙 트리 의 삭제

- 레드 블랙 트리의 삭제는 6 가지 경우가 있다

- Case(1) 

- 삭제 노드 N 루트 노드 일때 

- 모든 경로에서 하나의 Black Node를 삭제했고 루트 노드는 Black Node라 모든 특성 보존

- Case(2)

- 부모 노드가 Black Node, 형제 노드가 Red, 형제 노드의 자식이 Black 이거나 없을때

- 형제 노드를 Roate를 하고 Case(1) 부터 다시 시작한다

- Case(3)

- 부모 노드가 Black Node, 형제 노드 Black Node, 형제 노드의 자식이 Black 이거나 없을때

- 형제 노드의 색을 Red 변환 하고 Case(1) 부터 다시 시작한다 

- Case(4)

- 부모 노드 Red, 형제 노드 Black, 형제 노드의 자식들이 Red Node가 아닐때

- 형제 노드와 부모 노드의 색을 바꾸고 노드 삭제

- Case(5)

- closer node(형제 노드의 안쪽 노드) Red, out node(형제 노드의 바깥쪽 노드) Black 이거나 없을때

- closer node 를 부모와 형제 노드의 방향에 따라 Rotate 한고 Case6을 진행한다

 

- Case(6)

- 형제 노드 Black, out node가 Red 일때

- 형제 노드를 부모와 형제 노드의 방향에 따라 Rotate 하고 리턴한다

4. 레드 블랙 트리 ADT

- init(self)

- 레드 블랙 트리를 초기화 한다

- insert(self, data)

- 레드 블랙 트리에 데이터를 저장한다.

- rebalance(self, node)

- 삽입된 노드를 레드 블랙 트리의 조건에 따라 rebalance 해준다

- recolor(self, node)

- 삽입된 노드를 레드 블랙 트리의 조건에 따라 recolor를 하고 다시 rebalance를 실행한다.

- find_node(self, data)

-  data 가 트리에 있는지 없는지 확인하고 있으면 data 값을 가진 node를 반환한다.

- _find_in_order_successor(self, node)

- 노드를 삭제 할 때 자식이 있을때 오른쪽 자식의 가장 왼쪽 node를 찾아서 반환한다.

- 오른쪽 자식이 왼쪽 node가 없을때는 오른쪽 자식이 반환된다.

- remove(self, data)

- data를 가진 노드가 있는지 확인한다

- data를 가진 노드가 자식이 있는지 확인하고  _find_in_order_successor()함수를 실행한다.

- _find_in_order_successor()의 리턴 node를 data를 가진 노드에 넣어준다.

- 삭제할 node를 _remove() 함수의 인자로 넘겨준다.

- _remove(self, node)

- node가 root node면 남은 자식을 root node로 교체한다.

- node의 색이 Red 면 remove_node() 함수 실행한다.

- node의 색이 Black 면 remove_black_node() 함수 실행한다.

- remove_black_node(self, node)

- case_1() 함수를 실행하고 리턴된 node를 remove_node() 인자로 넘긴다.

- remove_node(self, node)

- node를 삭제한다

- case_1 ~ 6(self, node)

- node가 삭제 되었을때 레드 블랙 트리의 조건에 맞게 트리를 rebalance 한다.

- left_rotate(self, node, recolor=None), right_rotate(self, node, recolor=None)

- node를 left rotate시키고 recolor true 이면 node의 색을 Black 변환하고 자식들을 Red로 변환한다.

 

class Node:
    def __init__(self, data):
        self.data = data
        self.left = self.right = self.parent = None
        self.color = True


class RedBlackTree:
    null_node = Node(data=None)
    null_node.color = False

    def __init__(self):
        self.root_node = None

    def insert(self, data):
        if not self.root_node:
            self.root_node = Node(data)
            self.root_node.color = False
            self.root_node.right = self.null_node
            self.root_node.left = self.null_node
            return True
        node = self.root_node
        while node:
            if data > node.data:
                if not node.right.data:
                    node.right = Node(data)
                    node.right.parent = node
                    node = node.right
                    break
                else:
                    node = node.right
            else:
                if not node.left.data:
                    node.left = Node(data)
                    node.left.parent = node
                    node = node.left
                    break
                else:
                    node = node.left
        node.right = self.null_node
        node.left = self.null_node
        self.rebalance(node)
        return True

    def rebalance(self, node):
        if self.root_node == node or not node or node.parent == self.root_node\
                or (not node.color or not node.parent.color):
            return
        parent = node.parent
        g_parent = parent.parent
        parent_dir = 'L' if g_parent.data > parent.data else 'R'
        node_dir = 'L' if parent.data > node.data else 'R'
        uncle = g_parent.right if parent_dir == 'L' else g_parent.left
        rotate_dir = node_dir + parent_dir
        if uncle == self.null_node or not uncle.color:
            if rotate_dir == 'LL':
                self.right_rotate(parent, recolor=True)
            elif rotate_dir == 'RR':
                self.left_rotate(parent, recolor=True)
            elif rotate_dir == 'LR':
                self.right_rotate(node)
                self.left_rotate(node, recolor=True)
            elif rotate_dir == 'RL':
                self.left_rotate(node)
                self.right_rotate(node, recolor=True)
        else:
            self.recolor(g_parent)

    def recolor(self, g_parent):
        g_parent.left.color = False
        g_parent.right.color = False

        if g_parent != self.root_node:
            g_parent.color = True
        return self.rebalance(g_parent)

    def find_node(self, data):
        def _find_node(node, data):
            if not self.root_node or not node.data:
                return None

            if node.data > data:
                return _find_node(node.left, data)
            elif node.data < data:
                return _find_node(node.right, data)
            else:
                return node

        node = _find_node(self.root_node, data)
        return node

    def _find_in_order_successor(self, node):
        right_node = node.right
        left_node = right_node.left
        if not left_node.data:
            return right_node
        while left_node.left.data:
            left_node = left_node.left
        return left_node


    def remove(self, data):
        remove_node = self.find_node(data)
        if remove_node is None:
            return
        if remove_node.right.data and remove_node.left.data:
            successor = self._find_in_order_successor(remove_node)
            remove_node.data = successor.data
            remove_node = successor
        self._remove(remove_node)

    def _remove(self, node):
        left_node = node.left
        right_node = node.right
        not_null_child = right_node if not left_node.data else left_node
        if node == self.root_node:
            if not_null_child:
                self.root_node = not_null_child
                self.root_node.parent = None
                self.root_node.color = False
            else:
                self.root_node = None
        elif node.color:
            self.remove_node(node)
        else:
            self.remove_black_node(node)

    def remove_node(self, node):
        if node.data >= node.parent.data:
            node.parent.right = self.null_node
        else:
            node.parent.left = self.null_node

    def remove_black_node(self, node):
        self.case_1(node)
        self.remove_node(node)

    def case_1(self, node):
        if node == self.root_node:
            node.color = False
            return
        self.case_2(node)

    def case_2(self, node):
        parent = node.parent
        sibling, direction = self.get_sibling(node)
        if sibling.color and not parent.color and not sibling.left.color and not sibling.right.color:
            if direction == 'R':
                self.left_rotate(node)
            else:
                self.right_rotate(node)
            parent.color = True
            sibling.color = False
            return self.case_1(node)
        return self.case_3(node)

    def case_3(self, node):
        parent = node.parent
        sibling, _ = self.get_sibling(node)
        if not sibling.color and not parent.color and not sibling.left.color and not sibling.right.color:
            sibling.color = True
            return self.case_1(parent)
        self.case_4(node)

    def case_4(self, node):
        parent = node.parent
        if parent.color:
            sibling, direction = self.get_sibling(node)
            if not sibling.color and not sibling.left.color and not sibling.right.color:
                parent.color, sibling.color = sibling.color, parent.color
                return

        self.case_5(node)

    def case_5(self, node):
        sibling, direction = self.get_sibling(node)
        closer_node = sibling.right if direction == 'L' else sibling.left
        outer_node = sibling.left if direction == 'L' else sibling.right

        if closer_node.color and not outer_node.color and not sibling.color:
            if direction == 'L':
                self.left_rotate(closer_node)
            else:
                self.right_rotate(closer_node)
            closer_node.color = False
            sibling.color = True
        self.case_6(node)

    def case_6(self, node):
        sibling, direction = self.get_sibling(node)
        outer_node = sibling.left if direction == 'L' else sibling.right

        if not sibling.color and outer_node.color:
            parent_color = sibling.parent.color
            if direction == 'L':
                self.right_rotate(sibling)
            else:
                self.left_rotate(sibling)
            sibling.color = parent_color
            sibling.right.color = False
            sibling.left.color = False
            return
        raise Exception('어흑 마이갓!')

    def get_sibling(self, node):
        parent = node.parent
        if node.data >= parent.data:
            sibling = parent.left
            direction = 'L'
        else:
            sibling = parent.right
            direction = 'R'
        return sibling, direction

    def left_rotate(self, node, recolor=None):
        is_root = False
        parent_direction = None
        parent = node.parent
        gparent = node.parent.parent if node.parent.parent else None
        if not gparent:
            is_root = True
        else:
            if gparent:
                if gparent.data < parent.data:
                    parent_direction = True
                else:
                    parent_direction = False
        old_left = node.left
        node.left = parent
        parent.parent = node

        parent.right = old_left
        old_left.parent = parent
        node.parent = gparent

        if is_root:
            self.root_node = node
            self.root_node.color = False
        else:
            if parent_direction is True:
                gparent.right = node
            elif parent_direction is False:
                gparent.left = node

        if recolor:
            node.color = False
            node.right.color = False if node.right == self.null_node else True
            node.left.color = False if node.left == self.null_node else True

    def right_rotate(self, node, recolor=None):
        is_root = False
        parent_direction = None
        parent = node.parent
        gparent = node.parent.parent if node.parent.parent else None
        if not gparent:
            is_root = True
        else:
            if gparent:
                if gparent.data < parent.data:
                    parent_direction = True
                else:
                    parent_direction = False
        old_right = node.right
        node.right = parent
        parent.parent = node

        parent.left = old_right
        old_right.parent = node.parent
        node.parent = gparent

        if is_root:
            self.root_node = node
            self.root_node.color = False
        else:
            if parent_direction is True:
                gparent.right = node
            elif parent_direction is False:
                gparent.left = node

        if recolor:
            node.color = False
            node.right.color = False if node.right == self.null_node else True
            node.left.color = False if node.left == self.null_node else True