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

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

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

forest-python
├── forest
│   ├── __init__.py
│   ├── binary_trees
│   │   ├── __init__.py
│   │   ├── binary_search_tree.py
│   │   ├── double_threaded_binary_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_single_threaded_binary_trees.py
    └── test_traversal.py

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

Что такое двухпоточное двоичное дерево?

Как мы говорили в разделе Что такое бинарные деревья с нитями, двухпоточное бинарное дерево имеет символы обоих однопоточных бинарных деревьев: для любого пустого левого или правого атрибута пустые атрибуты связаны либо с предшественником в порядке или преемник: если левый атрибут пуст, левый атрибут указывает на предшественника узла; если правый атрибут пуст, правильный атрибут указывает на преемника узла.

Хотя добавление правого и левого потоков увеличивает сложность, двухпоточное дерево имеет преимущества обоих однопоточных деревьев.

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

Построить двухпоточное двоичное дерево поиска

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

Узел

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

Оба атрибута left_thread и right_thread являются булевыми переменными: True, если атрибут является потоком; False в противном случае.

@dataclass
class Node:
    key: Any
    data: Any
    left: Optional["Node"] = None
    right: Optional["Node"] = None
    parent: Optional["Node"] = None
    left_thread: bool = False
    right_thread: bool = False

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

Двухпоточное двоичное дерево имеет основные функции (вставка, удаление и поиск) для построения и изменения, а также другие вспомогательные функции, которые не привязаны к конкретному дереву, такие как получение крайнего левого узла и получение высоты дерева. Ту же самую функцию __repr__(), которую мы реализовали в двоичном дереве поиска, также можно использовать для целей отладки.

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

class DoubleThreadedBinaryTree:

    def __init__(self) -> None:
        self.root: Optional[Node] = None

    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) -> Optional[Node]:
        …

    @staticmethod
    def get_predecessor(node: Node) -> Optional[Node]:
        …

    @staticmethod
    def get_height(node: Optional[Node]) -> int:
        …

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

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

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

Вставлять

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

  1. Найдите подходящее место (т. е. родителя нового узла), чтобы вставить новый узел, пройдясь по дереву от корня и сравнивая ключ нового узла с ключом каждого узла на этом пути. При переходе к правому поддереву также проверьте переменную right_thread. Если переменная имеет значение True, мы достигаем конечного узла, а это родительский узел. Точно так же при переходе к левому поддереву мы проверяем left_thread. Если это true, мы достигаем листового узла и находим родительский узел узла, который нужно вставить.
  2. Обновите родительский атрибут нового узла, чтобы он указывал на родительский узел.
  3. Если новый узел является левым дочерним элементом родителя, скопируйте левый атрибут родителя в левый атрибут нового узла (левый атрибут родителя должен быть потоком перед вставкой) и установите для переменной left_thread значение Верно. Обновите левый атрибут родителя, чтобы он указывал на новый узел, и установите для left_thread родителя значение False.
  4. Если новый узел является правым потомком своего родителя, скопируйте атрибут right родителя в атрибут right нового узла (атрибутом right родителя должен быть поток перед вставкой) и установите для переменной right_thread значение Верно. Обновите атрибут right родительского узла, чтобы он указывал на новый узел, и установите для родительского элемента right_thread значение False.

На рисунке ниже показаны шаги вставки узла.

Реализация должна проверять и обновлять как левый, так и правый потоки.

def insert(self, key: Any, data: Any) -> None:
    node = Node(key=key, data=data)
    if self.root is None:
        self.root = node
    else:
        temp = self.root
        while temp:
            # Move to left subtree
            if node.key < temp.key:
                if temp.left_thread is False and temp.left:
                    temp = temp.left
                    continue
                else:
                    node.left = temp.left
                    temp.left = node
                    node.right = temp
                    node.right_thread = True
                    node.parent = temp
                    temp.left_thread = False
                    if node.left:
                        node.left_thread = True
                    break
            # Move to right subtree
            elif node.key > temp.key:
                if temp.right_thread is False and temp.right:
                    temp = temp.right
                    continue
                else:
                    node.right = temp.right
                    temp.right = node
                    node.left = temp
                    node.left_thread = True
                    temp.right_thread = False
                    node.parent = temp
                    if node.right:
                        node.right_thread = True
                    break
            else:
                raise tree_exceptions.DuplicateKeyError(key=key)

