레드-블랙 트리(Red-Black Tree)

2021. 8. 26. 23:16

읽기 전

불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
개인적으로 배운 점을 정리한 글입니다.
Python 구현 코드를 첨부한 포스팅이 별로 없어 넣어봤습니다.

Red-Black 트리란?

자가 균형 이진 탐색 트리의 일종으로 AVL 트리와 사용되는 용도가 조금 다르다 AVL 트리는 balance를 엄격히 유지하기에 조회 속도는 빠르나 삽입/삭제 시 balancing 과정으로 인해 속도가 지연된다. 따라서 조회가 빈번히 발생하는 DB에 사용되며 Red-Black Tree는 AVL 트리보다는 balance를 조금 느슨하게 유지하여 적절한 조회 속도를 가져가되 빠른 삽입/삭제를 지원한다. B-Tree, AVL Tree와 마찬가지로 BST의 고질적인 문제인 skewed tree 문제 해결이 가능하다.

레드 블랙 트리의 성질

노드의 색상은 Red 혹은 Black이다.
루트 노드의 색상은 무조건 Black이다.
모든 리프 노드의 색상은 Black이다.
Red 노드의 자식은 모두 Black이다.
- Red 노드가 루트에서 리프까지의 경로에 연속으로 등장할 수 없음을 의미한다.
루트 노드에서 임의의 리프 노드에 이르는 경로에 존재하는 Black 노드의 수는 일정하다.
- Red 노드 + Black 노드의 수는 다를 수 있다.
- 5번 성질로 인해 최단, 최장 경로의 노드 수가 차이가 2배 이상 커지지 않는다.

레드-블랙 트리에서의 리프 노드 : 일반적으로 트리에서의 리프 노드는 가장 하단에 있는 값을 가진 노드라 부르지만 레드-블랙 트리는 가장 하단의 값을 가진 노드(보통 리프 노드라 부르는)의 자식 노드에 Null 값을 줘서 NIL Leaves나 null Leaves라고 부른다.

Data Structure_Red_Black_Tree_001.png

모든 마지막 노드의 양쪽 자식 노드는 NIL Leaf 노드이므로 개념적으로 모든 노드가 가지고 있지만 실제 구현 시 하나의 객체를 참조하게 하면 공간복잡도를 줄일 수 있다.

레드 블랙 트리의 높이

노드 x의 높이 $h(x)$ 는 자신부터 리프 노드까지의 가장 긴 경로에 있는 edge의 개수다.
레드-블랙 트리의 black height = bh는 루트 노드에서 리프 노드까지의 블랙 노드의 개수이고 모든 리프 노드 또한 블랙 노드이기에 카운트에 들어간다. 높이 h인 레드-블랙 트리의 블랙 높이는 $bh \ge \cfrac{h}{2}$ 를 만족한다.(레드-블랙 트리의 성질 조건 4)
루트 노드가 x인 서브트리의 노드의 수는 적어도 2bh(x)−1개를 갖는다.
- $h(x)=0$ 이면 x는 NIL 노드로 $2^0-1=0$ 으로 가정이 성립한다.
- $h(x) >0$ 이고 x는 두 개의 자식을 갖는다고 하자. x의 색상에 따라 x의 자식 노드는 $bh(x)$ , $bh(x) - 1$ 의 높이를 갖는다. 최소한의 관점이므로 $bh(x) - 1$ 이라 하자. 그러면 적어도 x를 루트로 하는 서브 트리는 양쪽에 $2^{bh(x) - 1} - 1$ 개 노드를 갖는 트리가 되고 양 쪽 서브 트리와 x 노드를 포함하면 $2\cdot(2^{bh(x) - 1}-1) + 1 = 2^{bh(x)}- 1$ 가 된다.(귀납적 증명)
n개의 노드를 갖는 레드-블랙 트리의 높이는 h≤2log2(n+1)을 만족한다.
- $n \ge 2^{bh(x)} - 1 \ge 2^{h/2}-1$ 이므로 $2^{h/2} \le n + 1$ 이고 $\cfrac{h}{2}\le log_2{(n + 1)}$ 가 되어 $h\le 2log_2{(n + 1)}$ 이 된다.

레드 블랙 트리의 시간복잡도

