BST上下一个/上一个函数的时间复杂度

Question

我对在二进制搜索树中前进和后退的最坏情况效率感兴趣。

不平衡树：

   5
  /
 1 
  \
   2
    \
     3
      \
       4

看起来最坏的情况是4-

平衡树：

   2
  / \
 1   4
    / \ 
   3   5

最坏情况是2-

我认为BST的最坏情况是O（高度-1），对于平衡树是O（log n），对于不平衡树是O（n-1），这是对的吗？

Answer 1

如果您正在考虑按顺序遍历树，那么复杂性不会因平衡而改变。算法仍然是

 walk( Node n)
    walk( n.left )
    visit( n )
    walk( n.right )

每个步骤1个操作。

当你开始应用查找、插入和删除时，平衡就开始发挥作用了。

为了使这些操作处于O（log N）中，需要一个平衡树。

如果要在树定义的序列中查找下一个元素，可能需要遍历树的整个高度，当然，在平衡树中这是O（log N），在不平衡树中这是O（N）

Answer 2

我认为BST的最坏情况是O（高度-1），对于平衡树是O（log n），对于不平衡树是O（n-1），这是对的吗？

是的，当从k到k 1旅行时，您只需要向上或向下移动，而不需要两者兼而有之（因为不变量是左孩子

虽然O（高度-1）可以写成O（高度）（并且类似地写成O（n））。