Поиск

Операция поиска аналогична однопоточным деревьям, но мы проверяем переменные left_thread и right_thread, чтобы определить, достигли ли мы листа.

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

Реализация аналогична поиску в однопотоковых бинарных деревьях с простой модификацией — проверять как left_thread, так и right_thread.

def search(self, key: Any) -> Optional[Node]:
    current = self.root
    while current:
        if key == current.key:
            return current
        elif key < current.key:
            if current.left_thread is False:
                current = current.left
            else:
                break
        else:  # key > current.key
            if current.right_thread is False:
                current = current.right
            else:
                break
    return None

Удалить

Как и удаление в любом другом бинарном дереве, удаление двухпоточного бинарного дерева можно разбить на три подслучая: удаляемый узел не имеет дочерних элементов, только один дочерний элемент или два дочерних элемента. Мы также используем метод трансплантации, который мы использовали в Двоичном дереве поиска: удаление, чтобы заменить поддерево удаляемым узлом. Хотя основная идея одна и та же, и функция transplant, и функция delete должны учитывать правый и левый потоки. Самое важное, что нам нужно иметь в виду, это то, что когда мы удаляем узел, если есть правый или левый атрибуты других узлов, которые указывают на удаляемый узел, нам нужно обновить потоки этих узлов (т. е. правый или левый). левые атрибуты).

Случай 1: Нет ребенка

Если у удаляемого узла нет дочерних элементов, атрибуты left и right пусты, а оба атрибута left_thread и right_thread имеют значение True. Что касается потоков, нам необходимо рассмотреть два случая. См. рисунок ниже.

Случай 2: только один ребенок

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

Случай 3: двое детей

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

3.a Правый потомок удаляемого узла также является самым левым узлом в правом поддереве. В этом случае у правого потомка должен быть только один правильный потомок. Следовательно, мы можем заменить удаляемый узел его правым дочерним элементом, как показано на рисунке ниже.

3.б. Правый дочерний элемент удаляющего узла также имеет двух дочерних элементов.

В этом случае мы находим самый левый узел из правого поддерева, чтобы заменить удаляемый узел. Обратите внимание, что когда мы удаляем самый левый узел из правого поддерева, он также попадает в случаи удаления: случай 1: нет дочернего элемента или случай 2: только один правый дочерний элемент. В противном случае это не может быть крайний левый узел.

Поэтому мы используем функцию transplant дважды: один раз, чтобы удалить самый левый узел, а другой, чтобы заменить удаляемый узел исходным самым левым узлом. На рисунке ниже показано рассмотрение потока при удалении.

Замещающий узел не имеет дочерних элементов:

У замещающего узла есть только один правый дочерний элемент:

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

def delete(self, key: Any) -> None:
    if self.root and (deleting_node := self.search(key=key)):

        # Case 1: no child
        if (deleting_node.left_thread or deleting_node.left is None) and (
            deleting_node.right_thread or deleting_node.right is None
        ):
            self._transplant(deleting_node=deleting_node, replacing_node=None)

        # Case 2a: only one right child
        elif (
            deleting_node.left_thread or deleting_node.left is None
        ) and deleting_node.right_thread is False:

            successor = self.get_successor(node=deleting_node)
            if successor:
                successor.left = deleting_node.left
            self._transplant(
                deleting_node=deleting_node, replacing_node=deleting_node.right
            )

        # Case 2b: only one left child,
        elif (
            deleting_node.right_thread or deleting_node.right is None
        ) and deleting_node.left_thread is False:

            predecessor = self.get_predecessor(node=deleting_node)
            if predecessor:
                predecessor.right = deleting_node.right
            self._transplant(
                deleting_node=deleting_node, replacing_node=deleting_node.left
            )

        # Case 3: two children
        elif deleting_node.left and deleting_node.right:
            predecessor = self.get_predecessor(node=deleting_node)
            replacing_node: Node = self.get_leftmost(node=deleting_node.right)
            successor = self.get_successor(node=replacing_node)

            # the leftmost node is not the direct child of the deleting node
            if replacing_node.parent != deleting_node:
                if replacing_node.right_thread:
                    self._transplant(
                        deleting_node=replacing_node, replacing_node=None
                    )
                else:
                    self._transplant(
                        deleting_node=replacing_node,
                        replacing_node=replacing_node.right,
                    )
                replacing_node.right = deleting_node.right
                replacing_node.right.parent = replacing_node
                replacing_node.right_thread = False

            self._transplant(
                deleting_node=deleting_node, replacing_node=replacing_node
            )
            replacing_node.left = deleting_node.left
            replacing_node.left.parent = replacing_node
            replacing_node.left_thread = False
            if predecessor and predecessor.right_thread:
                predecessor.right = replacing_node

            if successor and successor.left_thread:
                successor.left = replacing_node
        else:
            raise RuntimeError("Invalid case. Should never happened")

