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

Am I right in thinking that the worst case for any BST is O(height-1), which is O(log n) for balanced trees, and O(n-1) for unbalanced trees?

是的，您只需要在从 k 出发时上下移动。至 k+1 ，从不两者兼而有之(因为不变量是 left child < parent < right child )。

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