树中的 Big O(h) vs. Big O(logn)

Question

我有一个关于树操作的时间复杂度问题。 据说（《数据结构与算法》Horowitz等人）在二叉搜索树中，插入、删除、查找、查找最小值-最大值、后继和前驱节点的时间复杂度为O(h)，而AVL树的时间复杂度为O(logn)。 我不太理解其中的区别。考虑到h=[logn]+1，那么为什么我们要用O(h)或者其他地方用O(logn)？

- Shahin

---

可能是重复的问题：在树结构的大O符号表示法中，为什么有些来源引用O(logN)，而有些引用O(h)？ - templatetypedef

Answer 1

h代表树的高度。它始终为Ω(logn) [不会比logn渐进地小]。在完全二叉树中，它可能非常接近于logn（这时你真正得到h=logn + 1），但在退化成链式结构的树中（每个节点只有一个儿子），h=O(n)。

对于平衡树，h=O(logn)（实际上是Θ(logn)），因此在这些树上任何O(h)算法其实都是O(logn)的。

自平衡搜索树的想法（AVL是其中之一）是防止树退化成链式结构（或者接近于它），而它们（平衡树）的特性能确保我们获得O(logn)的高度。

编辑：
为了更好地理解这个问题，请考虑下面的两棵树（请原谅我拙劣的ASCII艺术）：

          tree 1                                tree 2
            7
           /
          6
         /
        5                                         4
       /                                      /       \
      4                                      2         6
     /                                    /    \     /   \
    3                                    1      3   5     7
   /
  2
 /
1

这两个二叉搜索树都是有效的，对于查找元素（比如 1）来说，复杂度为 O(h)。但在第一个二叉搜索树中，O(h) 实际上是 O(n)，而在第二个二叉搜索树中则为 O(logn)

- amit

Answer 2

O(h) 表示复杂度与树的高度成线性相关。如果树是平衡的，这个渐近变成了 O(logn)（n - 元素数量）。但并非所有树都是如此。想象一个非常不平衡的二叉树，每个节点只有左子节点，这个树会变得类似于列表，并且该树中元素的数量等于树的高度。所述操作的复杂度将为 O(n) 而不是 O(logn)

- mishadoff