[CLRS] [13-3] LLRB Tree(Left-Leaning Red-Black Tree)

1. Intro

- RBTree는 노드의 속성중 색상을 정의하여 Red or Black으로 나타낸 후, BBST를 유지한다는 독특한 개념의 트리라고 말할 수 있다.

- 이러한 RBTree는 탐색, 삽입,삭제 연산의 수행시간이 O(logN)을 넘지않는 특징을 가진다.

 

2. RBTree의 문제점

- RBTree에 대한 설명은 13-2에서 했고, 이러한 RBTree의 문제점은 BBST를 유지하기 위해 까다로운 조건들을 고려해야한다는 것이다.

- 그로인해, 프로그램이 복잡해지고, 길이는 증가한다. 즉, 프로그래머가 상대적으로 더 많은 노력을 하게 된다.

- 이러한 RBTree을 간단하게 구현하고자 나온게 바로 LLRBTree이다. 

 

3. LLRB Tree(Left-Leaning Red-Black Tree)

- 일반적인 RBTree의 문제점을 해결하고자 LLRB Tree가 나오게 되었는데,

- 개념적으로 2-3Tree와 동일하다.

- 임의의 노드 n의 왼쪽 자식은 Red or Black 노드를 가지고, 오른쪽 자식은 무조건 Black 노드를 가지도록 설정한다.

 

3.1. LLRB Tree의 조건 

'''

1. Root, NIL Node는 Black으로 둔다.

2. no Double Red

3. Root부터 각 leaf까지의 Black 노드수는 모두 동일하다.

4. Red노드는 항상 왼쪽으로 기울어져 있다.

'''

- 이러한 네가지 조건을 만족해야 LLRB Tree라고 할 수 있다.

- 이러한 네가지 조건을 만족하게 LLRB Tree을 구현을 해보자.

 

4. LLRB Tree의 핵심 연산

4.1. CASE 1. (부모노드 : B / 왼쪽 자식 노드 : Black / 오른쪽 자식 노드 : Red)

4.2. CASE 2. (left double red)

4.3. CASE 3.(자식 노드가 전부 Red)

 

5. Code

5.1. Insert method구현한 LLRB Tree 

class Node:
    def __init__(self, key, color='R'):
        self.key = key
        self.left = None
        self.right = None
        self.color = color  # R: Red, B: Black


class LLRBT:
    def __init__(self):
        self.root = None

    def insert(self, key):
        # 삽입 후 루트는 항상 검은색이어야 함
        self.root = self._insert(self.root, key)
        self.root.color = 'B'

    def _insert(self, node, key):
        if node is None:
            # 새 노드는 항상 빨간색으로 삽입
            return Node(key)

        # 이진 탐색 트리 규칙
        if key < node.key:
            node.left = self._insert(node.left, key)
        elif key > node.key:
            node.right = self._insert(node.right, key)
        
        # LLRB 규칙 복구
        if self._isRed(node.right) and not self._isRed(node.left):
            node = self._rotateLeft(node)
        if self._isRed(node.left) and self._isRed(node.left.left):
            node = self._rotateRight(node)
        if self._isRed(node.left) and self._isRed(node.right):
            self._flipColors(node)

        return node

    def _isRed(self, node):
        # None 노드는 검은색으로 간주
        return node is not None and node.color == 'R'

    def _rotateLeft(self, node):
        # 오른쪽 자식의 빨간 간선을 왼쪽으로 회전
        newRoot = node.right
        node.right = newRoot.left
        newRoot.left = node
        # 색상 전환
        newRoot.color = node.color
        node.color = 'R'
        return newRoot

    def _rotateRight(self, node):
        # 왼쪽 자식의 빨간 간선을 오른쪽으로 회전
        newRoot = node.left
        node.left = newRoot.right
        newRoot.right = node
        # 색상 전환
        newRoot.color = node.color
        node.color = 'R'
        return newRoot

    def _flipColors(self, node):
        # 색상 전환: 부모는 빨간색으로, 자식들은 검은색으로 변경
        node.color = 'R' if node.color == 'B' else 'B'
        if node.left:
            node.left.color = 'B' if node.left.color == 'R' else 'R'
        if node.right:
            node.right.color = 'B' if node.right.color == 'R' else 'R'

    # 트리 출력 (디버깅용)
    def printTree(self, node=None, level=0, prefix="Root: "):
        if node is None:
            node = self.root
        if node is not None:
            print(" " * (level * 4) + prefix + f"({node.key}, {node.color})")
            if node.left:
                self.printTree(node.left, level + 1, "L--- ")
            if node.right:
                self.printTree(node.right, level + 1, "R--- ")

5.2. Tree 시각화

#Tree Visualization
import matplotlib.pyplot as plt
from pylab import rcParams
def plot_node(node, rb=True, level=1, posx=0, posy=0):
    width = 2000.0 * (0.5 ** (level))
    if node.color == 'B' or rb == False:
        plt.text(posx, posy, str(node.key), horizontalalignment='center', color='k', fontsize=15)
    else:
        if node.color == 'R' or rb == True:
            plt.text(posx, posy, str(node.key), horizontalalignment='center', color='r', fontsize=15)
    if node.left is not None:
        px = [posx, posx - width]
        py = [posy - 1, posy - 15]
        if node.left.color == 'B' or rb == False:
            plt.plot(px, py, 'k-')
        else:
            plt.plot(px, py, 'r-')
        plot_node(node.left, rb, level + 1, posx - width, posy - 20)

    if node.right is not None:
        plot_node(node.right, rb, level + 1, posx + width, posy - 20)
        px = [posx, posx + width]
        py = [posy - 1, posy - 15]
        if node.right.color == 'B' or rb == False:
            plt.plot(px, py, 'k-')
        else:
            plt.plot(px, py, 'r-')

def plot_tree(node, figsize=(20, 10)):
    if node.color == 'R':
        rb = False
    elif node.color == 'B':
        rb = True
    rcParams['figure.figsize'] = figsize
    fig, ax = plt.subplots()
    ax.axis('off')
    plot_node(node, rb)
    plt.show()

 

5.3. Result

#nodes = [56, 33, 52, 91, 24, 12, 51, 41, 84, 19, 20, 31, 2, 3, 4, 5, 6, 7, 32, 1, 0, 65, 5, 6, 22, 13, 14, 21, 32, 41, 25, 64, 37, 89, 10, 47, 89, 34, 21, 9]
nodes = [10,20,30,40,50,25]
obtest = LLRBT()
for node in nodes:
    obtest.insert(node)
plot_tree(obtest.root,figsize=(20, 10))