二叉搜索树（BST）

引言

在深入学习二叉搜索树之前，恭喜你！当你到达课程的这个阶段时，你已经掌握了指针和内存管理的所有知识。接下来，我们将进一步练习这些概念，以加深对它们的理解。

本章具有双重目的。

首先，我们将学习二叉搜索树（BST）。BST 是一种数据结构，能够高效地执行某些操作。我们关注 BST 的原因，正如链表一样，是因为它非常适合练习涉及大量指针的代码编写。

另一方面，本章内容将为课程的小型项目做好准备。通过本章的学习，你将掌握实现通用二叉搜索树所需的所有知识，并能在项目中使用它来高效地完成查找和排序操作——这些都是现实生活中的常见问题。在本章中，我们将使用伪代码，并重点理解 BST 应该如何工作。你需要在专门的练习环境中将这些伪代码实现出来。

使用场景

当使用数组或列表实现某些排序和查找操作时，效率往往不够高。例如：

• 在线排序。假设我们持续接收数据并希望保持其有序状态。我们可以使用数组并在每次插入后进行排序，但这会非常缓慢。而二叉搜索树则可以在不每次插入后都排序的情况下，始终保持数据有序。
• 在一组数据中计算最小值和最大值。
• 查找某个范围内的数值个数或具体数值。
  • 例如，统计一年中气温低于零度的天数，或高于30摄氏度的天数。
  • 查找某一时间段内收到的所有电子邮件。
• 找到与某个值最接近的值。例如，找到年龄最接近你的同事。

这些主题的共同点在于：它们都需要根据某种规则对大量数据进行排序。由于我们不断接收新数据，因此只排序一次是不可行的。我们需要保持数据始终有序，并能高效地执行各种查询操作。这里的“高效”意味着我们不希望每次都检查所有元素。我们希望利用元素天然的有序性，尽可能快速地完成操作。

定义

二叉搜索树是一种链式数据结构。

• 我们称它为“树”，因为它看起来像一棵倒置的树，有一个根节点，并向下不断扩展。
• 称它为“二叉树”，因为每个节点最多有两个子节点（可以是两个、一个，也可以没有）。
• 称它为“二叉搜索树”，因为左子树中的所有值都小于根节点的值，右子树中的所有值都大于根节点的值。

让我们看下面的示意图。

• 树的根节点是值为 2 的节点。
• 节点 2 有两个子节点——左子节点 1 和右子节点 3。
• 左子节点的值小于根节点（1 < 2），右子节点的值大于根节点（3 > 2）。
• 节点 1 和 3 是叶子节点，它们没有子节点。我们可以认为它们的子节点为 NULL。

再来看一个稍大的二叉搜索树。

• 它是一棵二叉树，因为每个节点最多有两个子节点。
• 树的根节点是 7，它有两个子节点：2 和 15。节点 2 和 15 各自有自己的子节点，因此它们分别是各自子树的根。
• 举个子树的例子，节点 9 是由节点 8 和 9 构成的子树的根。
• 整棵树都满足二叉搜索树的性质。
  • 根节点 7 的左子树中的所有值（1, 2, 4）都小于 7；右子树中的所有值（15, 11, 16, 9, 8）都大于 7。
  • 根节点 15 的左子树中的所有值（11, 9, 8）都小于 15；右子树中的所有值（16）都大于 15。
  • 任取树中任意一个节点，检查其子节点（以及子节点的子节点）是否都满足二叉搜索树的性质。

注意：右子树中的所有值都大于该子树的根节点值，左子树中的所有值都小于该子树的根节点值。因此，右子树中的值也一定大于左子树中的值。

我们可以将二叉搜索树看作一个包含 value 字段以及两个指针 left 和 right 的结构。

效率

为了快速展示这种结构在查找上的优势，我们来看一个例子：从集合 {7, 2, 15, 1, 4, 11, 16, 9, 8} 中查找值 11。

