Построй лес в серии Python: Красно-Черное дерево

Из Двоичного дерева поиска: анализ мы знаем, что высота дерева является критическим фактором производительности двоичного дерева поиска. В этой и следующей статьях будет реализован один вариант бинарного дерева поиска, который будет поддерживать баланс между деревьями: Красно-Черное дерево.

Настройка проекта

Следуйте тому же стилю и предположениям, что и в других статьях из серии Build the Forest, реализация предполагает Python 3.9 или новее. В этой статье к нашему проекту добавляются два модуля: red_black_tree.py для реализации красно-черного дерева и test_red_black_tree.py для его модульных тестов. После добавления этих двух файлов макет нашего проекта становится следующим:

forest-python
├── forest
│   ├── __init__.py
│   ├── binary_trees
│   │   ├── __init__.py
│   │   ├── binary_search_tree.py
│   │   ├── double_threaded_binary_tree.py
│   │   ├── red_black_tree.py
│   │   ├── single_threaded_binary_trees.py
│   │   └── traversal.py
│   └── tree_exceptions.py
└── tests
    ├── __init__.py
    ├── conftest.py
    ├── test_binary_search_tree.py
    ├── test_double_threaded_binary_tree.py
    ├── test_red_black_tree.py
    ├── test_single_threaded_binary_trees.py
    └── test_traversal.py

(Полный код доступен на forest-python)

Что такое красно-черное дерево?

Красно-черное дерево изменяет двоичное дерево поиска с помощью способности самобалансировки, а его узел имеет один дополнительный атрибут: цвет, который может быть красным или черным. В дополнение к свойству двоичного дерева поиска, красно-черное дерево также удовлетворяет следующему свойству красного-черного-дерева:

• Каждый узел красный или черный
• Корень черный
• Каждый лист черный
• Если узел красный, то оба его потомка черные.
• Весь путь каждого узла от узла к листьям содержит одинаковое количество черных узлов.

Красно-черное дерево гарантирует, что ни один путь не будет вдвое длиннее других путей, ограничивая цвета узла на любом простом пути от узла к его дочерним листьям. Другими словами, красно-черное дерево примерно сбалансировано.

Типичное красно-черное дерево выглядит как на картинке ниже.

Листовой узел древовидной структуры данных обычно относится к узлу, у которого нет дочерних элементов. Однако мы используем NIL для обозначения листьев у красно-черного дерева, и они всегда черные. Кроме того, листовые узлы не содержат никаких данных и в основном предназначены для поддержания свойства красно-черного дерева.

Мы используем высоту черного, чтобы указать количество черных узлов от узла до листьев (исключите узел, если узел черный). На следующем рисунке показана высота черного для каждого узла.

Рядом с каждым узлом указана высота черного для узла, а для листовых узлов (NIL) высота черного равна нулю.

Построить красно-черное дерево

Как и в предыдущих деревьях, в этом разделе мы рассмотрим реализацию и обсудим некоторые мысли, лежащие в основе выбора реализации.

Поскольку все листья равны NIL, а родительский элемент корня также может указывать на NIL, когда мы реализуем красно-черное дерево, мы можем определить один узел NIL и позволить родительскому элементу корня и все узлы, поддерживаемые для указания на узел NIL, указывают на узел NIL. Итак, красно-черное дерево, показанное в предыдущем разделе, становится следующим:

Такой способ упрощает реализацию и экономит место (т.е. в реализации нужен только один экземпляр узла NIL).

Для простоты узел NIL будет опущен в остальной части статьи, поэтому красно-черное дерево выше будет выглядеть следующим образом (но в реализации должен присутствовать узел NIL; в противном случае, это нарушит свойство красного-черного-дерева).

Узел

Узел красно-черного дерева похож на узел дерева двоичного поиска, но имеет еще один атрибут - цвет.

Поскольку цвет должен быть красным или черным, мы можем определить его как класс enum.

import enum

class Color(enum.Enum):
    RED = enum.auto()
    BLACK = enum.auto()

Зачем использовать перечисление?

Согласно PEP-435, перечисление - это набор символьных имен, привязанных к уникальным постоянным значениям. Внутри перечисления значения можно сравнивать по идентичности, а само перечисление можно повторять . Имеет смысл определить атрибут цвета как класс перечисления, потому что его значение (красный или черный) является постоянным, и мы можем идентифицировать атрибут цвета и сравнивать его. Кроме того, класс перечисления обеспечивает более надежную безопасность типов. Если мы не используем перечисление, мы могли бы определить атрибуты цвета как постоянные строки. Однако инструменты проверки типов (например, mypy) не смогут проверить, является ли значение атрибутом цвета или обычной строкой. Другой альтернативой является определение атрибута цвета как обычного класса или класса данных следующим образом:

@dataclass
class Color:
    RED: str = "red"
    BLACK: str = "black"

У этого метода все же есть недостатки. Например, тип подчеркивания по-прежнему является строкой. Можно сравнить с любыми струнами. Кроме того, класс изменчив. Другими словами, мы можем изменить класс Color во время выполнения, что противоречит определению цвета. Следовательно, использование перечисления для определения атрибутов цвета имеет наибольший смысл. Это увеличивает безопасность типов и упрощает реализацию.