def _transplant(self, deleting_node: Node, replacing_node: Optional[Node]) -> None:
    if deleting_node.parent is None:
        self.root = replacing_node
        if self.root:
            self.root.left_thread = False
            self.root.right_thread = False
    elif deleting_node == deleting_node.parent.left:
        deleting_node.parent.left = replacing_node

        if replacing_node:
            if deleting_node.left_thread:
                if replacing_node.left_thread:
                    replacing_node.left = deleting_node.left

            if deleting_node.right_thread:
                if replacing_node.right_thread:
                    replacing_node.right = replacing_node.right
        else:
            deleting_node.parent.left = deleting_node.left
            deleting_node.parent.left_thread = True

    else:  # deleting_node == deleting_node.parent.right
        deleting_node.parent.right = replacing_node

        if replacing_node:
            if deleting_node.left_thread:
                if replacing_node.left_thread:
                    replacing_node.left = deleting_node.left

            if deleting_node.right_thread:
                if replacing_node.right_thread:
                    replacing_node.right = replacing_node.right
        else:
            deleting_node.parent.right = deleting_node.right
            deleting_node.parent.right_thread = True

    if replacing_node:
        replacing_node.parent = deleting_node.parent

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

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

@staticmethod
def get_height(node: Optional[Node]) -> int:
    if node:
        if node.left_thread is False and node.right_thread is False:
            return (
                max(
                    DoubleThreadedBinaryTree.get_height(node.left),
                    DoubleThreadedBinaryTree.get_height(node.right),
                )
                + 1
            )

        if node.left_thread and node.right_thread is False:
            return DoubleThreadedBinaryTree.get_height(node.right) + 1

        if node.right_thread and node.left_thread is False:
            return DoubleThreadedBinaryTree.get_height(node.left) + 1

    return 0

Получите самые левые и самые правые узлы

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

@staticmethod
def get_leftmost(node: Node) -> Node:
    current_node = node
    while current_node.left and current_node.left_thread is False:
        current_node = current_node.left
    return current_node

Реализация get_rightmost симметрична реализации get_leftmost.

@staticmethod
def get_rightmost(node: Node) -> Node:
    current_node = node
    if current_node:
        while current_node.right and current_node.right_thread is False:
            current_node = current_node.right
    return current_node

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

Двухпоточное дерево имеет как левые, так и правые потоки, поэтому оно имеет быстрый доступ к преемнику и предшественнику по порядку.

@staticmethod
def get_predecessor(node: Node) -> Optional[Node]:
    if node.left_thread:
        return node.left
    else:
        if node.left:
            return DoubleThreadedBinaryTree.get_rightmost(node=node.left)
        return None

get_successor симметричен get_predecessor.

@staticmethod
def get_successor(node: Node) -> Optional[Node]:
    if node.right_thread:
        return node.right
    else:
        if node.right:
            return DoubleThreadedBinaryTree.get_leftmost(node=node.right)
        return None

