algorithm - 在 O(1) 中找到 bst 中的后继者和前任者

Question

有没有办法在插入或删除节点时向 bst 中的节点添加一些信息。这样就有可能在 O(1) 中得到后继者和前驱者。

标签： algorithmdata-structuresbinary-search-tree

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

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

但是，如果您考虑从最左边的叶子开始对所有节点进行完整的遍历，您会看到每条边都被准确地遍历了 2 次：第一次使用leftor right，第二次使用parent。除了从根到最左边叶子的路径上的边缘：那些只被访问一次，用parent. 但为简单起见，我们假设它们也被访问了两次（我们稍微高估了工作）。

这意味着对于n次调用getNext（前一个结果被输入到下一个调用并且最后一个调用返回null），您将访问2(n-1)个边，这意味着平均一个调用遍历2(n-1) /n边，总是（稍微）小于 2。

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

当然，算法getPrevious将是相似的并且具有相同的时间复杂度考虑。

插入和删除操作（包括自平衡树中的旋转）的算法可以很容易地扩展，以parent在不增加时间复杂度的情况下更新每个相关节点中的引用。