Python 中的二叉搜索树

二叉树是一种类似于树的数据结构。这种树的每个节点包含两个子节点，称为左子节点和右子节点。二叉搜索树是更常见的二叉树数据结构的一个特例。二叉搜索树应遵循以下属性。

• 树中任何父节点的左子树应该有一个子节点，其值小于父节点。
• 树中任何父节点的右子树应该有一个子节点，其值大于父节点。
• 每个节点的左子树和右子树也应遵循二叉搜索树的上述两个属性。
• 二叉搜索树不包含任何重复值。

这些树的属性有助于在节点中维护排序，以便像搜索、插入以及查找最大值和最小值等操作可以比在普通二叉树中执行这些操作花费的时间更少。因为那样我们就需要比较每个节点的值才能获得值。

在给定的二叉树中搜索值？

让我们以数组为例。如果我们有一个普通数组，并且需要搜索一个元素，我们将需要遍历数组中的元素并比较每个值。而如果我们有一个已排序的数组，我们可以执行二分搜索，它比普通搜索操作更快。类似地，在二叉搜索树和二叉树的情况下。

现在，假设我们需要在二叉搜索树中搜索一个元素。设该元素为 x。

• 我们将从给定树的根节点开始遍历。首先，我们将比较根节点的值和我们要搜索的值，
• 如果两个值相等，那么我们的搜索就完成了，我们将返回该值。如果我们需要搜索的值小于节点的值，那么这意味着我们需要在节点的左子树中搜索。如果该值较大，那么我们将转到右子树。

这是二叉搜索树的主要规则。如果值较小，则在左子树中搜索。如果值较大，则在右子树中搜索。该规则类比于数组中的二分搜索。

如果给定的二叉树是平衡的（平衡二叉树是指所有节点的左右子树之间的距离不超过一），我们将从搜索包含 n 个节点的空间开始。由于第一次迭代后我们将丢弃右子树或左子树，我们将丢弃 n/2 个节点。同样，在下一次迭代中，我们将只剩下 n/4 个节点。这样，每次迭代后，搜索空间将减少 2i，其中 i 是迭代次数。

BST 中搜索的说明

现在我们将看到一个二叉搜索树工作原理的例子。

考虑下面的树，x 的值为 4。

Tree

步骤：

1. 最初，我们将 x 与给定树的根节点值（即 9）进行比较。由于 4 小于 9，我们将在左子树中搜索该值，因此完全丢弃右子树。
2. 现在我们将 x 与当前节点值（即 1）进行比较。由于 x 的值大于节点的值，我们将搜索右子树。
3. 接下来我们将 x 与下一个节点值（即 3）进行比较。由于 4 大于 3，这意味着我们将在右子树中搜索。
4. 下一个节点的值是 4，它等于 x 的值。因此搜索完成，我们在给定的二叉搜索树中找到了 x 的值。

下面是实现二叉搜索树搜索操作的代码。

代码

输出

The node we are searching for is present in the given BST: 4

时间复杂度： O(h) 是该算法的时间复杂度。这里 h 表示给定二叉搜索树的高度。我们在这里取高度是因为我们正在执行 DFS；因此，在最坏的情况下，我们将遍历到树的叶节点，从而需要 h。

空间复杂度： 空间复杂度为 O(h)。这里 h 表示给定二叉搜索树的高度。空间复杂度为 O(h)，因为我们需要存储递归栈的最大空间等于我们遍历的节点数，这等于树的高度。

在 BST 中插入给定值？

二叉搜索树中的插入操作类似于搜索操作。插入节点并保持二叉搜索树的属性可以有很多方法。然而，最简单的方法是将节点插入到合适的叶节点。

• 我们将通过将要插入的值与给定 BST 的根节点的值进行比较来开始。
• 如果我们要插入的值小于根节点的值，我们将在左子树中查找叶节点。
• 否则，如果该值大于根节点的值，我们将在右子树中搜索。
• 我们将继续这个过程，直到我们到达叶节点。
• 现在我们将要插入的值与叶节点的值进行比较。如果该值小于叶节点，我们将创建叶节点的左子节点。
• 否则，如果该值大于叶节点的值，我们将创建叶节点的右子节点。

BST 中插入操作的说明

让我们看一个 BST 中插入操作的例子。

考虑下面绘制的 BST。在该树中，我们必须添加值 x = 5。

Tree

步骤：

1. 我们将通过将根节点的值与 x 进行比较来开始。由于 x 小于 9，我们将在左子树中搜索叶节点。
2. 现在下一个节点的值是 1。由于 x 的值大于 1，因此，现在我们将搜索右子树。
3. 下一个节点的值是 3。由于 x 再次大于 3，因此，我们将搜索右子树中的叶节点。
4. 下一个节点的值是 4，它是一个叶节点。因此，我们将 5 作为节点 4 的子节点插入。由于 x 大于 4，我们将 5 作为该节点的右子节点插入。

最终的 BST 将如下所示。

Tree

下面是实现上述插入操作算法的 Python 代码。

代码

输出

The tree before insertion:
0 1 3 4 9 10

The tree after insertion:
0 1 3 4 5 9 10

我们也可以使用迭代方法来解决这个问题。下面是展示如何使用迭代函数在 BST 中插入节点的代码。

代码

输出

The tree before insertion:
0 1 3 4 9 10

The tree after insertion:
0 1 3 4 5 9 10

时间复杂度： O(h) 是迭代方法的时间复杂度。这里 h 表示给定 BST 的高度。时间复杂度为 O(h)，因为我们遵循深度优先搜索而不是广度优先搜索（或中序遍历）。

辅助空间： 我们只创建了一个新节点来将其插入树中。由于我们没有使用任何变量，迭代方法的空间复杂度为 O(1)。