Question

6.14.查找树分析

随着二叉搜索树的实现完成，我们将对已经实现的方法进行快速分析。让我们先来看看 put 方法。其性能的限制因素是二叉树的高度。从词汇部分回忆一下树的高度是根和最深叶节点之间的边的数量。高度是限制因素，因为当我们寻找合适的位置将一个节点插入到树中时，我们需要在树的每个级别最多进行一次比较。

二叉树的高度可能是多少？这个问题的答案取决于如何将键添加到树。如果按照随机顺序添加键，树的高度将在 $log2^n$log2​n​​ 附近，其中 n 是树中的节点数。这是因为如果键是随机分布的，其中大约一半将小于根，一半大于根。请记住，在二叉树中，根节点有一个节点，下一级节点有两个节点，下一个节点有四个节点。任何特定级别的节点数为 $2^d$2​d​​ ，其中 d 是级别的深度。完全平衡的二叉树中的节点总数为 $2^{h+1} - 1$2​h+1​​−1，其中 h 表示树的高度。

完全平衡的树在左子树中具有与右子树相同数量的节点。在平衡二叉树中，put 的最坏情况性能是 $O(log2^n)$O(log2​n​​)，其中 n 是树中的节点数。注意，这是与前一段中的计算的反比关系。所以 log2^⁡n 给出了树的高度，并且表示了在适当的位置插入新节点时，需要做的最大比较次数。

不幸的是，可以通过以排序顺序插入键来构造具有高度 n 的搜索树！这样的树的示例见 Figure 6。在这种情况下，put方法的性能是 $O(n)$O(n)。

Figure 6

现在你明白了 put 方法的性能受到树的高度的限制，你可能猜测其他方法 get，in 和 del 也是有限制的。 由于 get 搜索树以找到键，在最坏的情况下，树被一直搜索到底部，并且没有找到键。 乍一看，del 似乎更复杂，因为它可能需要在删除操作完成之前搜索后继。 但请记住，找到后继者的最坏情况也只是树的高度，这意味着你只需要加倍工作。 因为加倍是一个常数因子，它不会改变最坏的情况