如果我们将集合存储为数组，就必须遍历整个数组并逐一检查每个元素。最坏情况下，当目标元素位于最后时，需要检查全部元素，时间复杂度为 $O(n)$。在这种情况下，需要进行六次迭代。

现在我们来看看将数据存储为二叉搜索树时的情况。

我们先检查根节点 7，发现不是 11，需要继续查找。但下一步应该去左子树还是右子树？

回忆一下二叉搜索树的性质：

• 左子树中的所有节点值都小于根节点。
• 右子树中的所有节点值都大于根节点。

那么 11 应该在哪里？因为 11 > 7，所以它一定在 7 的右子树中。因此，没有必要搜索左子树。这样，我们一下子就将问题规模减半，只需向右查找。

7 的右子节点是 15，不是 11，而 11 < 15，所以 11 一定在 15 的左子树中。于是我们转向左子树，到达节点 11，找到了目标值。总共只进行了三次迭代（7 → 15 → 11）。

结论：使用二叉搜索树查找 11 的速度是使用数组的两倍。

请参见下方幻灯片，演示了这一过程：

我们可以估算在二叉搜索树中查找元素的时间复杂度。每一步，我们都会舍弃左子树或右子树。如果我们假设树是平衡的（左右两侧的节点数量大致相等），那么每一步都能使待查范围减半。当搜索空间不断被对半分割时，时间复杂度为 $O(\log n)$。

如果你熟悉数组中的二分查找算法，就会发现它与此类似：每一步都舍弃一半的元素。

注意：在二叉搜索树中插入和查找元素的速度很快（$O(\log n)$）。然而，二叉搜索树可能退化为链表（所有节点都是另一个节点的左孩子或右孩子），此时时间复杂度变为 $O(n)$。存在更复杂的树结构（如红黑树、AVL树）可以通过自动平衡来解决这个问题。但我们不会深入探讨这些结构，因为我们关注二叉搜索树的主要目的是练习内存管理和指针操作。

形式化定义

仔细观察二叉搜索树的结构，可以发现它是一个递归的数据结构。因此，我们可以给出一个递归定义：二叉搜索树要么为空，要么包含一个节点，其 left 和 right 指针指向另外两棵二叉搜索树。

观察下图，left 和 right 指针指向的分别是仅包含一个节点的树。但正如我们在前面的例子中看到的，它们也可以指向包含多个节点的树。也就是说，节点 1 可以有子节点，子节点也可以有子节点，依此类推。

当我们处理一棵树时，总是从根节点开始。但随着向下移动，每个节点都会成为其子树的新根。

• 当我们开始处理下面这棵树时，根节点是 2。我们先向左移动，再向右移动。
• 一旦进入左子树，从我们的视角看，1 就成了新的根节点。
• 一旦进入右子树，从我们的视角看，3 就成了新的根节点。

正是由于这种递归结构，使用递归函数来处理树变得非常方便。

通用二叉搜索树

我们通常首先想到的数据类型是整数或浮点数等数值类型。然而，二叉搜索树可以存储任何可按某种规则排序的数据类型。

例如，字符串可以按字典序排列。 数组可以根据元素个数或其他有意义的指标进行排序。

在本章中，我们将以存储整数的二叉搜索树为例进行操作讲解。但在项目中，你需要实现一个通用的二叉搜索树，即能够存储任意数据类型的树（类似于泛型链表）。

二叉树与二叉搜索树

我们也可以讨论一般的二叉树。区别在于，二叉树不遵循二叉搜索树的有序性规则。在普通的二叉树中，节点可以任意排列，子节点与父节点之间没有固定的顺序关系。

我们只关注二叉搜索树。

测验

本练习旨在澄清：有序性必须在每一层都成立，而不仅仅是父节点与其直接子节点之间。

例如，在第二个树中，值为 4 的节点位于 7 的左侧，这是正确的。但它同时位于 6 的右子树中，这破坏了有序性规则。