12

我正在尝试解决 Union-Find 的这个问题，就像

后继删除。给定一组 N 个整数 S={0,1,…,N−1} 和以下形式的请求序列：

从 S 中删除 x 找到 x 的后继：S 中最小的 y，使得 y≥x。设计一种数据类型，以便所有操作（除了构造）都应该花费对数时间或更好。

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

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

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

4

6 回答 6

11

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

0 1 2 3 4 5 6 7 8 9

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

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

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

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

所以，这正在发生。

想象当 5 被移除时会发生什么

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

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

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

想象一下如果我们尝试删除 5 和 6 而不在 union() 中进行任何编辑会发生什么

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

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

在这种情况下，actualList 数组将存储 7 对应的索引 root(5) 和 root(6)。因此，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))];
    }
}
于 2018-09-29T03:39:28.067 回答
11

我们可以建立一个联合查找数据结构来表示这个问题。不变量将是在 S 中root(x)存储最小y的，使得y >= x.

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

为了模拟 的移除x，我们执行union(x, x+1). 我们必须确保我们的 union-find 实现保留了我们的不变量。如果我们加入root(x)to root(x+1)，那很好，但如果我们加入root(x+1)to root(x)，那么我们需要将值 from 存储root(x+1)到 noderoot(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 已删除

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

2和4已删除

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

2, 3, 4 已删除

于 2017-03-17T16:48:06.333 回答
1

我想应该没有加权联合。一旦你与下一个元素进行联合（记住下一个元素的根将成为被移除元素的根元素），根将在树的顶部。如果要形象化它，不要形象化成一棵树。相反，可视化父元素的列表。

class SuccessorUF(object):
    def __init__(self, n):
        self.parents = []
        for i in range(0, n):
            self.parents.append(i)

    def root(self, p):
        while self.parents[p] != p:
            p = self.parents[p]
        return p

    def union(self, p, q):
        root_p = self.root(p)
        root_q = self.root(q)
        self.parents[root_p] = root_q

    def remove(self, p):
        """
        :param (int) p: 
        :return: 
        """
        if p == len(self.parents) - 1:
            self.parents.pop(p)
            return
        self.union(p, p + 1)

    def successor(self, p):
        if p > len(self.parents) - 1 or self.root(p) != p:
            return 'DELETED_OR_NOT_EXISTED_EVER'  # Deleted Element
        if p == len(self.parents) - 1:
            return 'LAST_ELEMENT'
        return self.root(p + 1)
于 2017-08-29T04:31:43.287 回答
0

我从快速联合算法的非加权版本的路径压缩实现开始。

然后，实现这些新操作很简单：

void Remove(int x)
{
    Union(x, x + 1);
}

int SuccessorOf(int x)
{
    return RootOf(x + 1);
}

在纸上画出这些场景让我明白了它是如何工作的。对于任何感兴趣的人，这是我的实现测试用例：

const int capacity = 8;
var sut = new _03_SuccessorWithDelete(capacity);
for (int i = 0; i < capacity - 1; i++)
    sut.SuccessorOf(i).Should().Be(i + 1);

sut.Remove(3);
sut.SuccessorOf(2).Should().Be(4);

sut.Remove(2);
sut.SuccessorOf(1).Should().Be(4);

sut.Remove(4);
sut.SuccessorOf(1).Should().Be(5);

sut.Remove(6);
sut.SuccessorOf(5).Should().Be(7);

sut.Remove(5);
sut.SuccessorOf(1).Should().Be(7);
sut.SuccessorOf(0).Should().Be(1);

还有我的（缩小的）实现（C#）：

public sealed class _03_SuccessorWithDelete
{
    private readonly int[] id;
    public _03_SuccessorWithDelete(int n)
    {
        id = new int[n];
        for (int i = 0; i < id.Length; i++) id[i] = i;
    }
    public void Remove(int x) => Union(x, x + 1);
    public int SuccessorOf(int x) => RootOf(x + 1);
    public bool Connected(int p, int q) => RootOf(p) == RootOf(q);
    private int RootOf(int x)
    {
        while (x != id[x]) { id[x] = id[id[x]]; x = id[x]; }
        return x;
    }
    public void Union(int p, int q) => id[RootOf(p)] = RootOf(q);
}
于 2020-06-09T07:22:49.350 回答
0

实际上，我发现这个问题可以通过找到组件中的最大值来解决。您可以直接使用原始加权并集查找代码，而无需更改树和根的排列。但是，这里的后继者不是根，而是组件中最大的一个。希望这会帮助你。

于 2020-05-28T16:51:32.837 回答
0

我从https://www.programmerall.com/article/7941762158/找到了一个解决方案

我有一些改变。

题目要求有一个0~n-1的序列S，从S中取出任意一个x，然后调用getSuccessor(x)，方法会返回y，这个y是S中剩下的y>=x的最小数. 例如，当S={0,1,2,3,4,5,6,7,8,9}

remove 6, then getSuccessor(6)=7

remove 5, then getSuccessor(5)=7

remove 3, then getSuccessor(3)=4

remove 4, then getSuccessor(4)=7

remove 7, then getSuccessor(7)=8, getSuccessor(3)=8

根据上面的例子可以看出，其实就是把所有被移除的数都做成了一个union，而root是子集中的最大值，那么getSuccessor(x)其实就是获取remove的最大值数字 + 1。

对于没有删除的数字 x，应该getSuccessor(x)等于什么？会有3种情况：

Case1：数字本身是最后一个数字，返回自身。

Case2：下一个数不去掉，返回x+1。

Case3：下一个数被移除，返回移除数的最大值+1

JAVA代码如下。

public class Successor {
    private int num;
    private int[] id;
    private boolean[] isRemove;

    public Successor(int n) {
        num = n;
        id = new int[n];
        isRemove = new boolean[n];
        for (int i = 0; i < n; i++) {
            id[i] = i;
            isRemove[i] = false;
        }
    }

    public int find(int p) {
        while (p != id[p])
            p = id[p];
        return p;
    }

    public void union(int p, int q) {
        // The union here takes the larger root
        int pRoot = find(p);
        int qRoot = find(q);
        if (pRoot == qRoot)
            return;
        else if (pRoot < qRoot)
            id[pRoot] = qRoot;
        else
            id[qRoot] = pRoot;
    }

    public void remove(int x) {
        isRemove[x] = true;
        // Determine whether the adjacent node is also removed by remove, if remove is
        // removed, union
        if (x > 0 && isRemove[x - 1]) {
            union(x, x - 1);
        }
        if (x < num - 1 && isRemove[x + 1]) {
            union(x, x + 1);
        }
    }

    public int getSuccessor(int x) {
        if (x < 0 || x > num - 1) {// Out-of-bounds anomaly
            throw new IllegalArgumentException("Access out of bounds!");
        } else if (isRemove[x]) {
            if (find(x) + 1 > num - 1) // x and the number greater than x are removed, return -1
                return -1;
            else // The maximum value of all the remove numbers is +1, which is the successor
                return find(x) + 1;
        } else if (x == num - 1) {// the last elmemnet, return itself.
            return x;
        } else if (isRemove[x + 1]) { // if the next element is removed, return The maximum value of all the remove
                                      // numbers is +1, which is the successor
            return find(x + 1) + 1;
        } else { // if the next element is not removed && itself is not removed, return next
                 // element.
            return x + 1;
        }
    }

    public static void main(String[] args) {
        Successor successor = new Successor(10);
        successor.remove(2);
        successor.remove(4);
        successor.remove(3);
        System.out.println("the successor is : " + successor.getSuccessor(3));
        successor.remove(7);
        System.out.println("the successor is : " + successor.getSuccessor(0));
        System.out.println("the successor is : " + successor.getSuccessor(1));
        System.out.println("the successor is : " + successor.getSuccessor(9));
    }
}
于 2021-11-20T16:32:05.127 回答