在 Python 中构建森林系列：双向二叉搜索树

Shun Huang

5.00/5 (2投票s)

2021年4月10日

CPOL

9分钟阅读

6292

使用 Python 构建双向二叉搜索树。

项目设置

遵循构建二叉搜索树中其他文章的相同风格和假设，该实现假设 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

与二叉搜索树节点一样，我们将线索二叉树的节点类定义为数据类。

双线索二叉树具有用于构建和修改的核心功能（insert、delete 和 search）以及不与特定树绑定的其他辅助功能，例如获取最左边的节点和获取树的高度。我们在二叉搜索树中实现的相同 __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:
        …

Insert

insert 操作与单线索二叉树类似，但双线索树需要同时考虑左右线索的更新。

通过从根遍历树并比较新节点的键与沿途每个节点的键来找到插入新节点的正确位置（即新节点的父节点）。向右子树遍历时，也要检查 right_thread 变量。如果该变量为 True，则表示我们到达了叶节点，这就是父节点。类似地，向左子树遍历时，我们检查 left_thread。如果它为 true，则表示我们到达了叶节点并找到了要插入的节点的父节点。
更新新节点的 parent 属性以指向父节点。
如果新节点是父节点的左子节点，则将父节点的左属性复制到新节点的左属性（父节点的左属性在插入前必须是线索），并将 left_thread 变量设置为 True。更新父节点的左属性以指向新节点，并将父节点的 left_thread 设置为 False。
如果新节点是其父节点的右子节点，则将父节点的右属性复制到新节点的右属性（父节点的右属性在插入前必须是线索），并将 right_thread 变量设置为 True。更新父节点的右属性以指向新节点，并将父节点的 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 变量以确定是否到达叶节点。

从根遍历树，并沿树遍历比较键与每个节点的键
如果键匹配，则找到了该节点。
如果在 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_thread 和 right_thread 都为 True。关于线索，我们需要考虑两种情况。见下图。

情况 2：只有一个子节点

如果要删除的节点只有一个子节点，无论是左子节点还是右子节点，我们总是需要更新其线索：如果删除节点是左子节点，则更新删除节点交互的右线索。如果删除节点是右子节点，则更新指向它的左线索。需要更新线索的情况如下图所示。

情况 3：有两个子节点

与二叉搜索树删除类似，要删除的节点有两个子节点的情况可以分解为两个子情况

3.a. 删除节点的右子节点也是右子树中最左边的节点。在这种情况下，右子节点必须只有一个右子节点。因此，我们可以用其右子节点替换删除节点，如下图所示。

3.b. 删除节点的右子节点也有两个子节点。

在这种情况下，我们从右子树中找到最左边的节点来替换要删除的节点。请注意，当我们从右子树中取出最左边的节点时，它也属于删除情况：情况 1：无子节点或情况 2：只有一个右子节点。否则，它不能是最左边的节点。

因此，我们使用 transplant 函数两次：一次用于取出最左边的节点，另一次用于用原始最左边的节点替换删除节点。下图演示了执行删除时线索的考虑。

替换节点没有子节点

替换节点只有一个右子节点:

根据上图，我们可以如下实现 delete 和 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 是否为 True。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

中序、前序和反向中序遍历

双线索树具有左右线索树的优点，因此无需使用堆栈或递归方法即可执行中序、前序和反向中序遍历。

中序遍历

下图中的红色箭头演示了线索树中的中序遍历。

从整个树的最左边节点开始。
如果右属性是线索，则沿着右属性移动；如果右属性不是线索，则转到子树的最左边节点。
重复步骤 2，直到右属性为 None。

并实现不使用辅助堆栈或递归的函数。

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)

前序遍历

下图中的红色箭头显示了线索方式的前序遍历。

从根节点开始。
如果左属性不为空，则转到左子节点。
如果左属性为空或线索，则沿着右线索向右移动。
重复步骤 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

反中序遍历

下图中的红色箭头演示了线索方式的反向中序遍历。

从整个树的最右边节点开始。
如果左属性是线索，则沿着线索移动；如果左属性不是线索，则转到子树的最右边节点。
重复步骤 2，直到左属性为 None。

以下是实现：

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)

测试

一如既往，我们应该尽可能地为我们的代码编写单元测试。在这里，我们使用在构建二叉搜索树中创建的 conftest.py 中的 basic_tree 函数来测试我们的双线索二叉树。有关完整的单元测试，请查看 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')

摘要

双线索树确实提供了单线索二叉树的所有优点，但其实现比单线索二叉树更复杂。此外，运行时性能没有显著提高。然而，在某些情况下，例如关注空间复杂性且特定遍历（例如中序遍历）至关重要时，双线索二叉树可能是一个选择。

历史

2021年4月9日：初始版本