Красно-черный узел дерева

Как и другие узлы двоичного дерева, мы используем класс данных для определения красно-черного узла дерева.

from dataclasses import dataclass

@dataclass
class Node:
    """Red-Black Tree non-leaf node definition."""

    key: Any
    data: Any
    left: Union["Node", Leaf] = Leaf()
    right: Union["Node", Leaf] = Leaf()
    parent: Union["Node", Leaf] = Leaf()
    color: Color = Color.RED

Листовой узел

Как упоминалось в определении красно-черного дерева, мы используем NIL для обозначения конечного узла, и его можно определить следующим образом.

from dataclasses import dataclass

@dataclass
class Leaf:
    color = Color.BLACK

Обзор класса

Как и другие типы двоичных деревьев в проекте Build the Forest, класс красно-черного дерева имеет аналогичные функции.

class RBTree:

    def __init__(self) -> None:
        self._NIL: Leaf = Leaf()
        self.root: Union[Node, Leaf] = self._NIL

    def __repr__(self) -> str:
        """Provie the tree representation to visualize its layout."""
        if self.root:
            return (
                f"{type(self)}, root={self.root}, "
                f"tree_height={str(self.get_height(self.root))}"
            )
        return "empty tree"

    def search(self, key: Any) -> Optional[Node]:
        …

    def insert(self, key: Any, data: Any) -> None:
        …

    def delete(self, key: Any) -> None:
        …

    @staticmethod
    def get_leftmost(node: Node) -> Node:
        …

    @staticmethod
    def get_rightmost(node: Node) -> Node:
        …

    @staticmethod
    def get_successor(node: Node) -> Union[Node, Leaf]:
        …

    @staticmethod
    def get_predecessor(node: Node) -> Union[Node, Leaf]:
        …

    @staticmethod
    def get_height(node: Union[Leaf, Node]) -> int:
        …

    def inorder_traverse(self) -> traversal.Pairs:
        …

    def preorder_traverse(self) -> traversal.Pairs:
        …

    def postorder_traverse(self) -> traversal.Pairs:
        …

    def _transplant(
        self, deleting_node: Node, replacing_node: Union[Node, Leaf]
    ) -> None:
        …

    def _left_rotate(self, node_x: Node) -> None:
        …

    def _right_rotate(self, node_x: Node) -> None:
        …

    def _insert_fixup(self, fixing_node: Node) -> None:
        …

    def _delete_fixup(self, fixing_node: Union[Leaf, Node]) -> None:
        …

Обратите внимание, что помимо общих методов всех двоичных деревьев, класс RBTree имеет некоторые дополнительные методы. _left_rotate (), _right_rotate (), _insert_fixup () и _delete_fixup () - вспомогательные функции для поддержки свойство красного-черного-дерева после вставки и удаления. И операции вставки, и удаления изменяют дерево; следовательно, операции могут нарушать свойство красного-черного-дерева. Вот почему нам нужны эти функции.

Конечный узел имеет значение NIL, поэтому процедуры обхода (используйте None, чтобы определить, достигают ли конечный узел) из Обход двоичного дерева не работают с RBTree класс (необходимо использовать Leaf, чтобы определить, достигается ли листовой узел). Следовательно, класс RBTree должен предоставить свои процедуры обхода.

Вставлять

Поскольку операция вставки изменяет красно-черное дерево, результат может нарушать свойство красного-черного-дерева (это также верно для удаления). Чтобы восстановить свойство красного-черного-дерева, нам нужно изменить цвет некоторых узлов, а также обновить формирование красно-черного дерева. Метод обновления формирования двоичного дерева называется вращением. Техника исправления нарушенного свойства красного-черного-дерева взята из Введение в алгоритмы, а идею вставки красно-черного дерева можно резюмировать следующим образом:

1. Вставьте новый узел красного цвета так же, как вставку в двоичное дерево поиска: найдите правильное место (т. Е. Родительский узел нового узла) для вставки нового узла, пройдя по дереву от корня и сравнив новый ключ узла с ключом каждого узла по пути.
2. Исправьте нарушенное свойство красного-черного-дерева поворотом и раскраской.

Поскольку новый узел красный, мы можем нарушить свойство красного-черного-дерева - если узел красный, то оба его дочерних узла черные, и мы можем исправить нарушение после вставки.

Мы можем реализовать вставку красно-черного дерева аналогично обычной вставке двоичного дерева поиска.

def insert(self, key: Any, data: Any) -> None:
    # Color the new node as red.
    new_node = Node(key=key, data=data, color=Color.RED)
    parent: Union[Node, Leaf] = self._NIL
    current: Union[Node, Leaf] = self.root
    while isinstance(current, Node):  # Look for the insert location
        parent = current
        if new_node.key < current.key:
            current = current.left
        elif new_node.key > current.key:
            current = current.right
        else:
            raise tree_exceptions.DuplicateKeyError(key=new_node.key)
    new_node.parent = parent
    # If the parent is a Leaf, set the new node to be the root.
    if isinstance(parent, Leaf):
        new_node.color = Color.BLACK
        self.root = new_node
    else:
        if new_node.key < parent.key:
            parent.left = new_node
        else:
            parent.right = new_node

        # After the insertion, fix the broken red-black-tree-property.
        self._insert_fixup(new_node)