Data Structure_Red_Black_Tree_002.png

모든 경우에 대해 최선/최악을 가리지 않고 $O(log\ n)$ 의 시간복잡도는 보여준다. 현존하는 BST 중 가장 안정적으로 여러 SDK나 라이브러리의 검색알고리즘에 쓰인다고 한다.

레드 블랙 트리의 검색(Search)

레드 블랙 트리도 이진 탐색 트리의 일종이기에 검색 연산은 현재 노드보다 크면 우측, 작으면 좌측으로 탐색하면 된다.

python 코드 - 검색파트

 class Node:
    def __init__(self, data):
        self.data = data
        self.parent = None
        self.left = None
        self.right = None
        self.color = "Red"  # Initial color is red
 
class RedBlackTree:
    def __init__(self):
        self.root = None
        self.inserted_node = None
 
    def find(self, data):
        return self._find_data(self.root, data)
 
    def _find_data(self, root, data):
        if root is None or root.data == data:
            return root
        elif root.data >= data:
            return self._find_data(root.left, data)
        elif root.data < data:
            return self._find_data(root.right, data)

레드 블랙 트리의 삽입(Insert)

삽입 과정에서 노드 상태의 변화가 발생하면 경우에 따라 balancing 작업을 수행해야 한다. AVL 트리에서는 rotation만 사용했는데 레드 블랙 트리는 recoloring이 추가되어 recoloring이 불가할 경우 rotation을 구행한다.

Data Structure_Red_Black_Tree_003.png

삼촌 노드가 Red면 : recoloring 수행
삼촌 노드가 Black이면 : rotation 수행 후 recoloring 여부 결정

일반적인 BST 삽입처럼 노드를 삽입하되 색상은 Red로 한다.
만약 삽입한 노드가 루트 노드라면 Black으로 바꾼다.
삽입된 노드 x가 루트 노드가 아니라며 x의 부모가 Red인 경우

3.1 삼촌이 Red인 경우(이중 Red는 불가하므로 조부모 노드가 존재한다면 색상은 Black)
- 부모와 삼촌 노드의 색상을 Black으로 변경
- 조부모 노드의 색상은 Red로 변경
- x를 x의 조부모 노드로 치환하고 2, 3번 과정을 반복
3.2 삼촌이 Black인 경우
- 부모가 조부모의 왼쪽 자식이고 x가 부모의 왼쪽 자식일 때 - LL Case
- 부모가 조부모의 왼쪽 자식이고 x가 부모의 오른쪽 자식일 때 - LR Case
- 부모가 조부모의 오른쪽 자식이고 x가 부모의 오른쪽 자식일 때 - RR Case
- 부모가 조부모의 오른쪽 자식이고 x가 부모의 왼쪽 자식일 때 - RL Case

Python 코드 - 삽입 파트

     def insert(self, data):
        self.root = self._insert_node(self.root, data, None)
        self._balancing(self.inserted_node)
        return
 
    def _insert_node(self, cur, data, parent):
        if cur is None:
            cur = Node(data)
            cur.parent = parent
            self.inserted_node = cur
        else:
            if data < cur.data:
                cur.left = self._insert_node(cur.left, data, cur)
            elif data > cur.data:
                cur.right = self._insert_node(cur.right, data, cur)
        return cur
 
    def _balancing(self, node):
        P = node.parent
        if P is None:  # if node is root node
            node.color = "Black"
        else:  # if node isn't root node
            if P.color == "Red":  # if parent node is red
                G = P.parent  # must exist grandparent
                U = None
                if G.left == P:
                    U = G.right
                elif G.right == P:
                    U = G.left
 
                if U is not None and U.color == "Red":
                    # parent, uncle -> Black, grandparent -> Red
                    P.color, U.color = "Black", "Black"
                    G.color = "Red"
                    # rebalncing from grandparent
                    self._balancing(G)
                else:  # uncle is None or uncle.color is black
                    if P == G.left and P.left == node:  # LL Case
                        G.color, P.color = P.color, G.color
                        self._right_rotate(G)
                    elif P == G.left and P.right == node:  # LR Case
                        self._left_rotate(P)
                        G.color, node.color = node.color, G.color
                        self._right_rotate(G)
                    elif P == G.right and P.right == node:  # RR Case
                        G.color, P.color = P.color, G.color
                        self._left_rotate(G)
                    elif P == G.right and P.left == node:  # RL Case
                        self._right_rotate(P)
                        G.color, node.color = node.color, G.color
                        self._left_rotate(G)

