data-structures - BST，寻找下一个最高节点

Question

在 BST 中，根据暴露的编程面试

“给定一个节点，您甚至可以在 O(log(n)) 时间内找到下一个最高节点”第 65 页

BST 中的一个节点有右 child 作为下一个最高节点，那么为什么是 O(log(n))？请纠正

先回答问题，然后否定它

Answer 1

关于您的评论“BST 中的一个节点将右子节点作为下一个最高节点”(假设这里“下一个最高”表示下一个顺序值) - 不，它没有。

如果右 child 没有左子树，情况可能是这样，但并非总是如此。

下一个顺序值(我使用该术语而不是“最高”，因为后者可能与树的高度混淆，而“最大”意味着特定的(从低到高)顺序而不是任何顺序)值来自以下之一两个地方。

首先，如果当前节点有一个右 child ，移动到那个右 child ，然后，只要你能看到一个左 child ，就移动到它。

换句话说，用 S和 D作为源(当前)和目标(次大):

   S
  / \
 x   x <- This is the node your explanation chose,
    / \    but it's the wrong one in this case.
   x   x
  /
 D <----- This is the actual node you want.
  \
   x

否则(即，如果当前节点没有右 child )，您需要不断向上移动到父节点(因此节点需要右、左和父指针)，直到您移动的节点是左 child 。如果你到达根节点并且你仍然没有从左子节点向上移动，那么你的原始节点已经是树中最高的节点。

以图形方式说明整个过程:

x
 \
  D <- Walking up the tree until you came up
 / \     from a left node.
x   x
 \
  x
 / \
x   S
   /
  x

这种函数的伪代码(涵盖这两种情况)将是:

def getNextNode (node):
    # Case 1: right once then left many.

    if node.right != NULL:
        node = node.right
        while node.left != NULL:
            node = node.left
        return node

    # Case 2: up until we come from left.

    while node.parent != NULL:
        if node.parent.left == node:
            return node.parent
        node = node.parent

    # Case 3: we never came from left, no next node.

    return NULL

由于工作量与树的高度成正比(我们要么向下，要么向上然后向下)，平衡树的时间复杂度为 O(log N)因为高度有 logN项数的关系。

这本书在这里讨论的是平衡树，因为它包含了关于它们的以下片段:

此查找是一种快速操作，因为您在每次迭代时从搜索中消除了一半的节点。

查找是一个 O(log(n))二叉搜索树中的操作。

查找只是O(log(n))如果你能保证每次迭代时剩余要搜索的节点数将减半或接近减半。

因此，虽然它在最后一句话中承认 BST 可能不平衡，但 O(log N)属性仅适用于那些变体。

对于非平衡树，复杂度(最坏情况)为 O(n)因为你最终可能会得到退化的树，比如:

S             D
 \           /
  x         x
   \         \
    x         x
     \         \
      x         x
       \         \
        x         x
       /           \
      D             S