Одно из отличий от Двоичного дерева поиска: Вставка состоит в том, что мы используем isinstance, чтобы проверить, является ли узел обычным Узлом или Leaf, вместо того, чтобы проверять, является ли он Нет. Это потому, что у нас есть тип Leaf для конечных узлов и тип Node для обычных узлов.

После того, как новый узел вставлен в красно-черное дерево, нам нужно исправить нарушенное свойство красного-черного-дерева. В следующих подразделах мы обсудим использование поворота и раскраски для исправления сломанного красно-черного дерева.

Вращения

Операция вращения предназначена для изменения формирования красно-черного дерева, а также для сохранения его свойств двоичного поиска. Есть два типа вращения: левое вращение и правое вращение.

Вращение влево

Вращение влево перемещает два узла (x и y на рисунке) из верхнего дерева в нижнее дерево изображения и сохраняет его свойства двоичного дерева поиска.

def _left_rotate(self, node_x: Node) -> None:
    node_y = node_x.right  # Set node y
    if isinstance(node_y, Leaf):  # Node y cannot be a Leaf
        raise RuntimeError("Invalid left rotate")

    # Turn node y's subtree into node x's subtree
    node_x.right = node_y.left
    if isinstance(node_y.left, Node):
        node_y.left.parent = node_x
    node_y.parent = node_x.parent

    # If node's parent is a Leaf, node y becomes the new root.
    if isinstance(node_x.parent, Leaf):
        self.root = node_y
    # Otherwise, update node x's parent.
    elif node_x == node_x.parent.left:
        node_x.parent.left = node_y
    else:
        node_x.parent.right = node_y

    node_y.left = node_x
    node_x.parent = node_y

Обратите внимание, что правый дочерний элемент узла x не может быть Leaf (т. Е. NIL); Нет смысла вращать Leaf.

Поворот вправо

Правое вращение симметрично левому вращению и может быть реализовано следующим образом.

def _right_rotate(self, node_x: Node) -> None:
    node_y = node_x.left  # Set node y
    if isinstance(node_y, Leaf):  # Node y cannot be a Leaf
        raise RuntimeError("Invalid right rotate")
    # Turn node y's subtree into node x's subtree
    node_x.left = node_y.right
    if isinstance(node_y.right, Node):
        node_y.right.parent = node_x
    node_y.parent = node_x.parent

    # If node's parent is a Leaf, node y becomes the new root.
    if isinstance(node_x.parent, Leaf):
        self.root = node_y
    # Otherwise, update node x's parent.
    elif node_x == node_x.parent.right:
        node_x.parent.right = node_y
    else:
        node_x.parent.left = node_y

    node_y.right = node_x
    node_x.parent = node_y

Исправить

Чтобы восстановить свойство красного-черного-дерева, нам нужно знать, какие свойства красного-черного могут быть нарушены после вставки.

Красно-черное-дерево-свойство:

1. Каждый узел красный или черный (не может быть сломан).
2. Корень черный.
3. Каждый лист черный (не может быть сломан, поскольку каждый новый дочерний узел указывает на Leaf).
4. Если узел красный, то оба его дочерних элемента черные.
5. Весь путь каждого узла от узла к листьям содержит одинаковое количество черных узлов (также известную как черная высота).

Для 5-го объекта высота черного осталась прежней. Новый узел (как красный цвет) заменяет Leaf (NIL), но его дочерние элементы также являются Leaf (NIL ). Следовательно, свойство высоты черного сохраняется после вставки.

Таким образом, могут быть нарушены только свойство 2 и свойство 4, поскольку цвет нового узла красный. Если родительский узел нового узла также красный, свойство 4 нарушено. Что касается свойства 2, оно может быть нарушено, если новый узел является корнем или корень становится красным при исправлении свойства 4. И мы можем исправить свойство два, покрасив его в черный цвет в конце процедуры исправления.

Что касается фиксации свойства 4, мы можем разбить его на шесть случаев (два из трех - симметрично). Шесть вариантов определяются расположением и цветом родителя нового узла и брата родителя.

Начните с нового узла (fixing_node).

Случай 1

• Измените цвет родительского элемента fixing_node и его брата на черный
• Измените цвет прародителя fixing_node на красный
• Переместите текущее местоположение к прародителю fixing_node

Обратите внимание, что местоположение нового узла не имеет значения. На следующем рисунке показаны случаи 1. Новый узел (7) является левым дочерним элементом, а 2. Новый узел (18) является правым дочерним элементом.

Случай 2

• Выполните поворот влево родительского элемента fixing_node (эта операция переводит случай 2 в случай 3)

Случай 3

• Измените цвет родительского элемента fixing_node на черный
• Измените цвет прародителя fixing_node на красный
• Выполните поворот вправо на бабушке и дедушке fixing_node

Случай 4 (такой же, как случай 1)

• Измените цвет родительского элемента fixing_node и его брата на черный
• Измените цвет прародителя fixing_node на красный
• Переместите текущее местоположение к прародителю fixing_node

