RedBlackTree 삽입연산 구현과 삭제연산 구현

현굥·2024년 7월 29일

algorithm

목록 보기

3/17

RBT(Red-Black Tree)

RBT는 균형을 유지하는 이진 탐색 트리입니다. 이는 트리의 높이가 O(log n)이 되도록 보장하며, 이로 인해 탐색, 삽입, 삭제 연산의 평균 시간 복잡도가 O(log n)이 됩니다.
RBT는 이진 탐색 트리의 기본 속성을 BST와 동일하게 모두 가지고 있으나, 추가적으로 아래의 속성을 가지고 있다.

RBT의 특징:

각 노드는 빨간색 또는 검은색 중 하나로 색칠됩니다.
루트 노드는 검은색입니다.
모든 leaf(NIl) 노드는 검은색입니다.
노드가 빨간색이면 모든 자식 노드의 색은 검정색입니다.
모든 NIL 노드로부터 출발하여 임의의 노드로 도달하는 경로상의 검은색 노드의 수는 같아야 합니다.

RBT ( insert ) 의 구현

RBT 를 구현하기 위해 앞서 구현했던 BST 를 상속받은 이후, 추가적으로 Red-Black Tree 속성을 유지하기 위해 색상 속성과 색상에 따른 조정 메커니즘을 추가해주어야 합니다.

주요 변경사항은 아래와 같습니다.

rb_insert() : BST의 노드 삽입 함수를 수정하여 삽입된 노드의 색깔을 빨간색으로 설정하고, 이후에 Red-Black Tree 속성을 유지하기 위해 rb_insert_fixup()함수를 호출합니다.
left_rotate() , right_rotate(): RBT의 속성을 유지하기 위해 회전 연산 함수를 추가하여 Red-Black Tree 속성을 만족하도록 합니다.
rb_insert_fixup(): 새로운 노드를 삽입한 후에 Red-Black Tree 속성을 유지하기 위한 함수입니다.

RBT code

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

class RBT(BST):
    def __init__(self):
        super().__init__()
        self.nil = Node(None)
        self.nil.color = "BLACK"
        self.root = self.nil

    def left_rotate(self, x):
        y = x.right  # y를 설정
        x.right = y.left  # y의 왼쪽 서브트리를 x의 오른쪽 서브트리로 변환
        if y.left != self.nil:
            y.left.parent = x
        y.parent = x.parent  # x의 부모를 y로 연결
        if x.parent == self.nil:
            self.root = y
        elif x == x.parent.left:
            x.parent.left = y
        else:
            x.parent.right = y
        y.left = x  # x를 y의 왼쪽으로 놓음
        x.parent = y

    def right_rotate(self, y):
        x = y.left  # x를 설정
        y.left = x.right  # x의 오른쪽 서브트리를 y의 왼쪽 서브트리로 변환
        if x.right != self.nil:
            x.right.parent = y
        x.parent = y.parent  # y의 부모를 x로 연결
        if y.parent == self.nil:
            self.root = x
        elif y == y.parent.right:
            y.parent.right = x
        else:
            y.parent.left = x
        x.right = y  # y를 x의 오른쪽으로 놓음
        y.parent = x

    def rb_insert(self, z):
        y = self.nil
        x = self.root
        while x != self.nil:
            y = x
            if z.key < x.key:
                x = x.left
            else:
                x = x.right
        z.parent = y
        if y == self.nil:
            self.root = z
        elif z.key < y.key:
            y.left = z
        else:
            y.right = z
        z.left = self.nil
        z.right = self.nil
        z.color = "RED"
        self.rb_insert_fixup(z)

    def rb_insert_fixup(self, z):
        while z.parent.color == "RED":
            if z.parent == z.parent.parent.left:  # z의 부모가 왼쪽 자식인 경우
                y = z.parent.parent.right  # y는 삼촌 노드
                if y.color == "RED":  # Case 1
                    z.parent.color = "BLACK"
                    y.color = "BLACK"
                    z.parent.parent.color = "RED"
                    z = z.parent.parent
                else:
                    if z == z.parent.right: 
                        z = z.parent
                        self.left_rotate(z)
                    z.parent.color = "BLACK"  
                    z.parent.parent.color = "RED"
                    self.right_rotate(z.parent.parent)
            else:  # z의 부모가 오른쪽 자식인 경우 
                y = z.parent.parent.left  # y는 삼촌 노드
                if y.color == "RED":  
                    z.parent.color = "BLACK"
                    y.color = "BLACK"
                    z.parent.parent.color = "RED"
                    z = z.parent.parent
                else:
                    if z == z.parent.left:  
                        z = z.parent
                        self.right_rotate(z)
                    z.parent.color = "BLACK"  
                    z.parent.parent.color = "RED"
                    self.left_rotate(z.parent.parent)
        self.root.color = "BLACK"

    def tree_insert(self, key):
        node = Node(key)
        self.rb_insert(node)

    def inorder_tree_walk(self, x):
        if x != self.nil:
            self.inorder_tree_walk(x.left)
            print(x.key, end=' ')
            self.inorder_tree_walk(x.right)

