用于高效查找的二叉搜索树

虽然普通树提供了分层组织，但**二叉搜索树（BST）**规定了特定的排序性质，使元素查找非常高效。这个性质是 BST 对查找密集型任务有作用的原因。

二叉搜索树是一种二叉树（每个节点最多有两个子节点），其中每个节点都满足：

1. 节点左子树中的所有值都小于节点的值。
2. 节点右子树中的所有值都大于节点的值。
3. 左子树和右子树本身也必须是二叉搜索树。

这个递归定义形成了一个有序结构。我们来看一个包含整数值的简单 BST 示例：

一棵二叉搜索树，其中每个左子节点都小于其父节点，每个右子节点都大于其父节点。

在 BST 中查找

BST 性质的主要优点是查找速度快。要查找一个值（称之为 target）：

1. 从根节点开始。
2. 将 target 与当前节点的值比较。
3. 如果 target 与节点的值匹配，表示已找到。
4. 如果 target 小于节点的值，则移到左子节点并从步骤 2 重复。如果没有左子节点，则 target 不在树中。
5. 如果 target 大于节点的值，则移到右子节点并从步骤 2 重复。如果没有右子节点，则 target 不在树中。

由于每次比较有效地排除了大约一半的剩余节点（在相对平衡的树中），查找操作的时间通常与树的高度成正比。对于一个包含 $n$ 个节点的平衡 BST，其高度大约是 $\log_2 n$。因此，查找的平均时间复杂度是 $O(\log n)$。这种对数性能比未排序列表或数组所需的 $O(n)$ 线性查找要快得多，尤其是在大数据集中。

向 BST 中插入

向 BST 中添加新值必须保持其搜索性质。插入过程与查找类似：

1. 从根节点开始。
2. 将新值与当前节点的值比较。
3. 如果新值小于节点的值，则移到左子节点。如果没有左子节点，则将新值作为左子节点插入。否则，将左子节点作为当前节点，从步骤 2 重复。
4. 如果新值大于或等于节点的值（或者仅大于，取决于是否允许重复值以及如何处理），则移到右子节点。如果没有右子节点，则将新值作为右子节点插入。否则，将右子节点作为当前节点，从步骤 2 重复。

与查找一样，插入操作也沿着从根到叶节点位置的路径。因此，在平衡树中，其平均时间复杂度也是 $O(\log n)$。

将值 45 插入 BST。搜索路径（50 -> 30 -> 40）决定了其在 40 的右子节点位置。

从 BST 中删除

删除操作稍微复杂一些，因为移除节点可能破坏 BST 性质或使树断开连接。有以下三种情况：

1. 要删除的节点是叶节点（无子节点）： 直接移除该节点。
2. 要删除的节点有一个子节点： 用其子节点替换该节点。子树相对于被删除节点的父节点，保持 BST 性质。
3. 要删除的节点有两个子节点： 这是最麻烦的情况。不能直接移除该节点。而是用以下两者之一替换节点的值：
   • 其中序后继的值（其右子树中最小的值）。
   • 其中序前驱的值（其左子树中最大的值）。 然后，递归删除您取出替换值的那个节点（这个节点最多有一个子节点，属于情况 1 或 2）。

查找要删除的节点平均需要 $O(\log n)$ 时间。后续步骤（查找后继/前驱并执行较简单的删除）通常也需要对数时间。因此，删除的平均时间复杂度保持为 $O(\log n)$。

性能考量：平衡的需求

查找、插入和删除操作的理想 $O(\log n)$ 平均时间复杂度取决于树是否相对平衡。如果数据以排序或近似排序的顺序插入，BST 可能退化为类似链表的结构。

平衡 BST（左侧）与通过按排序顺序插入元素形成的倾斜 BST（右侧）的比较。在倾斜树中查找的性能会下降到 $O(n)$。

在这种倾斜情况下，树的高度变为 $n$，所有操作的性能下降到 $O(n)$，与链表相同。这说明了为什么自平衡 BST（例如 AVL 树或红黑树），我们接下来将简要讨论它们，在实践中通常更受欢迎，以确保即使在最坏情况下也能保持对数性能。

与机器学习的相关性

虽然您可能不会直接将简单的 BST 用作许多复杂机器学习模型的核心组成部分，但了解它们很重要：

• 索引： BST（及其平衡变体）是数据库索引的重要组成部分，数据库索引常用于加快机器学习训练集或特征查找的数据检索。
• 决策树的原理： 基于比较递归划分数据的原理是决策树运行方式的主要方面。决策树中的每个节点都进行一次划分，这与 BST 指导搜索向左或向右类似，尽管决策树是基于特征阈值而非单纯的值比较进行划分的。
• 高效查找： 在机器学习流程中需要频繁查找、插入和删除元素的场景（例如，管理活跃特征、维护某些类型的缓存）下，当还需要有序遍历或范围查询时，类似 BST 的结构可以提供比简单列表或哈希表更好的性能。

二叉搜索树提供了一种巧妙的方式来动态维护排序数据，为查找提供了高效的平均情况性能。它们的主要局限性在于倾斜数据可能导致性能下降，这促使了对接下来将讨论的平衡树结构的需求。