Python에서 Red-Black 이진 트리 만들기

게시물Building a Red-Black Binary Tree in Python은 Qvault에 처음 등장했습니다.

레드 블랙 트리는 일종의 자체 균형 이진 검색 트리입니다. 각 노드는 여분의 비트를 저장하며 이를 색상(빨간색 또는 검은색)이라고 합니다. 색상은 삽입 및 삭제 중에 트리가 대략적으로 균형을 유지하도록 합니다. 나무가 수정되면 새 나무가 재정렬되고 최악의 경우 나무가 얼마나 불균형해질 수 있는지를 제한하는 색상 속성을 복원하기 위해 다시 칠해집니다.

레드-블랙 트리의 목적은 균형을 유지하여 조회 및 삭제와 같은 일반적인 작업이 O(n*log(n)) 보다 악화되지 않도록 하는 것입니다.

방해해서 미안해! 나는 당신이 나의 새로운 무료 Python 과정인 "Big-O Data Structures"를 확인해야 한다고 언급하고 싶었습니다. 다가오는 코딩 인터뷰와 화이트보드 세션을 끝내기 위해 알아야 할 모든 것을 배우게 될 것입니다.

Start Python Data Structures Course

균형 이진 트리란?

이진 트리에 색상을 추가하는 이유는 균형을 유지하기 위한 것이므로 이진 트리가 균형을 이루는 방법과 이유를 이해해야 합니다. 간단히 말해서, 균형잡힌 나무의 가지는 높이가 1개 이상 차이가 나지 않습니다.

다음 트리는 두 가지 사이에서 하나의 높이가 2이고 다른 하나의 높이가 3이기 때문에 균형을 이룹니다.

A
   / \
  B C 
 /
D

다음 나무는 가지의 높이가 1 이상 다르기 때문에 균형이 맞지 않습니다. C 의 오른쪽은 높이가 2이고 왼쪽은 높이가 4입니다.

A
   / \
  B C
 / /
D E  
     /  
    G

균형 잡힌 트리를 원하는 이유는 무엇입니까?

균형 잡힌 이진 검색 트리는 속도를 보장합니다. 이진 트리의 작업 속도는 트리의 높이에 따라 다릅니다. 트리가 균형을 이루면 높이가 노드 수의 log에 불과하므로 트리가 최대한 빨리 작동합니다. 그러나 트리가 균형이 맞지 않는 경우(예: 하나의 매우 긴 가지) 높이는 로그가 아닌 총 노드 수 때문입니다.

A
     / 
    B
   /
  C
 /  
D

레드 블랙 트리의 속성

Binary Search Tree 의 모든 속성 외에도 레드-블랙 트리에는 다음이 있어야 합니다.

각 노드가 빨간색 또는 검은색임

뿌리가 검다. 이 규칙은 때때로 생략됩니다. 루트는 항상 빨간색에서 검은색으로 변경될 수 있지만 반드시 그 반대일 필요는 없기 때문에 이 규칙은 분석에 거의 영향을 미치지 않습니다.

모든nil 리프 노드가 검은색입니다.

노드가 빨간색이면 노드의 두 자식도 모두 검은색입니다.

단일 노드의 모든 경로는 하위nil 노드에 도달하기 위해 동일한 수의 검은색 노드를 통과합니다.

Python에서 Red-Black 트리 구현

1단계 – RBNode 클래스

구현에서는 Tree 클래스와 Node 클래스를 사용합니다. 노드는 매우 간단할 것입니다. 단지 생성자일 뿐입니다.

class RBNode:
    def __init__ (self, val):
        self.red = False
        self.parent = None
        self.val = val
        self.left = None
        self.right = None
<small id="shcb-language-1"><span>Code language:</span> <span>Python</span> <span>(</span><span>python</span><span>)</span></small>

2단계 – RBTree 클래스

다음으로 생성자로 트리 클래스를 만들어 봅시다.

