树木中的大O(h)与大O(logn)

Question

我对树木作业中的时间复杂有疑问.
据说(数据结构,Horowitz等)插入,删除,搜索,在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)