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

Question

我对通过二叉搜索树前进和后退的最坏情况效率感兴趣。

不平衡树：

   5
  /
 1 
  \
   2
    \
     3
      \
       4

看起来最坏的情况是 4->5，这需要 4 次操作。

平衡树：

   2
  / \
 1   4
    / \ 
   3   5

最坏的情况是 2->3，需要 2 次操作。

我是否认为任何 BST 的最坏情况是 O(height-1)，对于平衡树是 O(log n)，对于不平衡树是 O(n-1)？

Answer 1

我是否认为任何 BST 的最坏情况是 O(height-1)，对于平衡树是 O(log n)，对于不平衡树是 O(n-1)？

是的，您只需要在从kto移动时向上或向下移动，而k+1不是两者都需要（因为不变量是left child < parent < right child）。

尽管 O(height-1) 可以写成 O(height)（对于 O(n) 也是如此）。

Answer 2

如果您正在考虑按顺序遍历树，那么复杂性在平衡方面不会改变。算法还在

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

每步 1 个操作。

当您开始应用查找、插入和删除时，余额就会发挥作用。

为了使这些操作在 O(log N ) 中进行，需要一个平衡树。

如果您试图在树定义的序列中找到下一个元素，您可能需要遍历树的整个高度，当然在平衡树中这是 O ( log N )，而在不平衡树中这是 O(N)