在 Python 中构建森林系列：二叉搜索树
5.00/5 (1投票)
使用 Python 构建二叉搜索树。
引言
构建软件项目很难，它还需要广泛的知识，例如编写代码、理解算法、设置环境、测试和部署。此外，每种语言都有其实现事物的方式，即使所有语言都是面向对象编程语言。养成从不同角度思考软件开发的习惯需要时间。本项目“Build the Forest Series”试图通过用 Python 的方式以面向对象编程构建一些树形数据结构（森林）来提供学习软件开发和树形数据结构的不同视角。
为什么要使用树？
树是基本的数据结构，可解决软件中许多问题。此外，几乎所有的软件工程师职位面试都会问到与树相关的问题。虽然我们可能不需要在日常工作中从头开始实现树形数据结构，但对树形数据结构有扎实的理解有助于我们解决许多问题。
假设
本项目假定读者使用 Python 3.9 或更高版本，并具备 Python 编程和数据结构的基本知识。此外，为了简化起见，实现不考虑多线程，即不是线程安全的。
项目设置
项目具有以下基本布局
forest-python
├── forest
│ ├── __init__.py
│ ├── binary_trees
│ │ ├── __init__.py
│ │ └── binary_search_tree.py
│ └── tree_exceptions.py
└── tests
├── __init__.py
├── conftest.py
└── test_binary_search_tree.py
（项目可在 forest-python 获取。）
与编译型语言（例如 C++ 和 Java）不同，Python 没有编译器为我们检查错误，因此我们需要使用额外的工具。在此项目中，我们使用以下工具来确保代码质量。
- Flake8 是一个用于查找 Python 源代码中错误和风格问题的工具。
- 这是一个 Python 程序的静态类型检查器。虽然 Python 是一种动态语言，但类型检查有助于防止潜在的错误和问题。
- Pydocstyle 用于文档风格检查
- Black 用于代码风格检查
- pytest 用于单元测试
此外，代码还遵循 我的 Python 编码风格和原则。
什么是二叉搜索树？
二叉搜索树是一种二叉树，其键始终满足二叉搜索树属性
- 设 x 是二叉搜索树中的一个节点。
- 如果 y 是 x 的左子树中的一个节点，则
y.key < x.key。 - 如果 y 是 x 的右子树中的一个节点，则
y.key > x.key。
请注意，如果二叉搜索树允许重复键，则 y.key = x.key 是一个特殊情况。为简单起见，本项目不允许重复键，即所有键必须是唯一的。
二叉搜索树数据结构支持许多动态操作。最基本的功能是 search（查找）、insert（插入）和 delete（删除）。还可以支持其他辅助操作，包括获取最小键、最大键、节点的先前节点和后继节点。
构建二叉搜索树
本节将介绍实现过程以及一些关于实现选择的思考。
节点
二叉搜索树节点是二叉搜索树的构建块。
树节点可以出现在上图所示，并具有以下属性
- key 是构建二叉搜索树的基本字段，它必须满足二叉搜索树属性，并且其值必须是可比较的。
- left 属性指向左节点。
- right 属性指向右节点。
- parent 属性指向父节点，并且
- data 字段用于包含任何数据。
数据结构的目的是管理数据。虽然许多教科书为了简洁而省略了 data 字段，但在现实世界中，如果树节点不包含任何数据，它就没有用处。这就是我们的节点定义包含 data 字段的原因。
为什么要有 parent？ parent 不是二叉搜索树定义的必需项，但它简化了实现，因此我们在进行树操作时无需跟踪父节点。如果关心空间使用，可以使用不包含 parent 字段的树节点来实现二叉搜索树。
考虑到以上想法，我们可以按以下方式定义节点类
@dataclasses.dataclass
class Node:
key: Any
data: Any
left: Optional["Node"] = None
right: Optional["Node"] = None
parent: Optional["Node"] = None
为什么要使用 dataclass？
Python 在 3.7 版本中引入了 dataclass，它主要用于仅包含数据的类。当一个类被定义为 dataclass 时，dataclass 装饰器为我们提供了一些基本功能，例如 __init__() 和 __repr__() 函数。因此，dataclass 提供了一种方便的方式来定义主要用于数据的类，并提高了可读性。由于我们的树节点仅用于数据，因此将其定义为 dataclass 是有意义的。
异常
在我们的二叉搜索树中，有一种情况我们希望抛出异常，那就是当我们尝试插入一个键已存在于树中的节点时。Python 提供了几种内置异常。但是，没有一种适用于重复键的情况。因此，我们为此目的定义了自己的异常。在 tree_exceptions.py 中，我们添加了异常。
class DuplicateKeyError(Exception):
def __init__(self, key: str) -> None:
Exception.__init__(self, f"{key} already exists.")
这个对象清楚地说明了异常的原因，并告诉我们哪个键是重复的。
核心功能
就像一棵真实的树有根、分支和叶子一样，我们将树视为一个对象。因此，我们将二叉搜索树定义为一个类，并使用它来声明二叉搜索树对象。BinarySearchTree 类应该具有最少的功能——insert（插入）、delete（删除）和 search（查找），这样我们就可以增长、修剪和查找树。
class BinarySearchTree:
def __init__(self) -> None:
self.root: Optional[Node] = None
def search(self, key: Any) -> Optional[Node]:
…
def insert(self, key: Any, data: Any) -> None:
…
def delete(self, key: Any) -> None:
…
Insert
为了构建 BinarySearchTree，我们首先需要将一个树节点插入到树中，新节点总是添加到叶子级别。以下步骤总结了插入算法。
- 通过从根遍历树并逐个比较新节点的键与每个节点的键，找到插入新节点的合适位置（即新节点的父节点）。
- 找到父节点后，更新父节点的 left（或 right，取决于位置）以指向新节点。
- 更新新节点的 parent 属性以指向父节点。
下图可视化了插入算法的每个步骤。
该接口接受 key 和 data 作为参数，并使用它们来构造一个新的树节点。然后，根据二叉搜索树属性找到合适的插入节点的位置。因此，我们按以下方式实现 insert 函数
def insert(self, key: Any, data: Any) -> None:
new_node = Node(key=key, data=data)
parent: Optional[Node] = None
current: Optional[Node] = self.root
while current:
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 tree is empty
if parent is None:
self.root = new_node
elif new_node.key < parent.key:
parent.left = new_node
else:
parent.right = new_node
搜索
search（查找）算法与插入类似。我们按给定的键查找节点。
- 从根遍历树，并在树遍历过程中将键与每个节点的键进行比较。
- 如果键匹配，则找到了该节点。
- 如果在到达叶子级别后没有找到匹配的键，则表示节点不存在于树中。
我们可以通过下图可视化搜索步骤
并如下实现 search 方法
def search(self, key: Any) -> Optional[Node]:
current = self.root
while current:
if key < current.key:
current = current.left
elif key > current.key:
current = current.right
else:
return current
return None
需要注意的是，如果节点不存在，我们返回 None。客户端有责任检查搜索函数是否返回 None，并且一个不存在于树中的给定键是正常的。
删除
二叉搜索树的删除有三种情况——要删除的节点没有子节点、有一个子节点或有两个子节点。
删除节点的思路是用要删除的节点替换一个子树。该技术来自 《算法导论》。在该书中，作者定义了一个 transplant（移植）方法来在二叉搜索树内移动子树。使用 transplant 方法，我们可以利用该方法来实现三种删除情况。因此，本节从 transplant 函数开始，然后是三种删除情况。
移植
transplant 方法用 replacing_node（替换节点）为根的子树替换 deleting_node（删除节点）为根的子树。在 replacing_node 替换 deleting_node 之后，deleting_node 的父节点成为 replacing_node 的父节点，而 deleting_node 的父节点最终将 replacing_node 作为其子节点。由于该函数是内部函数，我们用下划线开头定义该函数，即 _transplant。
def _transplant(self, deleting_node: Node, replacing_node: Optional[Node]) -> None:
if deleting_node.parent is None:
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 replacing_node:
replacing_node.parent = deleting_node.parent
情况 1：无子节点
如果要删除的节点没有子节点，则使用 transplant 函数将该节点替换为 None。
情况 2：只有一个子节点
如果要删除的节点只有一个子节点，无论子节点是左子节点还是右子节点，都使用 transplant 函数替换子节点。
只有一个左子节点
只有一个右子节点
情况 3：有两个子节点
要删除的节点有两个子节点的情况可以分解为两种子情况
3.a 要删除的节点的右子节点也是右子树中最左边的节点。
在这种情况下，右子节点必须只有一个右子节点。否则，它就不能是最左边的节点。因此，我们可以用其右子节点替换要删除的节点，如下图所示
3.b. 要删除的节点的右子节点也有两个子节点。
在这种情况下，我们找到右子树中最左边的节点来替换要删除的节点。请注意，当我们从右子树中取出最左边的节点时，它也属于删除情况：情况 1：无子节点或情况 2：只有一个右子节点。否则，它就不能是最左边的节点。
因此，我们使用 transplant 函数两次：一次是取出最左边的节点，另一次是用原始最左边的节点替换要删除的节点。下图演示了这种情况的步骤。
以下步骤是删除过程
- 查找要删除的节点。
- 如果要删除的节点没有子节点，则用
None替换该节点。 - 如果要删除的节点只有一个子节点，则用其子节点替换该节点。
- 如果要删除的节点有两个子节点
- 找到右子树中最左边的节点
- 如果最左边的节点也是要删除节点的直接子节点，则用该子节点替换要删除的节点
- 如果右子节点也有两个子节点，
- 通过执行与情况：无子节点或只有一个右子节点相同的方式，取出最左边的节点
- 将最左边的节点作为右子树的新根
- 用右子树的新根替换要删除的节点
有了该算法，我们可以如下实现 delete 方法
def delete(self, key: Any) -> None:
if self.root and (deleting_node := self.search(key=key)):
# Case 1: no child or Case 2a: only one right child
if deleting_node.left is None:
self._transplant(
deleting_node=deleting_node, replacing_node=deleting_node.right
)
# Case 2b: only one left left child
elif deleting_node.right is None:
self._transplant(
deleting_node=deleting_node, replacing_node=deleting_node.left
)
# Case 3: two children
else:
replacing_node = BinarySearchTree.get_leftmost(node=deleting_node.right)
# The leftmost node is not the direct child of the deleting node
if replacing_node.parent != deleting_node:
self._transplant(
deleting_node=replacing_node,
replacing_node=replacing_node.right,
)
replacing_node.right = deleting_node.right
replacing_node.right.parent = replacing_node
self._transplant(
deleting_node=deleting_node, replacing_node=replacing_node
)
replacing_node.left = deleting_node.left
replacing_node.left.parent = replacing_node
辅助函数
除了核心功能外，二叉搜索树可能还有其他有用的功能，例如获取最左边的节点、获取节点的后继节点以及获取树的高度。这些功能与特定树对象无关。相反，它们可以应用于任何树和任何给定的子树。因此，我们将这些功能定义为独立的函数，而不是 BinarySearchTree 类的方法。
在本例中，我们将辅助函数实现为 BinarySearchTree 类的 static（静态）方法。
为什么使用 @staticmethod？
当一个方法被定义为 static 方法时，这意味着该方法执行与类相关的功能，但不需要任何类实例来完成工作。static 方法定义完美匹配辅助函数的情况，这些函数执行与 BinarySearchTree 类绑定的操作，而不是与 BinarySearchTree 对象绑定的操作。
为什么不直接定义一个普通函数？
使用 static 方法不仅在逻辑上说得通，而且还能提高可读性。当客户端（即人类）阅读代码时，函数定义会告诉客户端该函数与任何类型为 BinarySearchTree 的对象相关联。
下一节将重点介绍这些辅助函数。
获取高度
树的高度（subtree）是从根到叶子的最长距离。另外，只有一棵节点的树，其高度为零。例如，下图显示树的高度为 4，根为 11 和 30 的子树高度分别为 2 和 1。
树的高度是决定二叉搜索树操作性能的关键因素（有关详细信息，请参阅分析部分）。
为了计算树的高度，我们可以递归地为每个子节点的高度加一。如果一个节点有两个子节点，我们使用 max 函数获取子节点中较高的那个高度，并将其加一。
@staticmethod
def get_height(node: Node) -> int:
if node.left and node.right:
return max(
BinarySearchTree.get_height(node=node.left),
BinarySearchTree.get_height(node=node.right),
) + 1
if node.left:
return BinarySearchTree.get_height(node=node.left) + 1
if node.right:
return BinarySearchTree.get_height(node=node.right) + 1
# If reach here, it means the node is a leaf node.
return 0
获取最左侧和最右侧节点
由于二叉搜索树的属性，最左边的节点包含给定（子）树中的最小键。类似地，最右边节点的键是给定（子）树中的最大键。找到最左边和最右边很简单——沿着路径走。
由于我们可以从任何给定的子树（如果不是整个树）检索最左边或最右边的节点，因此参数是给定（子）树的根。
获取最左边的节点
@staticmethod
def get_leftmost(node: Node) -> Node:
current_node = node
while current_node.left:
current_node = current_node.left
return current_node
获取最右边的节点
@staticmethod
def get_rightmost(node: Node) -> Node:
current_node = node
while current_node.right:
current_node = current_node.right
return current_node
前驱和后继
当我们在二叉搜索树中进行遍历时，一个节点的先前节点（predecessor）是出现在给定节点之前的节点，而后继节点（successor）是紧跟在给定节点之后的节点。遍历二叉搜索树有许多方法。在本例中，先前节点和后继节点是按中序遍历顺序排列的。中序遍历会以排序的方式遍历二叉搜索树。因此，节点的先前节点将是在给定节点之前的那个节点（在排序顺序中），而后继节点将是紧跟在给定节点之后的那个节点（在排序顺序中）。由于中序遍历产生排序结果，因此使用给定节点的中序先前节点和后继节点是最有用的。
前驱
查找给定节点的先前节点有两种情况
|
下图显示了这两种情况
情况 1 很直接。对于情况 2，我们以节点 24 和节点 34 为例。
对于节点 24 的先前节点，节点 24 是 x。由于节点 24 (x) 没有左子节点，我们从节点 24 (x) 向上遍历，发现节点 30 (y) 是其父节点 23 (z) 的右子节点。算法告诉我们节点 23 (z) 是节点 24 (x) 的先前节点。
关于节点 34 的先前节点，节点 34 是 x。由于节点 34 (x) 没有左子节点，我们从节点 34 (x) 向上遍历，发现节点 34 (y) 也是其父节点 30 (z) 的右子节点。因此，节点 34 (x) 的先前节点是节点 30 (z)。请注意，一个节点可以是 x 和 y 同时出现，如果该节点是右子节点。
获取先前节点
@staticmethod
def get_predecessor(node: Node) -> Optional[Node]:
if node.left: # Case 1: left child is not empty
return BinarySearchTree.get_rightmost(node=node.left)
# Case 2: left child is empty
parent = node.parent
while parent and (node == parent.left):
node = parent
parent = parent.parent
return parent
后继
获取后继节点的算法与获取先前节点的算法对称，它也有两种情况可以找到给定节点的后继节点
|
下图显示了这两种情况
与先前节点的情况类似，如果节点是左子节点，则节点可以同时是 x 和 y。
对于节点 15 的后继节点，节点 15 是 x 和 y，节点 20 是 z，它是节点 15 的后继节点。
对于节点 22 的后继节点，节点 22 是 x，节点 4 是 y，节点 23 是 z。所以节点 23 是节点 22 (x) 的后继节点。
获取后继节点
@staticmethod
def get_successor(node: Node) -> Optional[Node]:
if node.right: # Case 1: right child is not empty
return BinarySearchTree.get_leftmost(node=node.right)
# Case 2: right child is empty
parent = node.parent
while parent and (node == parent.right):
node = parent
parent = parent.parent
return parent
特殊功能
根据 Python 文档，__repr__() 用于计算对象的官方字符串表示。文档还说，“这通常用于调试，…”。因此，在我们的 BinarySearchTree 类中，我们利用此函数提供树的详细信息，这将有助于我们调试问题。
def __repr__(self) -> str:
if self.root:
return (
f"{type(self)}, root={self.root}, "
f"tree_height={str(self.get_height(self.root))}"
)
return "empty tree"
当我们打印 BinarySearchTree 对象的 repr() 时，我们可以看到树的详细信息，如下所示
<class '__main__.BinarySearchTree'>, root=Node(key=23, data='23',
left=Node(key=4, data='4', left=Node(key=1, data='1', left=None, right=None, parent=...),
right=Node(key=11, data='11', left=Node(key=7, data='7', left=None, right=None, parent=...),
right=Node(key=20, data='20', left=Node(key=15, data='15', left=None, right=None, parent=...),
right=Node(key=22, data='22', left=None, right=None, parent=...), parent=...), parent=...),
parent=...), right=Node(key=30, data='30', left=Node(key=24, data='24', left=None, right=None,
parent=...), right=Node(key=34, data='34', left=None, right=None, parent=...), parent=...),
parent=None), tree_height=4
这些信息可以帮助我们调试问题。
测试
单元测试是确保软件项目质量的最低要求。pytest 框架是 Python 程序流行的测试框架。在我们的项目中，我们使用以下设置来运行它
- tests 文件夹包含所有测试文件
- pytest.ini 定义了指向 tests 文件夹的路径
- conftest.py 定义了可供任何测试使用的通用测试数据
- test_binary_search_tree.py 是我们
BinarySearchTree的测试代码
检查每个链接以获取详细信息。
分析
一个能够工作的软件程序，正确性和性能都是必需的。然而，我认为正确性比性能具有更高的优先级。当我们实现一个软件程序时，我们应该始终确保程序正常工作，然后再调整其性能。没有正确性，程序就毫无用处。这也是本文顺序安排的原因：测试部分在前，分析部分在后。在测试部分（并确保 BinarySearchTree 有效）之后，本节将重点关注其性能。本节的分析适用于通用的二叉搜索树（不仅仅是我们实现的 BinarySearchTree）。
二叉搜索树的空间复杂度为 O(n)，其中 n 是节点的总数。
二叉搜索树的每个操作的运行时间高度依赖于树的高度。如果树的高度为 h，则每个操作的运行时间如下
对于 insert（插入）操作，我们首先需要从根到叶子级别找到要插入节点的位置，这在树高为 h 的情况下需要 T(h) 的运行时间。然后更新节点属性，这需要常数运行时间。因此，插入操作的总运行时间为 T(h) + 常数，这相当于 O(h)，因为大 O 符号是运行时间的上限。
类似地，查找（search）和删除（delete）操作也需要从根遍历树，直到我们找到节点或要删除的节点。因此，它们的运行时间也为 O(h)，其中 h 是树的高度。
为了找到最左边和最右边的节点，我们还需要从给定节点遍历到叶子级别，因为最左边和最右边的节点必须在叶子级别。运行时间也为 O(h)，其中 h 是（子）树的高度。
给定节点的先前节点有两种情况：1. 给定节点有一个左子节点，2. 给定节点的左子节点为空。
由于如果给定节点有一个左子节点，左子树中最右边的节点就是先前节点，因此情况 1 的运行时间等同于获取最左边的节点，即 O(h)，其中 h 是树的高度。
关于情况 2，我们需要找到作为父节点右子节点的那个节点。换句话说，如果先前节点位于最高级别，则可能需要 O(h) 的时间。
因此，先前节点（predecessor）的运行时间是这两种情况的组合：O(h) + O(h) = 2 * O(h) = O(h)。
后继节点（successor）与先前节点对称，其运行时间也为 O(h)，其中 h 是树的高度。
现在，我们知道每个操作的运行时间都取决于树的高度。接下来我们想知道的是，当树有 n 个节点时，树可能有多高。
如果一棵树是完整的，它的高度是 O(lg n)。然而，如果一棵二叉树是线性链式的，它的高度将变为 O(n)。
根据定理，“n 个不同键上随机构建的二叉搜索树的期望高度是 O(lg n)”，在平均情况下，每个操作的时间复杂度变为 O(lg n)。该定理的细节和证明在 《算法导论》 第 12.4 章中进行了讨论。
因此，我们可以在下表中总结每个操作的运行时间。n 是节点的数量。
示例
树形数据结构在软件中被广泛使用，包括实现其他数据结构。例如，BinarySearchTree 提供的操作允许我们将搜索树用作键值映射（key-value map）。本节演示了一个使用本项目实现的 BinarySearchTree 的键值 Map。
键值 Map 类支持的操作，例如插入键值对、按 key 获取项以及按 key 删除项。为了支持这些操作，我们需要实现 __setitem__ 函数用于插入键值对，__getitem__ 函数用于通过 key 检索项，以及 __delitem__ 函数用于按键删除项。因此，我们有如下实现
from typing import Any, Optional
from forest.binary_trees import binary_search_tree
class Map:
"""Key-value Map implemented by the Binary Search Tree."""
def __init__(self) -> None:
self._bst = binary_search_tree.BinarySearchTree()
def __setitem__(self, key: Any, value: Any) -> None:
self._bst.insert(key=key, data=value)
def __getitem__(self, key: Any) -> Optional[Any]:
node = self._bst.search(key=key)
if node:
return node.data
return None
def __delitem__(self, key: Any) -> None:
self._bst.delete(key=key)
@property
def empty(self) -> bool:
"""Return `True` if the map is empty; `False` otherwise."""
return self._bst.empty
if __name__ == "__main__":
# Initialize the Map instance.
contacts = Map()
# Add some items.
contacts["Mark"] = "mark@email.com"
contacts["John"] = "john@email.com"
contacts["Luke"] = "luke@email.com"
# Retrieve an email
print(contacts["Mark"])
# Delete one item.
del contacts["John"]
# Check the deleted item.
print(contacts["John"]) # This will print None
（完整的示例可在 bst_map.py 获取。）
摘要
二叉搜索树在平均情况下提供了良好的空间利用率和相对较好的插入、查找和删除操作性能。然而，在大多数情况下，我们无法保证树是平衡的。正因为如此，二叉搜索树并未被广泛用于解决现实世界的问题。为了解决不平衡问题并提高某些操作的性能，引入了二叉搜索树的几种变体，例如红黑树和 AVL 树。因此，全面理解二叉搜索树是学习高级树形数据结构的基础。
（最初发表于 Shun's Vineyard，发布日期为 2021 年 3 月 13 日）