레드 블랙 트리에서의 삭제(Delete)

삽입 연산에서는 삼촌 노드의 색상에 따라 분기문이 나뉘었지만 삭제 연산에서는 형제 노드의 색상에 따라 나뉜다. 삽입 연산에서는 노드 삽입 시 연속된 Red 노드가 문제였으나 삭제 연산에서는 루트에서 리프 노드까지의 블랙 높이가 일정하지 않게 되어 문제가 된다. AVL 트리도 그렇고 레드 블랙 트리도 삭제 연산은 특히 복잡하다.

삭제될 노드 V이고 V의 자식 노드 C가 V를 대체할 노드라고 하자.

일반적인 BST에서의 삭제 연산처럼 접근하여 삭제될 노드를 가르키는 객체를 생성한다.
- 삭제될 노드의 자식이 없거나 1개면 문제가 되지 않지만 2개인 경우 successor 중 가장 작은 값(inorder)를 찾아서 값을 치환한 후 해당 successor가 노드를 삭제하면 전체 대소관계를 해치지 않고 삭제될 노드는 리프 노드이거나 자식 노드가 1개임을 보장할 수 있다.

python 코드 - 삭제 파트(삭제 노드 명시)

     def delete(self, data):
        node = self._get_delete_node(self.root, data)
        if node is None:
            return False
        self._delete_node(node)
        return True
 
    def _get_delete_node(self, node, data):
        if node.data > data:
            return self._get_delete_node(node.left, data)
        elif node.data < data:
            return self._get_delete_node(node.right, data)
        elif node.data == data:
            # check left, right child
            left = node.left
            right = node.right
            if left is not None and right is not None:
                # delete node has both child
                # swap value of minimum successor and delete node
                min_successor = self._find_min_successor(node.right)
                node.data, min_successor.data = min_successor.data, node.data
                return min_successor
            else:
                return node

만약 V나 C들 중 하나가 Red라면 V를 대체할 자식 노드 C의 색상을 Black으로 바꾸고 종료한다.
- 둘 다 Red인 경우는 이중 Red로 존재할 수 없어 생략

만약 V, C가 모두 Black인 경우 V를 대체할 C 노드를 "double black"으로 표기한다. 이후 double black을 single black으로 바꿔야 한다.

3.1 만약 V를 대체할 C 노드가 루트 노드라면 single black으로 바꾸고 종료한다.

전체 bh가 1 감소한 효과

     def _delete_node(self, V):
        C, S = None, None
        P = V.parent
        if V.left is not None:
            C = V.left
        elif V.right is not None:
            C = V.right
        if P is None:
            self.root = None
            return
        elif V == P.left:
            S = P.right
        elif V == P.right:
            S = P.left
        if C is None:
            C = Node(None)  # temporary Node
            C.parent = V
            C.color = "Black"
        if V.color == "Red" or C.color == "Red":
            # if V has child and V or C node color is red
            # make C color black and just delete V
            if P is None:
                self.root = V
            else:
                if C.data is not None:
                    C.parent = P
                    C.color = "Black"
                    if P.left == V:
                        P.left = C
                    elif P.right == V:
                        P.right = C
 
                elif C.data is None:
                    if P.left == V:
                        P.left = None
                    elif P.right == V:
                        P.right = None
                V = C
 
        elif V.color == "Black" and C.color == "Black":
            C.parent = P
            if V == P.left:
                if C.data is None:
                    P.left = None
                else:
                    P.left = C
            elif V == P.right:
                if C.data is None:
                    P.right = None
                else:
                    P.right = C
            V = C
            V.color = "BBlack"
            if P is None:
                V.color = "Black"
                self.root = V
            else:
                # if S and S's child are all black,
                # V's double black mark would be shifted to P
                # so need to make recursive function
                self._delete_balancing(V, P, S)

3.2 C 노드가 루트 노드가 아닐 경우 기존 V의 형제 노드 S의 색상에 따라 분기문이 나뉜다.

