跳转至

6.14.查找树分析

6.14.查找树分析

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

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

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

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

6.14.查找树分析.figure6

Figure 6

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