algorithm - Union-Find:后继删除

Question

我正在尝试解决这个 Union-Find 问题

Successor with delete. Given a set of N integers S={0,1,…,N−1} and a sequence of requests of the following form:

Remove x from S Find the successor of x: the smallest y in S such that y≥x. design a data type so that all operations (except construction) should take logarithmic time or better.

尽管我发现很少有解决方案和文章解释如何使用 Union-Find 完成此操作，但我无法想象它是如何工作的。

例如:Delete(X) 可以通过Union(X,X+1) 来完成，但是我无法想象它是如何作为删除的。与查找 Successor(X) 类似。

任何帮助/指导或解释的详细说明都会有很大帮助。

Answer 1

我们可以建立一个 union-find 数据结构来表示这个问题。不变式是 root(x) 在 S 中存储最小的 y 使得 y >= x。

首先，我们可以确保节点 1..N 上的初始联合查找数据结构满足不变量:我们只需确保每个初始节点 i 存储 i .

为了模拟 x 的移除，我们执行 union(x, x+1)。我们必须确保我们的 union-find 实现保留我们的不变量。如果我们将 root(x) 连接到 root(x+1)，那很好，但是如果我们连接 root(x+1) 到 root(x)，然后我们需要将 root(x+1) 的值存储到节点 root(x).

我们需要小心确保 union 在保证的 O(log n) 时间内运行。为此，我们需要为每个节点存储以节点为根的树的大小。这是一个实现和一个简单的示例。

class Node:
    def __init__(self, i):
        self.i = i
        self.size = 1
        self.max = i
        self.root = self

def root(node):
    r = node
    while r.root != r:
        r = r.root
    # perform path compression
    while node.root != node:
        node, node.root = node.root, r
    return r

def union(n1, n2):
    n1 = root(n1)
    n2 = root(n2)
    if n1.size < n2.size:
        n1, n2 = n2, n1
    n2.root = n1
    n1.size += n2.size
    n1.max = max(n1.max, n2.max)

def Sfind(uf, i):
    return root(uf[i]).max

def Sdelete(uf, i):
    union(uf[i], uf[i+1])

N = 100
S = dict((i, Node(i)) for i in xrange(1, N))
Sdelete(S, 10)
Sdelete(S, 12)
Sdelete(S, 11)

for i in [10, 12, 13, 20]:
    print i, Sfind(S, i)

这是一个例子。我们从 5 个节点开始，逐步执行 union(2, 3)、union(4, 5) 和 union(3, 4) —— 对应于删除 2、然后是 4、然后是 3。请注意图中的箭头从a到b对应a.root = b。当我在上面谈论“以节点为根的树”时，更自然地考虑箭头指向相反的方向。

没有节点被删除。

2 已删除 -- union(2, 3)

删除 2 和 4 -- union(2, 3), union(4, 5)

删除 2、3、4 -- union(2, 3), union(4, 5), union(3, 4)