Union-Find:删除后继者

Question

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

继承者删除.给定一组N个整数S = {0,1,...,N-1}和一系列以下形式的请求:

从S中删除x找到x的后继:S中的最小y,使得y≥x.设计一种数据类型,以便所有操作(构造除外)应采用对数时间或更好.

即使我找不到解决方法和文章解释如何做到这一点Union-Find,我也无法想象它是如何工作的.

例如: Delete(X)可以通过实现Union(X,X+1),但它如何作为删除我只是无法可视化.与发现相似Successor(X).

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

Answer 1

一开始，假设列表中有 10 个数字，从 0 到 9。

0 1 2 3 4 5 6 7 8 9

就像在普通的加权联合查找中一样，这些数字中的每一个都是一个数组索引，数组索引值的内容代表数组索引的父级。

因此，最初 0 的父代是 0，而 0 的根（祖父母中最伟大的）也是 0。所有数字都是如此。

现在，我们删除一个数字，比如 5。

删除 5 意味着，我们实际上是在说 union (5, 6)。

所以，这正在发生。

在这个阶段，如果我们想找到一个数 x 的后继者，我们可以简单地找到它作为根 (x+1)。所以，4 的后继是 6，因为根 (4+1) 是 6。

现在，假设我们删除了 6。这意味着 union (6, 7)。

这很棘手，因为在加权联合查找中，应将 7 (7) 的根添加到 6 (6) 的根中，因为 6-5 分量具有更大的权重。但如果我们这样做，我们将如何找到继任者？因为这会发生：

所以，如果想要 4 的后继，我们不能说它是 root (4+1) 因为 root (5) 是 6 但 6 已经被删除了。4 的后继者应该是 7。

因此，我们可以使用另一个名为 actualList 的数组。这个数组将存储需要在我们列表中的实际数字 - 对应于任何已删除数字的根。需要在 union() 中进行一行修改才能做到这一点。

在这种情况下，actualList 数组将存储对应于索引 root(5) 和 root(6) 的 7。因此，actualList[root(4+1)] 将产生 4 的后继者的正确答案为 7。

要找到后继者，我们必须访问 actualList[(root(x+1)] 而不是 root (x+1)。

这是我在 Java 中对整个事情的实现：

public class SuccessorWithDelete {

    private int id[];
    private int sz[];
    private int actualList[];
    private int N;

    public SuccessorWithDelete(int N){
        this.N = N;
        id = new int[N];
        sz = new int[N];
        actualList = new int[N];
        for(int i=0; i<N; i++){
            id[i] = i;
            sz[i] = 1;
            actualList[i] = i;
        }
    }

    // returns the root of the component the integer is in
    private int root(int i){
        while(id[i]!=i){

            i = id[i];
        }
        return i;
    }

    // weighted quick union
    public void union(Integer p, Integer q) {

        int pRoot = root(p);
        int qRoot = root(q);
        if (sz[pRoot] < sz[qRoot]) {
            id[pRoot] =  qRoot;
            sz[qRoot] = sz[qRoot] + sz[pRoot];

        } else {
            id[qRoot] = pRoot;
            sz[pRoot] = sz[pRoot] + sz[qRoot];
            actualList[pRoot] = qRoot;              // this is the crucial step
        }
    }


    public void remove(int x){
        union(x, x+1);

    }

    public int successor(int x){
        return actualList[(root(x+1))];
    }
}

Answer 2

我们可以设置union-find数据结构来表示这个问题.不变量将root(x)存储yS中的最小值y >= x.

首先,我们可以确保节点1..N上的初始union-find数据结构满足不变量:我们只需确保每个初始节点都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个节点开始,逐步进行联合(2,3),联合(4,5)和联合(3,4) - 这对应于删除2,然后是4,然后是3.注意图中的箭头从a到b对应a.root = b.当我谈到上面的"植根于一个节点的树"时,考虑箭头反过来会更自然.

没有删除节点.

2已删除 - 联合(2,3)

2和4删除 - 联合(2,3),联合(4,5)

2,3,4删除 - 联合(2,3),联合(4,5),联合(3,4)