BST,找到下一个最高节点

Question

在BST,根据编程访谈曝光

"给定节点,您甚至可以在O(log(n))时间内找到下一个最高节点"Pg 65

BST中的节点将右子节点作为下一个最高节点,那么为什么O(log(n))？请改正

首先回答这个问题,然后否定它

Answer 1

"BST中的一个节点将右子节点作为下一个最高节点"(假设这里"下一个最高"表示下一个最大值) - 不,它没有.这可以是这样的,如果它没有左节点,但它并不总是如此(见下文1点).

下一个最大的值(使用该术语而不是"最高",因为后者可能与树高混淆)值来自两个地方之一:

首先,如果当前节点有一个正确的孩子,那么移动到那个正确的孩子,只要你能看到一个左孩子,就移动到它.

换句话说(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

否则(当前节点没有右孩子),你需要不断地向上移动到父(所以节点需要一个左,右和父指针),直到移动节点从是左孩子.如果你到达root并且仍然没有从左子节点向上移动,则原始节点已经是树中最高的节点.图形上可能是:

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

由于努力与树的高度成比例,因此平衡树(例如红黑,2-3-4和AVL)将具有O(log N)的时间复杂度,因为高度与log具有logN关系.东西的个数.这本书正在讨论平衡树,因为它包含了关于它们的片段:

• 此查找是一种快速操作,因为您在每次迭代时从搜索中消除了一半的节点.
• Lookup是二叉搜索树中的O(log(n))操作.
• 如果您可以保证在每次迭代时剩余要搜索的节点数量减半或几乎减半,则查找仅为O(log(n)).

所以,虽然它在这最后的报价承认一个BST可能不均衡,在O(日志N)的属性是只对那些变异的.

对于非平衡树,复杂性(最坏的情况)将是O(n),因为你可能最终得到退化树,如:

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