Случай 5

• Выполните поворот вправо на родительском элементе fixing_node (эта операция переводит случай 5 в случай 6)

Случай 6

• Измените цвет родительского элемента fixing_node на черный
• Измените цвет прародителя fixing_node на красный

При исправлении нарушенного свойства красного-черного-дерева для fixing_node процесс исправления может привести к тому, что родитель или дедушка fixing_node (в зависимости от случая) нарушит красный-черный-дерево-свойство. Когда это происходит, родитель (или дедушка) fixing_node становится новым fixing_node. Тогда мы сможем решить ее согласно шести случаям. Повторяйте этот шаг, пока не дойдем до корня. Если корень становится красным (нарушено свойство 2) после операций исправления, мы можем исправить это, покрасив корень в черный цвет.

На рисунке ниже показана полная операция вставки для построения красно-черного дерева.

Реализация исправления вставки показана ниже.

def _insert_fixup(self, fixing_node: Node) -> None:
    while fixing_node.parent.color == Color.RED:
        if fixing_node.parent == fixing_node.parent.parent.left:
            parent_sibling = fixing_node.parent.parent.right
            if parent_sibling.color == Color.RED:  # Case 1
                fixing_node.parent.color = Color.BLACK
                parent_sibling.color = Color.BLACK
                fixing_node.parent.parent.color = Color.RED
                fixing_node = fixing_node.parent.parent
            else:
                # Case 2
                if fixing_node == fixing_node.parent.right:
                    fixing_node = fixing_node.parent
                    self._left_rotate(fixing_node)
                # Case 3
                fixing_node.parent.color = Color.BLACK
                fixing_node.parent.parent.color = Color.RED
                self._right_rotate(fixing_node.parent.parent)
        else:
            parent_sibling = fixing_node.parent.parent.left
            if parent_sibling.color == Color.RED:  # Case 4
                fixing_node.parent.color = Color.BLACK
                parent_sibling.color = Color.BLACK
                fixing_node.parent.parent.color = Color.RED
                fixing_node = fixing_node.parent.parent
            else:
                # Case 5
                if fixing_node == fixing_node.parent.left:
                    fixing_node = fixing_node.parent
                    self._right_rotate(fixing_node)
                # Case 6
                fixing_node.parent.color = Color.BLACK
                fixing_node.parent.parent.color = Color.RED
                self._left_rotate(fixing_node.parent.parent)

    self.root.color = Color.BLACK

Поиск

Операция поиска аналогична Двоичному дереву поиска: поиск, но мы используем Leaf (NIL), чтобы определить, достигаем ли мы листа.

1. Пройдите по дереву от корня и сравните ключ с ключом каждого узла в обходе дерева.
2. Если ключ совпадает, мы нашли узел.
3. Если мы дойдем до Leaf, узел не существует в дереве.

Поиск реализован аналогично функции поиска по двоичному дереву поиска.

def search(self, key: Any) -> Optional[Node]:
    current = self.root

    while isinstance(current, Node):
        if key < current.key:
            current = current.left
        elif key > current.key:
            current = current.right
        else:  # Key found
            return current
    # If the tree is empty (i.e., self.root == Leaf()), still return None.
    return None

Удалить

Подобно вставке красно-черного дерева, удаление изменяет красно-черное дерево, и результат может нарушить свойство красного-черного-дерева. Следовательно, нам нужно восстановить свойство красного-черного-дерева после удаления узла.

Основная идея удаления красно-черного дерева аналогична обычному Двоичное дерево поиска: Удалить. У нас есть метод трансплантации, позволяющий заменить поддерево с корнем в deleting_node поддеревом с корнем в замещающем_узле. У нас также есть три основных случая удаления: без дочернего элемента, только один дочерний элемент и два дочерних элемента. И, наконец, нам нужно исправить неработающее свойство красного-черного-дерева.

Пересадка

Метод трансплантации является модификацией Двоичного дерева поиска: Удалить, поэтому он подходит для красно-черного дерева. Модификация заключается в том, что мы используем isinstance, чтобы проверить, является ли узел нормальным Узлом или Leaf, вместо того, чтобы проверять, является ли он None.

def _transplant(
    self, deleting_node: Node, replacing_node: Union[Node, Leaf]
) -> None:
    if isinstance(deleting_node.parent, Leaf):
        self.root = replacing_node
    elif deleting_node == deleting_node.parent.left:
        deleting_node.parent.left = replacing_node
    else:
        deleting_node.parent.right = replacing_node

    if isinstance(replacing_node, Node):
        replacing_node.parent = deleting_node.parent

Общая процедура удаления похожа на обычное двоичное дерево поиска с некоторыми изменениями.

1. Найдите узел, который нужно удалить (deleting_node).
2. Сохраните цвет deleting_node.
3. Если у deleting_node нет или только один дочерний элемент, используйте метод transplant, чтобы заменить deleting_node на NIL или единственный ребенок.
4. Если у deleting_node есть два дочерних элемента, найдите преемника deleting_node в качестве replaceing_node. Сохраните цвет replace_node. Воспользуйтесь методом трансплантации, чтобы удалить замещающий_узел и продолжить отслеживание узла, чтобы заменить замещающий_узел, либо NIL, либо замещающий_узел изначальный правый ребенок. Используйте метод трансплантации, чтобы заменить deleting_node на replaceing_node. Раскрасьте замещающий_узел в цвет удаляющего_узла.
5. Исправьте нарушенное свойство красного-черного-дерева, изменив цвета и выполнив вращения.