Обходы в порядке, предварительном порядке и в обратном порядке

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

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

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

  1. Начните с самого левого узла всего дерева.
  2. Если правильный атрибут — поток, следуйте правильному атрибуту; если правый атрибут не является потоком, перейти к самому левому узлу поддерева.
  3. Повторяйте шаг 2, пока правильный атрибут не станет Нет.

И реализовать функцию без использования вспомогательного стека или рекурсии.

def inorder_traverse(self) -> traversal.Pairs:
    if self.root:
        current: Optional[Node] = self.get_leftmost(node=self.root)
        while current:
            yield (current.key, current.data)
            if current.right_thread:
                current = current.right
            else:
                if current.right is None:
                    break
                current = self.get_leftmost(current.right)

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

Следующие красные стрелки на рисунке ниже показывают обход предзаказа резьбового пути.

  1. Начните с корня.
  2. Если левый атрибут не пуст, перейдите к левому дочернему элементу.
  3. Если левый атрибут пуст или представляет собой поток, следуйте за правым потоком вправо.
  4. Повторяйте шаги 2 и 3, пока правильный атрибут не станет пустым.

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

def preorder_traverse(self) -> traversal.Pairs:
    current = self.root
    while current:
        yield (current.key, current.data)
        if current.right_thread:
            # If it is right thread, it must have a right child.
            current = current.right.right  # type: ignore
        elif current.left_thread is False:
            current = current.left
        else:
            break

Обход в обратном порядке

Красные стрелки на картинке ниже демонстрируют нитевой способ обратного обхода по порядку.

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

Далее идет реализация.

def reverse_inorder_traverse(self) -> traversal.Pairs:
    if self.root:
        current: Optional[Node] = self.get_rightmost(node=self.root)
        while current:
            yield (current.key, current.data)
            if current.left_thread:
                current = current.left
            else:
                if current.left is None:
                    break
                current = self.get_rightmost(current.left)

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

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

Анализ

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

И он имеет постоянную пространственную сложность при обходах по порядку, предварительному порядку и обратному порядку.

Пример

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

from typing import Any

from forest.binary_trees import double_threaded_binary_tree
from forest.binary_trees import traversal

class MyDatabase:
    """Example using threaded binary trees to build index."""

    def __init__(self) -> None:
        self._double_bst = double_threaded_binary_tree.DoubleThreadedBinaryTree()

    def _persist(self, payload: Any) -> str:
        """Fake function pretent storing data to file system.

        Returns
        -------
        str
            Path to the payload.
        """
        return f"path_to_{payload}"

    def insert_data(self, key: Any, payload: Any) -> None:
        """Insert data.

        Parameters
        ----------
        key: Any
            Unique key for the payload
        payload: Any
            Any data
        """
        path = self._persist(payload=payload)
        self._double_bst.insert(key=key, data=path)

    def dump(self, ascending: bool = True) -> traversal.Pairs:
        """Dump the data.

        Parameters
        ----------
        ascending: bool
            The order of data.

        Yields
        ------
        `Pairs`
            The next (key, data) pair.
        """
        if ascending:
            return self._double_bst.inorder_traverse()
        else:
            return self._double_bst.reverse_inorder_traverse()

if __name__ == "__main__":

    # Initialize the database.
    my_database = MyDatabase()

    # Add some items.
    my_database.insert_data("Adam", "adam_data")
    my_database.insert_data("Bob", "bob_data")
    my_database.insert_data("Peter", "peter_data")
    my_database.insert_data("David", "david_data")

    # Dump the items in ascending order.
    print("Ascending...")
    for contact in my_database.dump():
        print(contact)

    print("\nDescending...")
    # Dump the data in decending order.
    for contact in my_database.dump(ascending=False):
        print(contact)

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

Вывод будет выглядеть так, как показано ниже.

Ascending...
('Adam', 'path_to_adam_data')
('Bob', 'path_to_bob_data')
('David', 'path_to_david_data')
('Peter', 'path_to_peter_data')

Descending...
('Peter', 'path_to_peter_data')
('David', 'path_to_david_data')
('Bob', 'path_to_bob_data')
('Adam', 'path_to_adam_data')

Резюме

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

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