class RBTree:
    def __init__ (self):
        self.nil = RBNode(0)
        self.nil.red = False
        self.nil.left = None
        self.nil.right = None
        self.root = self.nil`
<small id="shcb-language-2"><span>Code language:</span> <span>Python</span> <span>(</span><span>python</span><span>)</span></small>

3단계 – 방법 삽입

def insert(self, val):
    # Ordinary Binary Search Insertion
    new_node = RBNode(val)
    new_node.parent = None
    new_node.left = self.nil
    new_node.right = self.nil
    new_node.red = True # new node must be red

    parent = None
    current = self.root
    while current != self.nil:
        parent = current
        if new_node.val < current.val:
            current = current.left
        elif new_node.val > current.val:
            current = current.right
        else:
            return

    # Set the parent and insert the new node
    new_node.parent = parent
    if parent == None:
        self.root = new_node
    elif new_node.val < parent.val:
        parent.left = new_node
    else:
        parent.right = new_node

    # Fix the tree
    self.fix_insert(new_node)
<small id="shcb-language-3"><span>Code language:</span> <span>Python</span> <span>(</span><span>python</span><span>)</span></small>

삽입 방법은 전통적인 이진 트리 삽입 방법과 매우 유사합니다. 가장 큰 차이점은 삽입을 수행한 후 특수fix_insert 메서드를 호출한다는 것입니다. 지금은 그냥 부르기만 하면 됩니다. 잠시 후에 구현하겠습니다.

4단계 - 왼쪽으로 회전

다가오는 "수정"단계에서 몇 가지 회전 방법이 필요합니다. 이제 코드를 작성해 보겠습니다.

# rotate left at node x
def rotate_left(self, x):
    y = x.right
    x.right = y.left
    if y.left != self.nil:
        y.left.parent = x

    y.parent = x.parent
    if x.parent == None:
        self.root = y
    elif x == x.parent.left:
        x.parent.left = y
    else:
        x.parent.right = y
    y.left = x
    x.parent = y
<small id="shcb-language-4"><span>Code language:</span> <span>Python</span> <span>(</span><span>python</span><span>)</span></small>

5단계 – 오른쪽으로 회전

# rotate right at node x
def rotate_right(self, x):
    y = x.left
    x.left = y.right
    if y.right != self.nil:
        y.right.parent = x

    y.parent = x.parent
    if x.parent == None:
        self.root = y
    elif x == x.parent.right:
        x.parent.right = y
    else:
        x.parent.left = y
    y.right = x
    x.parent = y
<small id="shcb-language-5"><span>Code language:</span> <span>Python</span> <span>(</span><span>python</span><span>)</span></small>

6단계 - 인서트 수정

진정한 빵과 버터는 이 단계에 있습니다. 이것이 바로 레드-블랙 트리의 균형을 맞추는 것입니다.

def fix_insert(self, new_node):
    while new_node != self.root and new_node.parent.red:
        if new_node.parent == new_node.parent.parent.right:
            u = new_node.parent.parent.left # uncle
            if u.red:

                u.red = False
                new_node.parent.red = False
                new_node.parent.parent.red = True
                new_node = new_node.parent.parent
            else:
                if new_node == new_node.parent.left:
                    new_node = new_node.parent
                    self.rotate_right(new_node)
                new_node.parent.red = False
                new_node.parent.parent.red = True
                self.rotate_left(new_node.parent.parent)
        else:
            u = new_node.parent.parent.right # uncle

            if u.red:
                u.red = False
                new_node.parent.red = False
                new_node.parent.parent.red = True
                new_node = new_node.parent.parent
            else:
                if new_node == new_node.parent.right:
                    new_node = new_node.parent
                    self.rotate_left(new_node)
                new_node.parent.red = False
                new_node.parent.parent.red = True
                self.rotate_right(new_node.parent.parent)
    self.root.red = False
<small id="shcb-language-6"><span>Code language:</span> <span>Python</span> <span>(</span><span>python</span><span>)</span></small>

코드 내 Red-Black 트리의 전체 예

import random

class RBNode:
    def __init__ (self, val):
        self.red = False
        self.parent = None
        self.val = val
        self.left = None
        self.right = None

class RBTree:
    def __init__ (self):
        self.nil = RBNode(0)
        self.nil.red = False
        self.nil.left = None
        self.nil.right = None
        self.root = self.nil

    def insert(self, val):
        # Ordinary Binary Search Insertion
        new_node = RBNode(val)
        new_node.parent = None
        new_node.left = self.nil
        new_node.right = self.nil
        new_node.red = True # new node must be red

        parent = None
        current = self.root
        while current != self.nil:
            parent = current
            if new_node.val < current.val:
                current = current.left
            elif new_node.val > current.val:
                current = current.right
            else:
                return

        # Set the parent and insert the new node
        new_node.parent = parent
        if parent == None:
            self.root = new_node
        elif new_node.val < parent.val:
            parent.left = new_node
        else:
            parent.right = new_node

        # Fix the tree
        self.fix_insert(new_node)

    def fix_insert(self, new_node):
        while new_node != self.root and new_node.parent.red:
            if new_node.parent == new_node.parent.parent.right:
                u = new_node.parent.parent.left # uncle
                if u.red:
                    u.red = False
                    new_node.parent.red = False
                    new_node.parent.parent.red = True
                    new_node = new_node.parent.parent
                else:
                    if new_node == new_node.parent.left:
                        new_node = new_node.parent
                        self.rotate_right(new_node)
                    new_node.parent.red = False
                    new_node.parent.parent.red = True
                    self.rotate_left(new_node.parent.parent)
            else:
                u = new_node.parent.parent.right # uncle

                if u.red:
                    u.red = False
                    new_node.parent.red = False
                    new_node.parent.parent.red = True
                    new_node = new_node.parent.parent
                else:
                    if new_node == new_node.parent.right:
                        new_node = new_node.parent
                        self.rotate_left(new_node)
                    new_node.parent.red = False
                    new_node.parent.parent.red = True
                    self.rotate_right(new_node.parent.parent)
        self.root.red = False

    def exists(self, val):
        curr = self.root
        while curr != self.nil and val != curr.val:
            if val < curr.val:
                curr = curr.left
            else:
                curr = curr.right
        return curr

    # rotate left at node x
    def rotate_left(self, x):
        y = x.right
        x.right = y.left
        if y.left != self.nil:
            y.left.parent = x

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

    # rotate right at node x
    def rotate_right(self, x):
        y = x.left
        x.left = y.right
        if y.right != self.nil:
            y.right.parent = x

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

    def __repr__ (self):
        lines = []
        print_tree(self.root, lines)
        return '\n'.join(lines)

def print_tree(node, lines, level=0):
    if node.val != 0:
        print_tree(node.left, lines, level + 1)
        lines.append('-' * 4 * level + '> ' +
                     str(node.val) + ' ' + ('r' if node.red else 'b'))
        print_tree(node.right, lines, level + 1)

def get_nums(num):
    random.seed(1)
    nums = []
    for _ in range(num):
        nums.append(random.randint(1, num-1))
    return nums

def main():
    tree = RBTree()
    for x in range(1, 51):
        tree.insert(x)
    print(tree)

main()
<small id="shcb-language-7"><span>Code language:</span> <span>Python</span> <span>(</span><span>python</span><span>)</span></small>

코딩할 준비가 되셨나요?

Try our coding courses free

Join our Discord community

질문이나 의견이 있으십니까?

질문이나 의견이 있으면 트위터에서 나를 팔로우하고 연락하십시오. 기사에서 실수를 한 경우 반드시 let me know 수정하여 수정할 수 있도록 해주세요!