Основываясь на описанной выше процедуре удаления, мы можем реализовать метод удаления следующим образом.

def delete(self, key: Any) -> None:
    if (deleting_node := self.search(key=key)) and (
        not isinstance(deleting_node, Leaf)
    ):
        original_color = deleting_node.color

        # Case 1: no children or Case 2a: only one right child
        if isinstance(deleting_node.left, Leaf):
            replacing_node = deleting_node.right
            self._transplant(
                deleting_node=deleting_node, replacing_node=replacing_node
            )
            # Fixup
            if original_color == Color.BLACK:
                if isinstance(replacing_node, Node):
                    self._delete_fixup(fixing_node=replacing_node)

        # Case 2b: only one left child
        elif isinstance(deleting_node.right, Leaf):
            replacing_node = deleting_node.left
            self._transplant(
                deleting_node=deleting_node, replacing_node=replacing_node
            )
            # Fixup
            if original_color == Color.BLACK:
                self._delete_fixup(fixing_node=replacing_node)

        # Case 3: two children
        else:
            replacing_node = self.get_leftmost(deleting_node.right)
            original_color = replacing_node.color
            replacing_replacement = replacing_node.right
            # The replacing node is not the direct child of the deleting node
            if replacing_node.parent != deleting_node:
                self._transplant(replacing_node, replacing_node.right)
                replacing_node.right = deleting_node.right
                replacing_node.right.parent = replacing_node

            self._transplant(deleting_node, replacing_node)
            replacing_node.left = deleting_node.left
            replacing_node.left.parent = replacing_node
            replacing_node.color = deleting_node.color
            # Fixup
            if original_color == Color.BLACK:
                if isinstance(replacing_replacement, Node):
                    self._delete_fixup(fixing_node=replacing_replacement)

Следует упомянуть следующее:

• Мы сохраняем исходный цвет (original_color) для deleting_node.
• Если у удаляемого узла есть два дочерних элемента, мы обновляем original_color до цвета узла (replaceacing_node).
• В конце каждого случая, если original_color черный, это означает, что какое-то свойство красного-черного-дерева нарушено, и нам нужно их исправить.

Перед восстановлением нарушенного свойства красного-черного-дерева нам нужно знать, какие свойства красного-черного могут быть нарушены во время процедуры удаления.

Красно-черное-дерево-свойство:

1. Каждый узел красный или черный (не может быть сломан).
2. Корень черный
3. Каждый лист черный (не может быть сломан, поскольку каждый новый дочерний узел указывает на Leaf).
4. Если узел красный, то оба его потомка черные.
5. Весь путь каждого узла от узла к листьям содержит одинаковое количество черных узлов (также известную как черная высота)

Случай 1. Удаляемый узел не имеет дочернего элемента

Если цвет deleting_node красный, свойство красного-черного-дерева не нарушено. Если цвет deleting_node черный, свойство 5 нарушено.

Случай 2. У удаляемого узла только один дочерний элемент

Из-за свойства красного-черного-дерева невозможно, чтобы у красного узла был только один черный дочерний элемент. Также невозможно, чтобы у черного узла был только один черный дочерний элемент. Следовательно, если deleting_node имеет только один дочерний элемент, его цвет должен быть черным, а цвет replaceing_node должен быть красным.

Согласно изображению выше, если deleting_node черный, свойство 4 и свойство 5 могут быть нарушены, а также свойство 2, если deleting_node является корневым.

Случай 3. У удаляемого узла двое дочерних узлов

В этом случае делаем следующие шаги:

1. Найдите крайний левый узел (replaceing_node) в качестве узла для замены deleting_node из правого поддерева deleting_node.
2. Извлеките replace_node, выполнив операцию трансплантации.
3. Установите замещающий_узел как новый корень правого поддерева удаляющего_узла.
4. Выполните операцию трансплантации, чтобы заменить deleting_node поддеревом, корнем которого является replaceacing_node.
5. Раскрасьте замещающий_узел в цвет удаляющего_узла

После шага 5 цвет replace_node такой же, как и deleting_node, поэтому свойство красного-черного-дерева не нарушается. Единственный шаг, который может нарушить свойство красного-черного-дерева, - это шаг 2. Когда мы выполняем операцию трансплантации на замещающем_узле, он оказывается либо в случае 1, либо в случай 2.

На следующих рисунках показано, как удаление узла с двумя дочерними элементами может нарушать, а может и не нарушать свойство красного-черного-дерева.

Случай, когда replaceing_node является прямым потомком deleting_node.

Случай, когда replaceing_node черный, а не прямой дочерний элемент deleting_node.

Случай, когда replaceing_node красный, а не прямой дочерний элемент deleting_node.

Таким образом, мы можем резюмировать ситуацию, в которой нам нужно исправить нарушенное свойство красного-черного-дерева.