Node

RBT의 노드 클래스에서는 부가적으로 nil 노드를 나타내는 속성과 노드의 색상을 저장하는 속성이 추가되었습니다.
색상은 기본적으로 빨간색("RED")으로 설정됩니다.

code

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

RBT

앞에서 구현했던 BST 클래스에 기본적인 동작이 구현되어 있으므로, BST 를 상속받은 이후, Red-Black Tree 속성을 만족시켜주는 메서드를 추가하여 RBT 클래스를 구현하였습니다.

RBT를 구현하기 위해 추가하고 수정한 메서드와 코드에 대해 설명해보겠습니다.

__init__()

RBT 클래스에서는 부모, 왼쪽 자식, 오른쪽 자식 노드들을 가리키는 포인터뿐만 아니라, 레드블랙 트리에서 사용되는 색상도 추가로 초기화합니다.
```
 def __init__(self):
        super().__init__()
        self.nil = Node(None)
        self.nil.color = "BLACK"
        self.root = self.nil
```

tree_insert()

BST 클래스와 동일하게 새로운 노드를 삽입합니다.
RBT에서는 새로운 노드를 삽입한 후, rb_insert_fixup 메서드를 호출하여 레드블랙 트리의 속성을 유지합니다.

 def tree_insert(self, key):
        node = Node(key)
        self.rb_insert(node)

rb_insert_fixup()

Red-Black Tree의 속성을 유지하면서 노드를 삽입한 후에 발생할 수 있는 위반된 상황을 해결하는 메서드입니다.
이 메서드는 레드블랙 트리의 속성을 보존하기 위해 부모와 삼촌 노드의 색깔을 확인하고, 필요에 의해 회전 연산을 수행합니다.
함수의 작동방식은 아래 세가지 케이스에 따라 나누어 작동합니다.

Case 1: Uncle y is red

z의 부모와 삼촌 노드가 모두 빨간색인 경우입니다.
이 경우에는 부모와 삼촌 노드의 색상을 검은색으로 변경하고, 조부모 노드의 색상을 빨간색으로 변경합니다. 그 후에 삽입된 노드 z를 조부모로 이동시켜 레드블랙 트리의 속성을 만족합니다.

Case 2: Uncle y is black and z is a right child

이 경우에는 삼촌 노드가 검은색이므로 회전 연산을 수행합니다.
z가 부모의 오른쪽 자식이므로, z를 부모로 하여 왼쪽 회전을 수행합니다.
이후 Case 3으로 이동하여 레드블랙 트리의 속성을 다시 확인합니다.

Case 3: Uncle y is black and z is a left child

이 경우에는 부모와 조부모의 색상을 변경하고, 조부모를 기준으로 오른쪽 회전을 수행하여 레드블랙 트리의 속성을 만족합니다.

def rb_insert_fixup(self, z):
    while z.parent.color == "RED":  # z의 부모가 빨간색인 동안 반복
        if z.parent == z.parent.parent.left:  # z의 부모가 왼쪽 자식인 경우
            y = z.parent.parent.right  # y는 삼촌 노드
            if y.color == "RED":  # Case 1: 삼촌 노드가 빨간색인 경우
                z.parent.color = "BLACK"  # 부모 노드를 검은색으로 변경
                y.color = "BLACK"  # 삼촌 노드를 검은색으로 변경
                z.parent.parent.color = "RED"  # 조부모 노드를 빨간색으로 변경
                z = z.parent.parent  # z를 조부모 노드로 이동
            else:
                if z == z.parent.right:  # Case 2: z가 부모의 오른쪽 자식인 경우
                    z = z.parent  # z를 부모로 이동
                    self.left_rotate(z)  # 부모를 기준으로 왼쪽 회전
                z.parent.color = "BLACK"  # Case 3: 부모를 검은색으로 변경
                z.parent.parent.color = "RED"  # 조부모를 빨간색으로 변경
                self.right_rotate(z.parent.parent)  # 조부모를 기준으로 오른쪽 회전
        else:  # z의 부모가 오른쪽 자식인 경우
            y = z.parent.parent.left  # y는 삼촌 노드
            if y.color == "RED":  # Case 4: 삼촌 노드가 빨간색인 경우
                z.parent.color = "BLACK"  # 부모 노드를 검은색으로 변경
                y.color = "BLACK"  # 삼촌 노드를 검은색으로 변경
                z.parent.parent.color = "RED"  # 조부모 노드를 빨간색으로 변경
                z = z.parent.parent  # z를 조부모 노드로 이동
            else:
                if z == z.parent.left:  # Case 5: z가 부모의 왼쪽 자식인 경우
                    z = z.parent  # z를 부모로 이동
                    self.right_rotate(z)  # 부모를 기준으로 오른쪽 회전
                z.parent.color = "BLACK"  # Case 6: 부모를 검은색으로 변경
                z.parent.parent.color = "RED"  # 조부모를 빨간색으로 변경
                self.left_rotate(z.parent.parent)  # 조부모를 기준으로 왼쪽 회전
    self.root.color = "BLACK"  # 루트를 검은색으로 변경