a) S 노드 색상이 Black이고 S의 자식 노드 중 적어도 하나가 Red인 경우

S 노드에 대해 rotation 수행
- S가 부모 노드의 좌측 자식이고 S의 좌측 자식 노드가 Red인 경우(Left Left Case) - right(P) rotation
  
  C 노드의 bh가 1 감소했으므로 S의 bh를 감소시키도록 right rotation 수행, 자식노드 r은 Black으로 바꿔서 증가한 우측 bh에 맞춰준다.
- S가 부모 노드의 좌측 자식이고 S의 우측 자식 노드가 Red인 경우(Left Right Case) - left(S), right(P) rotation
  
  S 노드에 대해 left rotation 수행 후 S와 r 노드의 색상을 바꾼다. 이후 LL Case처럼 right rotation을 수행한 뒤 S의 색상을 Black으로 바꾼다.
- S가 부모 노드의 우측 자식이고 S의 우측 자식 노드가 Red인 경우(Right Right Case) - left(P) rotation
  
  LL 케이스를 좌우 반전한 경우다.
- S가 부모 노드의 우측 자식이고 S의 좌측 자식 노드가 Red인 경우(Right Left Case) - right(S), left(P) rotation
  
  LR 케이스를 좌우 반전한 경우다.
b) S 노드의 색상이 Black이고 S의 자식 노드들도 모두 Black인 경우 재귀적으로 recoloring을 수행한다.
- C의 double black을 빼앗아 부모 노드 P에게 주고 S 노드를 Red로 바꾼다. - C 노드의 bh가 1 감소하였으므로 S도 Red로 만들어 bh 균형 유지
- P 노드가 Red였다면 red + double black = single black이 되어 P 노드를 Black으로 바꾸고 종료한다.
- P 노드가 Black이었다면 P 노드가 double black이 되어 처리루틴 3.2로 회귀한다.
c) S 노드의 색상이 Red일 경우
- S가 부모 노드 P의 왼쪽 노드일 경우(Left Case) P를 오른족으로 내리는 right rotation 수행한 후 P와 S의 색상 swap
- S가 부모 노드 P의 오른쪽 노드일 경우(Right Case) P를 왼쪽으로 내리는 left rotation 수행한 후 P와 S의 색상 swap

     rotation과 recoloring을 수행하면 double black 노드인 C 노드에 대해 다시 새로운 현재 상황이 주어지고 처리루틴 3.2로 회귀한다.
 
 
```python
    def _delete_balancing(self, V, P, S):
        S_l, S_r = S.left, S.right
        if S_l is None:
            S_l = Node(None)  # temporary Node
            S_l.parent = S
            S_l.color = "Black"
        if S_r is None:
            S_r = Node(None)  # temporary Node
            S_r.parent = S
            S_r.color = "Black"
        if S.color == "Black" and (S_l.color == "Red" or S_r.color == "Red"):
            if S == P.left and S_l.color == "Red":
                S_l.color = "Black"
                self._right_rotate(P)
            elif S == P.left and S_r.color == "Red":
                S_r.color = "Black"
                self._left_rotate(S)
                self._right_rotate(P)
            elif S == P.right and S_r.color == "Red":
                S_r.color = "Black"
                self._left_rotate(P)
            elif S == P.right and S_l.color == "Red":
                S_l.color = "Black"
                self._right_rotate(S)
                self._left_rotate(P)
        elif S.color == "Black" and S_l.color == S_r.color and S_l.color == "Black":
            V.color = "Black"
            if P.color == "Red":
                P.color = "Black"
                return
            else:
                # if S and all S's child ar black
                # give V's double black to P
                # if P is black, balancing routine for V would be shifted to P
                P.color = "BBlack"
                S.color = "Red"
                PP = P.parent
                if PP and P == PP.left:
                    S = PP.right
                elif PP and P == PP.right:
                    S = PP.left
                if PP is None:
                    S = None
                self._delete_balancing(P, PP, S)
        elif S.color == "Red":
            S.color, P.color = P.color, S.color
            if S == P.left:
                self._right_rotate(P)
            elif S == P.right:
                self._left_rotate(P)
            self._delete_balancing(V, P, S)
 
    def _find_min_successor(self, node):
        if node.left is None:
            return node
        else:
            return self._find_min_successor(node.left)

  
### python 전체 코드
 
```python
class Node:
    def __init__(self, data):
        self.data = data
        self.parent = None
        self.left = None
        self.right = None
        self.color = "Red"  # Initial color is red
 
