6.14.查找树分析
Last updated
Last updated
随着二叉搜索树的实现完成,我们将对我们已经实现的方法进行快速分析。让我们先来看看 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)。
Figure 6
现在你明白了 put
方法的性能受到树的高度的限制,你可能猜测其他方法 get
,in
和 del
也是有限制的。 由于 get
搜索树以找到键,在最坏的情况下,树被一直搜索到底部,并且没有找到键。 乍一看,del
似乎更复杂,因为它可能需要在删除操作完成之前搜索后继。 但请记住,找到后继者的最坏情况也只是树的高度,这意味着你只需要加倍工作。 因为加倍是一个常数因子,它不会改变最坏的情况