Резюме также подразумевает, что свойство красного-черного-дерева все еще сохраняется в следующих ситуациях.

1. Удаляемый узел красный, и у него меньше двух дочерних узлов.
2. У удаляющего узла есть два дочерних узла, а заменяющий узел красный.

Причины:

• Высота черного не меняется. Свойство 5 выполнено.
• В первой ситуации удаляемый узел не может быть красным, если он является корневым; во второй ситуации крайний левый узел не может быть корнем. Свойство 2 выполнено.
• Если узел (первая или вторая ситуация) красный, его родительский и дочерний или дочерние элементы не могут быть красными. Таким образом, после удаления или перемещения последовательных красных узлов не может произойти. Свойство 4 выполнено.

Исправить

Чтобы исправить нарушенное свойство красного-черного-дерева, мы используем идею из Введение в алгоритмы, и процедура исправления сначала исправляет свойство 5 (оба значения черной высоты каждого узла от узла до листьев одинаковы) путем введения концепция двойного черного и красно-черного. Для высоты черного дважды черный и красно-черный дают 2 или 1 соответственно. И мы используем следующие значки, чтобы обозначить узлы с двойным черным и красно-черным цветом.

Когда мы используем функцию transplant для замены одного узла другим узлом, вместо замены узла мы сохраняем цвет обоих узлов и используем двойной черный и красно-черный для обозначения его цвета. Следовательно, если удаляемый узел имеет менее двух дочерних элементов, после функции трансплантация цвет заменяющего узла становится либо дважды черным, либо красно-черным. Если удаляемый узел имеет двух дочерних элементов, цвет замены крайнего левого узла становится либо дважды черным, либо красно-черным, когда мы используем функцию трансплант для удаления крайнего левого узла поддерева. с корнем удаляемого узла. Для простоты мы используем fixing_node, чтобы указать, что узел имеет двойной черный или красно-черный цвет. Обратите внимание, что на самом деле мы не окрашиваем fixing_node как двойной черный или красно-черный в реализации кода. Мы просто притворяемся, что у fixing_node есть лишний черный или красный цвет.

Таким образом будут устранены недопустимые значения высоты черного, и возможные неработающие случаи станут следующими:

У удаляемого узла нет дочерних

У удаляемого узла только один дочерний элемент

У удаляемого узла два дочерних элемента

Если удаляемый узел имеет двух дочерних элементов, узел, занимающий позицию крайнего левого узла, нарушает свойство красного-черного-дерева.

replace_node является прямым потомком deleting_node.

replace_node не является прямым потомком deleting_node.

Поскольку цвет fixing_node не является ни красным, ни черным, свойство 1 также нарушено. Теперь нам нужно восстановить свойство красного-черного-дерева 1, 2 и 4.

Если цвет fixing_node красно-черный, мы можем исправить это, покрасив его в черный цвет. Все сломанные красно-черные деревья восстановлены.

Оставшаяся нарушенная ситуация - двойная черная. Процедуру фиксации для этого можно разбить на четыре симметричных случая.

Обращения идентифицируются по расположению fixing_node, цвету дочернего элемента fixing_node и цвету дочерних элементов.

Начните с fixing_node.

Случай 1

• Измените цвет родственного узла на черный
• Измените цвет родительского элемента fixing_node на красный
• Поверните влево родительский элемент fixing_node
• Обновите родственный узел (родственный узел меняется из-за левого вращения)
• После операций, описанных выше, случай 1 переходит в случай 2, случай 3 или случай 4.

Случай 2

• Измените цвет брата или сестры на красный
• Переместите fixing_node вверх, т.е. новый fixing_node станет родительским элементом исходного fixing_node

Случай 3

• Измените цвет левого дочернего элемента брата или сестры на черный
• Измените цвет брата или сестры на красный
• Выполните правое вращение на родственном узле
• После операций, описанных выше, случай 3 переходит в случай 4.

Случай 4

• Измените цвет родственного элемента, чтобы он совпадал с цветом родительского элемента fixing_node
• Измените цвет родительского элемента fixing_node на черный
• Измените цвет правого дочернего узла дочернего узла на черный
• Поверните влево родительский элемент fixing_nopde
• После описанных выше операций все нарушенные свойства красного-черного-дерева восстановлены.

Случай 5

• Измените цвет родственного узла на черный
• Измените цвет родительского элемента fixing_node на красный
• Поверните вправо родительского элемента fixing_node
• Обновите родственный узел (родственный узел меняется из-за правого вращения)
• После операций, описанных выше, случай 1 переходит в случай 6, случай 7 или случай 8.

Случай 6

• Измените цвет брата или сестры на красный
• Переместите fixing_node вверх, т.е. новый fixing_node станет родительским элементом исходного fixing_node

Случай 7

• Измените цвет правого ребенка брата или сестры на черный
• Измените цвет брата или сестры на красный
• Выполните левое вращение на родственном узле
• После описанных выше операций случай 7 переходит в случай 8.

Случай 8

