理解二叉搜索树

二叉树（BST）是一棵二叉树，其构建方式使树总是排序的。这意味着左边子节点的值小于或等于父节点的值，而右边子节点的值大于父节点的值。因此，每当我们需要搜索一个值时，要么向左搜索，要么向右搜索。由于是排序，我们只能搜索树的一部分，而不能同时搜索两部分，而且这种搜索会递归进行。由于它的分割性质，搜索速度变得非常快，我们可以实现对数复杂度的搜索。例如，如果我们有 n 个节点，我们将搜索节点的前半部分或后半部分。一旦我们进入上半部分或下半部分，我们就可以再次将其分为两半，这意味着我们的一半现在变成了四分之一，如此循环往复，直到我们到达最终节点。由于我们不是移动到每个节点进行搜索，因此操作的复杂度不会达到 \$O(n)\$。在下一章中，我们将对二进制搜索进行复杂度分析，并了解为什么二进制搜索树的搜索复杂度为 \$O(log n)\$。与二叉树不同的是，在不重建 BST 属性的情况下，我们不能在树上添加或删除任何节点。

如果节点 X 有两个子节点，那么节点 X 的后继节点就是属于树中大于 X 的值的最小值。另一方面，前置节点是左子树的最大值。现在，我们将更多地关注 BST 的不同操作以及正确执行这些操作所需的步骤。

以下是 BST 的操作。

插入新节点

当我们在二叉搜索树中插入新节点时，我们必须考虑以下步骤：

创建一个新节点作为叶子节点（无左子节点或右子节点）。
从根节点开始，将其设置为当前节点。
如果节点为空，则将新节点设为根节点。
检查新值是否小于或大于当前节点。
如果小于，则向左移动，并将左节点设为当前节点。
如果大于，则转到右边，并将右边设为当前节点。
继续执行步骤 3，直到访问完所有节点并设置好新节点。

搜索节点

当我们在二叉搜索树中搜索新节点时，我们必须考虑以下步骤：

从根节点开始，并将其设置为当前节点。
如果当前节点为空，则返回 false。
如果当前节点值是搜索值，则返回 true。
检查搜索值是否小于或大于当前节点。
如果小于，则转到左边，并将左边设为当前节点。
如果大于，则转到右边并将右边设为当前节点。
继续执行步骤 3，直到访问完所有节点。

寻找最小值

由于二叉搜索树以排序的方式存储数据，我们总能在左节点中找到较小的数据，而在右节点中找到较大的数据。因此，要找到最小值，我们需要访问从根节点开始的所有左节点，直到找到最左节点及其值。以下是查找最小值的步骤：

从根节点开始，并将其设置为当前节点。
如果当前节点为空，则返回 false。
转到左节点，并将左节点设置为当前节点。
如果当前节点没有左节点，则进入第 5 步；否则继续第 4 步。
继续执行步骤 3，直到访问完所有左节点。
返回当前节点。

寻找最大值

以下是寻找最大值的步骤：

从根节点开始，并将其设置为当前节点。
如果当前节点为空，则返回 false。
向右移动，并将右节点设置为当前节点。
如果当前节点没有右节点，则进入第 5 步；否则继续第 4 步。
继续执行步骤 3，直到访问完所有右节点。
返回当前节点。

删除节点

在删除节点时，我们必须考虑到该节点可能是内部节点，也可能是叶子节点。如果是叶子节点，它就没有子节点。但如果是内部节点，则可能有一个或两个子节点。在这种情况下，我们需要采取额外的步骤来确保删除后的树是正确的。这就是为什么与其他操作相比，从 BST 中删除节点总是一项具有挑战性的工作。以下是删除节点时需要考虑的事项：

如果该节点没有子节点，则将该节点设置为 NULL。
如果节点只有一个子节点，则让该子节点取代节点的位置。
如果节点有两个子节点，则找到该节点的后继节点，并将其替换到当前节点的位置。删除后继节点。

我们已经讨论了二叉搜索树的大部分可能操作。现在，我们将逐步实现二叉搜索树，首先是插入、搜索、查找最小值和最大值，最后是删除操作。让我们开始实现吧。