Python 二叉搜索树
二叉搜索树是一种二叉树，其中每个节点的左子节点值都较小，每个节点的右子节点值都较大。
二叉搜索树的一个明显优势是，搜索、删除和插入等操作非常快速，且无需在内存中移动值。
二叉搜索树
二叉搜索树（BST）是一种二叉树数据结构，对于树中的任意节点“X”，必须满足以下属性：
- X 节点的左子节点及其所有后代（子节点、子节点的子节点等）的值都小于 X 的值。
- 右子节点及其所有后代的值都大于 X 的值。
- 左右子树也必须是二叉搜索树。
这些属性使得搜索、添加和删除值的速度比普通二叉树更快。
为了使二叉搜索树尽可能易于理解和实现，我们还假设二叉搜索树中的所有值都是唯一的。
树的大小是指树中的节点数量 (n)。
子树以树中的一个节点作为局部根节点开始，由该节点及其所有后代组成。
节点的后代是指该节点的所有子节点，以及所有子节点的子节点，以此类推。从一个节点开始，其所有连接的下方节点都是其后代。
节点的高度是指该节点与叶节点之间的最大边数。
节点的中序后继是指在中序遍历时位于该节点之后的节点。对上述BST进行中序遍历，节点13将位于节点 14 之前，因此节点13的后继是节点 14。
二叉搜索树的遍历
为了确认我们面前确实是一个二叉搜索树数据结构，我们可以检查页面顶部的属性是否成立。因此，对于上图中的每个节点，检查该节点左侧的所有值是否都较小，右侧的所有值是否都较大。
另一种检查二叉树是否为BST的方法是进行中序遍历（如上一页所述），并检查结果值列表是否按升序排列。
以下代码实现了上图中的二叉搜索树及其遍历。
实例
Python 二叉搜索树的遍历：
class TreeNode:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def inOrderTraversal(node):
if node is None:
return
inOrderTraversal(node.left)
print(node.data, end=", ")
inOrderTraversal(node.right)
root = TreeNode(13)
node7 = TreeNode(7)
node15 = TreeNode(15)
node3 = TreeNode(3)
node8 = TreeNode(8)
node14 = TreeNode(14)
node19 = TreeNode(19)
node18 = TreeNode(18)
root.left = node7
root.right = node15
node7.left = node3
node7.right = node8
node15.left = node14
node15.right = node19
node19.left = node18
# 遍历
inOrderTraversal(root)
通过运行上面的代码示例，我们可以看到中序遍历产生的数字列表是按升序排列的，这意味着这棵二叉树是二叉搜索树。
在 BST 中搜索值
在 BST 中搜索值与使用二分查找在数组中查找值非常相似。
为了使二分查找有效，数组必须已经排序，然后可以在数组中非常快速地查找值。
同样，由于节点的排列方式，在 BST 中查找值也可以非常快速。
工作原理：
- 从根节点开始。
- 如果这是我们要查找的值，则返回。
- 如果我们要查找的值较大，则继续在右子树中搜索。
- 如果我们要查找的值较小，则继续在左子树中搜索。
- 如果要搜索的子树不存在，则根据编程语言返回 None、NULL 或类似值，以表示该值不在 BST 中。
该算法可以这样实现：
实例
在树中搜索值 "13"：
def search(node, target):
if node is None:
return None
elif node.data == target:
return node
elif target < node.data:
return search(node.left, target)
else:
return search(node.right, target)
# 搜索值
result = search(root, 13)
if result:
print(f"Found the node with value: {result.data}")
else:
print("Value not found in the BST.")
在 BST 中搜索值的时间复杂度为 O(h)，其中 h 是树的高度。
例如，对于右侧节点较多的 BST，树的高度会变得比必要的高度更大，最坏情况下的搜索时间会更长。这样的树被称为不平衡树。
上述两棵二叉搜索树具有相同的节点，并且对两棵树进行中序遍历得到的结果相同，但高度却大不相同。搜索上述不平衡树的时间更长，因为它的高度更高。
我们将在下一页介绍一种称为 AVL 树的二叉树。AVL 树是自平衡的，这意味着树的高度保持在最低限度，以便搜索、插入和删除等操作花费的时间更少。
在 BST 中插入节点
在 BST 中插入节点与搜索值类似。
工作原理：
- 从根节点开始。
- 比较每个节点：
- 值较小？向左走。
- 值较大？向右走。
- 继续将节点与新值进行比较，直到没有左右节点可比较为止。那就是插入新节点的位置。
按照上述方式插入节点意味着插入的节点将始终成为新的叶节点。
BST 中的所有节点都是唯一的，因此，如果我们找到与要插入的值相同的节点，则不执行任何操作。
BST 中的节点插入可以这样实现：
实例
在 BST 中插入节点：
def insert(node, data):
if node is None:
return TreeNode(data)
else:
if data < node.data:
node.left = insert(node.left, data)
elif data > node.data:
node.right = insert(node.right, data)
return node
# 将新值插入 BST
insert(root, 10)
在 BST 子树中查找最小值
下一节将解释如何在 BST 中删除节点，但为此我们需要一个函数来查找节点子树中的最小值。
工作原理：
- 从子树的根节点开始。
- 尽可能向左走。
- 你最终到达的节点就是该 BST 子树中具有最小值的节点。
以下是在 BST 节点的子树中查找最小值的函数：
实例
在 BST 子树中查找最小值：
def minValueNode(node):
current = node
while current.left is not None:
current = current.left
return current
# 查找最小值
print("\nLowest value:",minValueNode(root).data)
我们将在下面的部分中使用此 minValueNode() 函数来查找节点的中序后继，并使用它来删除节点。
在 BST 中删除节点
要删除节点，我们的函数必须首先在 BST 中搜索该节点。
找到节点后，有三种不同的情况需要以不同的方式删除节点。
工作原理：
- 如果节点是叶节点，则通过移除指向它的链接来删除它。
- 如果节点只有一个子节点，则将要删除节点的父节点连接到该子节点。
- 如果节点既有右子节点又有左子节点：找到节点的中序后继，与该节点交换值，然后删除它。
在上述步骤 3 中，我们找到的后继始终是叶节点，并且由于它是紧跟在要删除节点之后的节点，因此我们可以与它交换值并删除它。
以下是具有删除节点功能的 BST 的实现方式：
实例
在 BST 中删除节点：
def delete(node, data):
if not node:
return None
if data < node.data:
node.left = delete(node.left, data)
elif data > node.data:
node.right = delete(node.right, data)
else:
# 只有一个子节点或没有子节点的节点
if not node.left:
temp = node.right
node = None
return temp
elif not node.right:
temp = node.left
node = None
return temp
# 有两个子节点的节点，获取中序后继
node.data = minValueNode(node.right).data
node.right = delete(node.right, node.data)
return node
# 删除节点 15
delete(root,15)
第 1 行：这里的 node 参数使函数能够在搜索要删除的 data 时对越来越小的子树递归调用自身。
第 2-8 行：这是在搜索具有要删除的正确 data 的节点。
第 9-22 行：已找到要删除的节点。有三种这样的情况：
情况 1：没有子节点的节点（叶节点）。返回 None，并通过递归使其成为父节点的新左值或右值（第 6 行或第 8 行）。
情况 2：有左子节点或右子节点的节点。通过递归使该左子节点或右子节点成为父节点的新左子节点或右子节点（第 7 行或第 9 行）。
情况 3：节点既有左子节点又有右子节点。使用 minValueNode() 函数找到中序后继。我们通过将中序后继的值设置为要删除节点的值来保留该值，然后我们可以删除后继节点。
第 24 行：返回 node 以保持递归功能。
BST 与其他数据结构的比较
二叉搜索树结合了另外两种数据结构的优点：数组和链表。
| 数据结构 | 搜索值 | 删除/插入导致内存中的移动 |
|---|---|---|
| 有序数组 | O(\log n) | 是 |
| 链表 | O(n) | 否 |
| 二叉搜索树 | O(\log n) | 否 |
搜索 BST 的速度与在数组上进行二分查找一样快，时间复杂度相同，为 O(log n)。
并且可以像链表一样，在删除和插入新值时无需在内存中移动元素。
BST 的平衡性与时间复杂度
在二叉搜索树上，插入新节点、删除节点或搜索节点等操作的时间复杂度实际上是 O(h)。这意味着树的高度（h）越高，操作所需的时间就越长。
我们在上面的表格中写搜索值为 O(log n) 的原因是，如果树是“平衡的”，如上图所示，那么这是成立的。
我们称这棵树是平衡的，因为树的左侧和右侧的节点数量大致相同。
判断二叉树是否平衡的确切方法是，任何节点的左右子树的高度差不超过 1。在上图中，根节点的左子树高度为 h=2，右子树高度为 h=3。
对于具有大量节点（大 n）的平衡 BST，我们得到高度 h ≈ \log_2 n，因此搜索、删除或插入节点的时间复杂度可以表示为 O(h) = O(\log n)。
但是，如果 BST 完全不平衡，如上图所示，树的高度大约与节点数量相同，h ≈ n，我们得到搜索、删除或插入节点的时间复杂度为 O(h) = O(n)。
因此，为了优化 BST 上的操作，必须最小化高度，为此必须平衡树。
保持二叉搜索树平衡正是 AVL 树所做的，这是下一页将解释的数据结构。