• Измените цвет родственного элемента, чтобы он совпадал с цветом родительского элемента fixing_node
• Измените цвет родительского элемента fixing_node на черный
• Измените цвет левого дочернего элемента дочернего узла на черный
• Поверните вправо родительского элемента fixing_nopde
• После описанных выше операций все нарушенные свойства красного-черного-дерева восстановлены.

Следующая реализация суммирует описанные выше процедуры исправления.

def _delete_fixup(self, fixing_node: Union[Leaf, Node]) -> None:
    while (fixing_node is not self.root) and (fixing_node.color == Color.BLACK):
        if fixing_node == fixing_node.parent.left:
            sibling = fixing_node.parent.right

            # Case 1: the sibling is red.
            if sibling.color == Color.RED:
                sibling.color == Color.BLACK
                fixing_node.parent.color = Color.RED
                self._left_rotate(fixing_node.parent)
                sibling = fixing_node.parent.right

            # Case 2: the sibling is black and its children are black.
            if (sibling.left.color == Color.BLACK) and (
                sibling.right.color == Color.BLACK
            ):
                sibling.color = Color.RED
                fixing_node = fixing_node.parent  # new fixing node

            # Cases 3 and 4: the sibling is black and one of
            # its child is red and the other is black.
            else:
                # Case 3: the sibling is black and its left child is red.
                if sibling.right.color == Color.BLACK:
                    sibling.left.color = Color.BLACK
                    sibling.color = Color.RED
                    self._right_rotate(node_x=sibling)

                # Case 4: the sibling is black and its right child is red.
                sibling.color = fixing_node.parent.color
                fixing_node.parent.color = Color.BLACK
                sibling.right.color = Color.BLACK
                self._left_rotate(node_x=fixing_node.parent)
                # Once we are here, all the violation has been fixed, so
                # move to the root to terminate the loop.
                fixing_node = self.root
        else:
            sibling = fixing_node.parent.left

            # Case 5: the sibling is red.
            if sibling.color == Color.RED:
                sibling.color == Color.BLACK
                fixing_node.parent.color = Color.RED
                self._right_rotate(node_x=fixing_node.parent)
                sibling = fixing_node.parent.left

            # Case 6: the sibling is black and its children are black.
            if (sibling.right.color == Color.BLACK) and (
                sibling.left.color == Color.BLACK
            ):
                sibling.color = Color.RED
                fixing_node = fixing_node.parent
            else:
                # Case 7: the sibling is black and its right child is red.
                if sibling.left.color == Color.BLACK:
                    sibling.right.color = Color.BLACK
                    sibling.color = Color.RED
                    self._left_rotate(node_x=sibling)
                # Case 8: the sibling is black and its left child is red.
                sibling.color = fixing_node.parent.color
                fixing_node.parent.color = Color.BLACK
                sibling.left.color = Color.BLACK
                self._right_rotate(node_x=fixing_node.parent)
                # Once we are here, all the violation has been fixed, so
                # move to the root to terminate the loop.
                fixing_node = self.root

    fixing_node.color = Color.BLACK

Вспомогательные функции

В дополнение к основным функциям (т.е. вставке, поиску и удалению) красно-черное дерево могло иметь другие полезные функции, такие как получение самого левого узла, получение преемника узла и получение высоты дерева, реализация которого аналогична Дереву двоичного поиска: вспомогательные функции, но с некоторыми изменениями.

Получить высоту

Чтобы вычислить высоту красно-черного дерева, мы можем рекурсивно увеличить высоту на единицу для высоты каждого дочернего элемента, как мы это делали в Двоичное дерево поиска: получить высоту. Если у узла два дочерних узла, мы используем функцию max, чтобы получить от дочерних узлов большую высоту и увеличить на единицу наибольшую высоту. Основное отличие состоит в том, что мы используем isinstance, чтобы проверить, есть ли у узла лист или нет.

@staticmethod
def get_height(node: Union[Leaf, Node]) -> int:
    if isinstance(node, Node):
        if isinstance(node.left, Node) and isinstance(node.right, Node):
            return (
                max(RBTree.get_height(node.left), RBTree.get_height(node.right)) + 1
            )

        if isinstance(node.left, Node):
            return RBTree.get_height(node=node.left) + 1

        if isinstance(node.right, Node):
            return RBTree.get_height(node=node.right) + 1

    return 0

Получите крайний левый и крайний правый узлы

Красно-черное дерево делает то же самое, что и Дерево двоичного поиска: получение крайних левых и крайних правых узлов, чтобы получить крайний правый узел данного (под) дерева и крайний левый узел данного (под) дерева. И снова мы используем isinstance, чтобы проверить, является ли узел обычным красно-черным узлом дерева или листом.

Крайний левый

@staticmethod
def get_leftmost(node: Node) -> Node:
    current_node = node
    while isinstance(current_node.left, Node):
        current_node = current_node.left
    return current_node

Крайний правый

@staticmethod
def get_rightmost(node: Node) -> Node:
    current_node = node
    while isinstance(current_node.right, Node):
        current_node = current_node.right
    return current_node

Предшественник и преемник

Красно-черное дерево делает то же самое, что и Дерево двоичного поиска: предшественник и преемник, чтобы получить предшественника и преемника узла.

Предшественник