left_rotate() , right_rotate()

노드의 위치를 회전시켜 트리의 균형을 조정합니다.
레드블랙 트리에서는 삽입연산 혹은 삭제연산 이후에 회전 연산을 통해 노드의 색상을 조정하여 레드블랙 트리의 속성을 유지합니다.

left_rotate() 의 작동 원리

왼쪽 회전은 한 노드를 기준으로 그 노드의 오른쪽 자식을 새로운 루트로 하여 회전하는 연산입니다.
이 과정에서 해당 노드의 오른쪽 자식을 가져와서 새로운 루트로 설정하며, 이 때 오른쪽 자식의 왼쪽 서브트리는 원래 부모 노드의 오른쪽 서브트리로 이동합니다.
따라서 회전 후에는 회전하는 노드의 오른쪽 자식이 새로운 루트가 되고, 회전하는 노드는 해당 자식의 왼쪽 자식으로 들어가게 됩니다.
이로써 회전한 노드와 그 자식 노드들 사이의 관계가 변경되며, 이에 따라 부모 및 자식 포인터가 새로 설정됩니다.

left_rotate() code

 def left_rotate(self, x):
        y = x.right  # y를 설정
        x.right = y.left  # y의 왼쪽 서브트리를 x의 오른쪽 서브트리로 변환
        if y.left != self.nil:
            y.left.parent = x
        y.parent = x.parent  # x의 부모를 y로 연결
        if x.parent == self.nil:
            self.root = y
        elif x == x.parent.left:
            x.parent.left = y
        else:
            x.parent.right = y
        y.left = x  # x를 y의 왼쪽으로 놓음
        x.parent = y


    def right_rotate(self, y):
        x = y.left  # x를 설정
        y.left = x.right  # x의 오른쪽 서브트리를 y의 왼쪽 서브트리로 변환
        if x.right != self.nil:
            x.right.parent = y
        x.parent = y.parent  # y의 부모를 x로 연결
        if y.parent == self.nil:
            self.root = x
        elif y == y.parent.right:
            y.parent.right = x
        else:
            y.parent.left = x
        x.right = y  # y를 x의 오른쪽으로 놓음
        y.parent = x

print_tree() , _print_tree_recursive

실습을 위해 tree를 출력하기 위한 함수를 아래와 같이 정의했습니다.

def print_tree(self):
        self._print_tree_recursive(self.root, 0)

def _print_tree_recursive(self, node, level):
        if node == self.nil:
            return
        self._print_tree_recursive(node.right, level + 1)
        print('  ' * level + str(node.key) + f" ({node.color})")
        self._print_tree_recursive(node.left, level + 1)

RBT Test _insertion

RBT insertion Test를 해보겠습니다.

코드와 결과는 아래와 같습니다.

def test_rbt():
    # 빈 Red-Black Tree 생성
    rbt = RBT()

    # Case 1: Uncle y is red
    print("RBT Insert Test ")
    rbt.tree_insert(8)
    rbt.tree_insert(4)
    rbt.tree_insert(20)
    rbt.tree_insert(6)
    rbt.tree_insert(10)
    rbt.tree_insert(25)
    rbt.tree_insert(8)
    rbt.tree_insert(12)
    rbt.tree_insert(37)
    print()
    rbt.print_tree()
    print()

    rbt.tree_insert(15)
    print(" After inserting nodes 15 :")
    print()
    rbt.print_tree()
    print()

test_rbt()

Untitled

이제 과정을 설명해보겠습니다.

빈 트리에 8, 4, 20, 6,10,25,8,12,37 을 넣어주었습니다.

