在O（1）中的bst中查找继承者和前任者

Question

是否有一种方法可以在插入或删除节点时将一些信息添加到节点中。这样就可以在O（1）中获得后继者和前任者。

Answer 1

如果在每个节点中还存储了对父节点的引用，那么您将看到如何在给定节点的情况下找到下一个节点：

getNext(node):
    if node.right is not null:
        node = node.right
        while node.left is not null:
            node = node.left
        return node
    while node.parent is not null:
        if node.parent.left == node:  # node is a left child
            return node.parent
        node = node.parent  # node was a right child
    # no more nodes...
    return null

如您所见，其中涉及到循环，因此这需要花费不同的时间。在最坏的情况下，跟随叶的节点可能是根，而跟随根的节点可能是深叶。因此，一个调用最多可能涉及到node的h个重新分配，之后是树中的许多边（h是树的高度）。

但是，如果您考虑从最左边的叶子开始在所有节点上进行完整遍历，则会看到每个边沿都精确地遍历了2次：第一次使用left或right，第二次使用parent。这意味着对于对getNext的n调用（先前的结果被馈送到下一个调用，而最后一个调用返回null），您将访问2（n-1）边，这意味着平均一个调用遍历2（n-1）/ n边，该边小于，但接近2。

因此，这表示摊销的O（1）时间复杂度。