Union-Find: Successor with delete

Question

I'm trying to solve this problem of Union-Find which goes like

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.

Even though I find few solution and article explaining how this can be done with Union-Find, I 'm not able to visualise how it's working.

For instance: Delete(X) can be accomplished by Union(X,X+1), but how it is acting as delete I'm just not able to visualize. Similar with finding Successor(X).

Any help/direction or elaboration of explanations will be of great help.

Answer 1

In the beginning, let's say there are 10 numbers in the list from 0 to 9.

0 1 2 3 4 5 6 7 8 9

Just like in normal weighted union-find, each of these numbers is an array index and the content of the array index value represents the parent of the array index.

So, initially, the parent of 0 is 0 and the root of 0 (the grandest of grandparents) is also 0. The same is true for all numbers.

Now, we remove a number, say 5.

Removing 5 means, we are actually saying union (5, 6).

So, this is happening.

At this stage, if we want to find the successor of a number x, we can simply find it as root (x+1). So, the successor of 4 is 6, because root (4+1) is 6.

Now, let's say we remove 6.This means union (6, 7).

This is tricky because in weighted union-find, the root of 7 (7) should be added to the root of 6 (6) as the 6-5 component has more weight. But if we do that, how will we find the successor? Because this will happen:

So, if want the successor of 4, we can't say it is root (4+1) as root (5) is 6 but 6 has been removed. The successor of 4 should be 7.

So, we can use another array called, say, actualList. This array will store the actual number that needs to be on our list - that corresponds to the root of any removed number. One line of modification will be needed in union() to do this.

In this case, the actualList array will store 7 corresponding to the index root(5) and root(6). So, actualList[root(4+1)] will yield the correct answer of the successor of 4 to be 7.

To find the successor, we'll have to access actualList[(root(x+1)] and not root (x+1).

Here's my implementation of the whole thing in 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

We can set up a union-find datastructure to represent this problem. The invariant will be that root(x) stores the smallest y in S such that y >= x.

First, we can make sure the initial union-find datastructure on nodes 1..N satisfies the invariant: we simply make sure that each initial node i stores i.

To simulate the removal of x, we perform union(x, x+1). We'll have to make sure that our implementation of union-find preserves our invariant. If we're joining root(x) to root(x+1), that's fine, but if we join root(x+1) to root(x), then we'll need to store the value from root(x+1) into the node root(x).

We need to be a little careful to make sure that union runs in guaranteed O(log n) time. For that, we need to store per node the size of the tree rooted at node. Here's an implementation and a simple example.

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)

Here's an example. We start with 5 nodes, and progressively do union(2, 3), union(4, 5) and union(3, 4) -- which correspond to deleting 2, then 4, then 3. Note that in the picture an arrow from a to b corresponds to a.root = b. When I talk about "tree rooted at a node" above, it'd be more natural to consider the arrows to go the other way round.

No nodes deleted.

2 deleted -- union(2, 3)

2 and 4 deleted -- union(2, 3), union(4, 5)

2, 3, 4 deleted -- union(2, 3), union(4, 5), union(3, 4)

Answer 3

I guess one should go without the weighted union. Once you do the union with next element (keeping in mind that next element's root will become the root element for the removed element), roots will be there at the top of the tree. If one wants to visualize it, don't visualize in the form of a tree. Instead, visualize the parent elements' list.

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)