algorithm - 树中的大 O(h) 与大 O(logn)

Question

我有一个关于树操作的时间复杂度的问题。
据说(Data Structures, Horowitz et al)在 BST 中插入、删除、搜索、查找 mins-maxs、后继和前导节点的时间复杂度是 O(h) 而那些的 AVL 使得 O(logn)。
我不太明白有什么区别。考虑到 h=[logn]+1，那么为什么我们说 O(h) 而在其他地方说 O(logn)？

Answer 1

h 是树的高度。它总是 Omega(logn) [不渐近小于 logn]。在完整的树中它可以非常接近logn(然后你真的得到了h=logn+1，但是在一棵衰落成链的树中(每个节点只有一个子)是 O(n)。

对于平衡树，h=O(logn)(实际上是Theta(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)