@staticmethod
def get_predecessor(node: Node) -> Union[Node, Leaf]:
    if isinstance(node.left, Node):
        return RBTree.get_rightmost(node=node.left)
    parent = node.parent
    while isinstance(parent, Node) and node == parent.left:
        node = parent
        parent = parent.parent
    return node.parent

Преемник

@staticmethod
def get_successor(node: Node) -> Union[Node, Leaf]:
    if isinstance(node.right, Node):
        return RBTree.get_leftmost(node=node.right)
    parent = node.parent
    while isinstance(parent, Node) and node == parent.right:
        node = parent
        parent = parent.parent
    return parent

Обходы

Из-за листовых узлов мы не можем использовать функции обхода, реализованные в Обход двоичного дерева. Однако концепция обхода осталась прежней. Нам нужна только простая модификация: используйте isinstance, чтобы проверить, является ли узел обычным красно-черным узлом дерева или листом.

Обход по порядку

def inorder_traverse(self) -> traversal.Pairs:
    return self._inorder_traverse(node=self.root)

def _inorder_traverse(self, node: Union[Node, Leaf]) -> traversal.Pairs:
    if isinstance(node, Node):
        yield from self._inorder_traverse(node.left)
        yield (node.key, node.data)
        yield from self._inorder_traverse(node.right)

Обход предварительного заказа

def preorder_traverse(self) -> traversal.Pairs:
    return self._preorder_traverse(node=self.root)

def _preorder_traverse(self, node: Union[Node, Leaf]) -> traversal.Pairs:
    if isinstance(node, Node):
        yield (node.key, node.data)
        yield from self._preorder_traverse(node.left)
        yield from self._preorder_traverse(node.right)

Пост-заказ

def postorder_traverse(self) -> traversal.Pairs:
    return self._postorder_traverse(node=self.root)

def _postorder_traverse(self, node: Union[Node, Leaf]) -> traversal.Pairs:
    if isinstance(node, Node):
        yield from self._postorder_traverse(node.left)
        yield from self._postorder_traverse(node.right)
        yield (node.key, node.data)

Обратите внимание, что тип возвращаемого значения (traversal.Pairs) определен в traversal.py из Обход двоичного дерева.

Контрольная работа

Как всегда, у нас должно быть как можно больше модульных тестов для нашего кода. Здесь мы используем функцию basic_tree в conftest.py, которую мы создали в Построении двоичного дерева поиска, чтобы проверить наше красно-черное дерево. Проверьте test_red_black_tree.py для полного модульного теста.

Анализ

Как мы обсуждали в Дерево двоичного поиска: Анализ, мы знаем, что время выполнения операции двоичного дерева поиска основано на высоте дерева. Красно-черное дерево является самобалансирующимся двоичным деревом поиска и имеет высоту не более 2 * lg (n + 1) = O (lg n), где n - количество узлов. (Доказательство можно отсылать к лемме 13.1 Введение в алгоритмы). Таким образом, временная сложность красно-черного дерева может быть представлена ​​в таблице ниже.

Примеры

Из-за способности к самобалансировке Red-Black Tree широко используется в программах, в том числе для реализации других структур данных. Например, карта C ++ STL реализована в виде красно-черного дерева. В этом разделе используется красно-черное дерево, которое мы здесь реализуем, для реализации пары "ключ-значение" Map.

from typing import Any, Optional

from forest.binary_trees import red_black_tree
from forest.binary_trees import traversal

class Map:
    """Key-value Map implemented using Red-Black Tree."""

    def __init__(self) -> None:
        self._rbt = red_black_tree.RBTree()

    def __setitem__(self, key: Any, value: Any) -> None:
        """Insert (key, value) item into the map."""
        self._rbt.insert(key=key, data=value)

    def __getitem__(self, key: Any) -> Optional[Any]:
        """Get the data by the given key."""
        node = self._rbt.search(key=key)
        if node:
            return node.data
        return None

    def __delitem__(self, key: Any) -> None:
        """Remove a (key, value) pair from the map."""
        self._rbt.delete(key=key)

    def __iter__(self) -> traversal.Pairs:
        """Iterate the data in the map."""
        return self._rbt.inorder_traverse()

if __name__ == "__main__":

    # Initialize the Map instance.
    contacts = Map()

    # Add some items.
    contacts["Mark"] = "[email protected]"
    contacts["John"] = "[email protected]"
    contacts["Luke"] = "[email protected]"

    # Retrieve an email
    print(contacts["Mark"])

    # Delete one item.
    del contacts["John"]

    # Check the deleted item.
    print(contacts["John"])  # This will print None

    # Iterate the items.
    for contact in contacts:
        print(contact)

(Полный пример доступен на rbt_map.py)

Резюме

Хотя поддерживать свойство красного-черного-дерева сложно, его способность к самобалансировке делает Красно-Черное дерево более производительным, чем двоичное дерево поиска. Во многих случаях очень важно поддерживать сбалансированность дерева, поэтому усложнение красно-черного дерева того стоит. В следующей статье мы реализуем еще одно известное самобалансирующееся дерево - AVL Tree.

Первоначально опубликовано на https://shunsvineyard.info 1 мая 2021 г.