class RedBlackTree:
    def __init__(self):
        self.root = None
        self.inserted_node = None
 
    def find(self, data):
        return self._find_data(self.root, data)
 
    def _find_data(self, root, data):
        if root is None or root.data == data:
            return root
        elif root.data >= data:
            return self._find_data(root.left, data)
        elif root.data < data:
            return self._find_data(root.right, data)
 
    def insert(self, data):
        self.root = self._insert_node(self.root, data, None)
        self._balancing(self.inserted_node)
        return
 
    def _insert_node(self, cur, data, parent):
        if cur is None:
            cur = Node(data)
            cur.parent = parent
            self.inserted_node = cur
        else:
            if data < cur.data:
                cur.left = self._insert_node(cur.left, data, cur)
            elif data > cur.data:
                cur.right = self._insert_node(cur.right, data, cur)
        return cur
 
    def _balancing(self, node):
        P = node.parent
        if P is None:  # if node is root node
            node.color = "Black"
        else:  # if node isn't root node
            if P.color == "Red":  # if parent node is red
                G = P.parent  # must exist grandparent
                U = None
                if G.left == P:
                    U = G.right
                elif G.right == P:
                    U = G.left
 
                if U is not None and U.color == "Red":
                    # parent, uncle -> Black, grandparent -> Red
                    P.color, U.color = "Black", "Black"
                    G.color = "Red"
                    # rebalncing from grandparent
                    self._balancing(G)
                else:  # uncle is None or uncle.color is black
                    if P == G.left and P.left == node:  # LL Case
                        G.color, P.color = P.color, G.color
                        self._right_rotate(G)
                    elif P == G.left and P.right == node:  # LR Case
                        self._left_rotate(P)
                        G.color, node.color = node.color, G.color
                        self._right_rotate(G)
                    elif P == G.right and P.right == node:  # RR Case
                        G.color, P.color = P.color, G.color
                        self._left_rotate(G)
                    elif P == G.right and P.left == node:  # RL Case
                        self._right_rotate(P)
                        G.color, node.color = node.color, G.color
                        self._left_rotate(G)
 
    def delete(self, data):
        node = self._get_delete_node(self.root, data)
        if node is None:
            return False
        self._delete_node(node)
        return True
 
    def _get_delete_node(self, node, data):
        if node.data > data:
            return self._get_delete_node(node.left, data)
        elif node.data < data:
            return self._get_delete_node(node.right, data)
        elif node.data == data:
            # check left, right child
            left = node.left
            right = node.right
            if left is not None and right is not None:
                # delete node has both child
                # swap value of minimum successor and delete node
                min_successor = self._find_min_successor(node.right)
                node.data, min_successor.data = min_successor.data, node.data
                return min_successor
            else:
                return node
 
    def _delete_node(self, V):
        C, S = None, None
        P = V.parent
        if V.left is not None:
            C = V.left
        elif V.right is not None:
            C = V.right
        if P is None:
            self.root = None
            return
        elif V == P.left:
            S = P.right
        elif V == P.right:
            S = P.left
        if C is None:
            C = Node(None)  # temporary Node
            C.parent = V
            C.color = "Black"
        if V.color == "Red" or C.color == "Red":
            # if V has child and V or C node color is red
            # make C color black and just delete V
            if P is None:
                self.root = V
            else:
                if C.data is not None:
                    C.parent = P
                    C.color = "Black"
                    if P.left == V:
                        P.left = C
                    elif P.right == V:
                        P.right = C
 
                elif C.data is None:
                    if P.left == V:
                        P.left = None
                    elif P.right == V:
                        P.right = None
                V = C
 
        elif V.color == "Black" and C.color == "Black":
            C.parent = P
            if V == P.left:
                if C.data is None:
                    P.left = None
                else:
                    P.left = C
            elif V == P.right:
                if C.data is None:
                    P.right = None
                else:
                    P.right = C
            V = C
            V.color = "BBlack"
            if P is None:
                V.color = "Black"
                self.root = V
            else:
                # if S and S's child are all black,
                # V's double black mark would be shifted to P
                # so need to make recursive function
                self._delete_balancing(V, P, S)
 
    def _delete_balancing(self, V, P, S):
        S_l, S_r = S.left, S.right
        if S_l is None:
            S_l = Node(None)  # temporary Node
            S_l.parent = S
            S_l.color = "Black"
        if S_r is None:
            S_r = Node(None)  # temporary Node
            S_r.parent = S
            S_r.color = "Black"
        if S.color == "Black" and (S_l.color == "Red" or S_r.color == "Red"):
            if S == P.left and S_l.color == "Red":
                S_l.color = "Black"
                self._right_rotate(P)
            elif S == P.left and S_r.color == "Red":
                S_r.color = "Black"
                self._left_rotate(S)
                self._right_rotate(P)
            elif S == P.right and S_r.color == "Red":
                S_r.color = "Black"
                self._left_rotate(P)
            elif S == P.right and S_l.color == "Red":
                S_l.color = "Black"
                self._right_rotate(S)
                self._left_rotate(P)
        elif S.color == "Black" and S_l.color == S_r.color and S_l.color == "Black":
            V.color = "Black"
            if P.color == "Red":
                P.color = "Black"
                return
            else:
                # if S and all S's child ar black
                # give V's double black to P
                # if P is black, balancing routine for V would be shifted to P
                P.color = "BBlack"
                S.color = "Red"
                PP = P.parent
                if PP and P == PP.left:
                    S = PP.right
                elif PP and P == PP.right:
                    S = PP.left
                if PP is None:
                    S = None
                self._delete_balancing(P, PP, S)
        elif S.color == "Red":
            S.color, P.color = P.color, S.color
            if S == P.left:
                self._right_rotate(P)
            elif S == P.right:
                self._left_rotate(P)
            self._delete_balancing(V, P, S)
 
    def _find_min_successor(self, node):
        if node.left is None:
            return node
        else:
            return self._find_min_successor(node.left)
 
    def _left_rotate(self, node):
        c = node.right
        p = node.parent
 
        if c.left is not None:
            c.left.parent = node
 
        node.right = c.left
        node.parent = c
        c.left = node
        c.parent = p
        if p is None:
            self.root = c
        elif p is not None:
            if p.left == node:
                p.left = c
            elif p.right == node:
                p.right = c
 
    def _right_rotate(self, node):
        c = node.left
        p = node.parent
 
        if c.right is not None:
            c.right.parent = node
 
        node.left = c.right
        node.parent = c
        c.right = node
        c.parent = p
        if p is None:
            self.root = c
        elif p is not None:
            if p.left == node:
                p.left = c
            elif p.right == node:
                p.right = c
 