RBT성질을 만족하며 아래와 같이 Red-Black Tree가 완성된것을 확인할 수 있습니다.

Untitled

Tree에 15를 Insert 해주었습니다. 새로운 노드를 삽입할 때, 트리의 속성을 최대한 유지하면서 삽입을 간단하게 만들기 위해 빨간색으로 넣어주었습니다. 12의 Right child으로 삽입되어 빨간색 노드가 연속하여 나와 Red-black Tree의 속성 4를 위배하는것을 볼 수 있습니다.
RBT의 속성을 만족시키기 위해 12를 Black, 10을 Red으로 Recolor 했습니다. 아래와 같이 20, 10 에서 빨간색 노드가 연속하여 나와 Red-black Tree의 속성 4가 위배된 것 확인할 수 있습니다.
Red - Black Tree의 속성을 만족시키기 위해 Right-Rotate(10) 을 해주었습니다.
RBT의 속성을 만족시키기 위해 left Rotate(10) 한 이후, recolor해주었습니다. 그 결과, 10을 root로 하는 red-black Tree가 완성된것을 확인할 수 있습니다.

RBT Test _Delete

레드블랙트리에서 노드를 삭제하고 난 후, 삭제된 노드의 자리에 이식된 노드를 x, w를 x의 형제노드라고 할 때, 발생할 주요 케이스들이 존재합니다.

다음은 삭제 과정에서 발생할 수 있는 주요 케이스들입니다.

Case 1: `w` is red

처리 방법:
- w를 검은색으로 바꾼다.
- x의 부모 p[x]를 빨간색으로 바꾼다.
- p[x]를 기준으로 좌회전을 수행한다.
- 이렇게 하면 w가 검은색이 되고, 새 w는 x의 새 형제 노드가 된다. 그 다음은 새로운 w가 검은색인 경우를 처리하는 나머지 케이스로 넘어간다.

Case 2: `w` is black, and both `w`'s children are black

처리 방법:
- w를 빨간색으로 바꾼다.
- x의 부모 p[x]가 검은색이라면 x를 p[x]로 설정하여 반복한다. (다음 반복에서 새로운 x의 형제 w를 검사한다.)
- 만약 p[x]가 빨간색이라면 p[x]를 검은색으로 바꿔서 균형을 맞춘다.

Case 3: `w` is black, `w`'s left child is red, and `w`'s right child is black

처리 방법:
- w의 왼쪽 자식을 검은색으로 바꾼다.
- w를 빨간색으로 바꾼다.
- w를 기준으로 우회전을 수행한다.
- 이렇게 하면 w의 새로운 형제 노드 w가 검은색이고, w의 오른쪽 자식이 빨간색인 경우로 전환된다. 이때는 다음 케이스를 처리한다.

Case 4: `w` is black, `w`'s right child is red

처리 방법:
- w의 색을 p[x]의 색으로 바꾼다.
- p[x]를 검은색으로 바꾼다.
- w의 오른쪽 자식을 검은색으로 바꾼다.
- p[x]를 기준으로 좌회전을 수행한다.
- 이로써 트리의 모든 속성이 복원되고, 삭제 작업이 완료된다.

현굥

이전 포스트

[algorithm] 이진탐색(Binary Search)

다음 포스트

RedBlackTree 삽입연산 구현과 삭제연산 구현

algorithm

RBT(Red-Black Tree)

RBT의 특징:

RBT ( insert ) 의 구현

Node

RBT

RBT Test _insertion

RBT Test _Delete

Case 1: `w` is red

Case 2: `w` is black, and both `w`'s children are black

Case 3: `w` is black, `w`'s left child is red, and `w`'s right child is black

Case 4: `w` is black, `w`'s right child is red

[algorithm] 이진탐색(Binary Search)

[algorithm] 분할 정복 기법

0개의 댓글

RedBlackTree 삽입연산 구현과 삭제연산 구현

algorithm

RBT(Red-Black Tree)

RBT의 특징:

RBT ( insert ) 의 구현

Node

RBT

RBT Test _insertion

RBT Test _Delete

Case 1: w is red

Case 2: w is black, and both w's children are black

Case 3: w is black, w's left child is red, and w's right child is black

Case 4: w is black, w's right child is red

[algorithm] 이진탐색(Binary Search)

[algorithm] 분할 정복 기법

0개의 댓글

Case 1: `w` is red

Case 2: `w` is black, and both `w`'s children are black

Case 3: `w` is black, `w`'s left child is red, and `w`'s right child is black

Case 4: `w` is black, `w`'s right child is red