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

Question

我对树木操作中的时间复杂度有疑问。
据说（Data Structures，Horowitz 等人）在 BST 中插入、删除、搜索、查找 mins-max、后继和前驱节点的时间复杂度O(h)是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)

Answer 2

O(h)意味着复杂度线性依赖于树的高度。如果树是平衡的，则此渐近变为O(logn)（n - 元素数）。但并非所有树都如此。想象一下非常不平衡的二叉树，其中每个节点只有左子节点，这棵树变得类似于列表，并且该树中的元素数量等于树的高度。所描述操作的复杂性将O(n)代替O(logn)