def check(node):
    if node.left is not None:
        check(node.left)
    if node.parent != None:
        print(
            f'key: {node.data}, parent: {node.parent.data}, color: {node.color}')
    else:
        print(f'key: {node.data}, root: {node.parent}, color: {node.color}')
    if node.right is not None:
        check(node.right)
 
rbt = RedBlackTree()
a = [2, 1, 8, 9, 7, 3, 6, 4, 5]
 
for x in a:
    rbt.insert(x)
 
check(rbt.root)
print()
rbt.delete(4)
 
check(rbt.root)

Data Structure_Red_Black_Tree_012.png

'Algorithms > Data Structure' 카테고리의 다른 글

B+트리, B트리(B+Tree, BTree) (5)	2021.08.31
B-트리(B-Tree) (0)	2021.08.31
세그먼트 트리 비재귀 구현 (0)	2021.08.16
세그먼트 트리(Segment Tree) (0)	2021.08.14
최소 신장 트리(Minimum Spanning Tree) (1)	2021.08.02

내 블로그 - 관리자 홈 전환	`Q` `Q`
새 글 쓰기	`W` `W`

글 수정 (권한 있는 경우)	`E` `E`
댓글 영역으로 이동	`C` `C`

이 페이지의 URL 복사	`S` `S`
맨 위로 이동	`T` `T`
티스토리 홈 이동	`H` `H`
단축키 안내	`Shift` + `/` `⇧` + `/`

스터디룸