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

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 2

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 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)

Answer 4

Actually, I find this problem can be solved by finding the largest value in your components. You can directly use the original weighted union-find code without changing the arrangement of the trees and the roots. However, the successor here is not the root but the largest one in the components. Hope this will help you.

Answer 5

I started out from the path compressed implementation of the non-weighted version of quick union algorithm.

Then, implementing these new operations are simple:

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

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

Drawing these scenarios on paper made me understand how it works. For anyone interested, here is my test case for the implementation:

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);

And my (minified) implementation (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);
}

Answer 6

I found a solution from https://www.programmerall.com/article/7941762158/

I have some changes from it.

The requirement of the question has a sequence S of 0~n-1, remove any x from S, and then call getSuccessor(x), the method will return a y, this y is the remaining y>=x in S The smallest number. For example, when 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

According to the above example, it can be seen that, in fact, all the removed numbers are made into a union, and root is the maximum value in the subset, then getSuccessor(x) is actually to obtain the maximum value of the remove number + 1.

And for the number x without remove, what should getSuccessor(x) equal? There would be 3 cases:

Case1: The number itself is the last number, return itself.

Case2: The next number is not removed, return x+1.

Case3: The next number is removed, return the maximum value of the remove number + 1

Codes below in 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));
    }
}

Answer 7

Just a little bit more explaination for Meghashyam Chirravoori's answer.

we keep another list called successor_list[], It is used to find the successor. but to find the succesor, we don't look them up directly. instead, we look up its root first. then we found the root's successor.

the root's succssor is the successor for the whole branch. this is the invariant we want to keep during our operation.

in the beginning. without deleting anything, according to the question, the smallest value >= the node is the node iteself. the invariant keeps.

when we delete x . we union( x , x + 1 ). we use the normal union find weighted algorithm. so there are two cases.

1. x's branch is smaller, then the branch is attached to root of x + 1. the successor list does not need to update. invariant keeps.
2. x's branch is bigger, then x + 1 's branch is attach to the x's branch. invariant broken. then we need to update the successor list.

    root_x = root(x) // this is the root for the new united branch
    root_y = root(x + 1)
    successor[root_x] = successor[root_y]

after this operation, the invariant keeps, the successor of the root is the sucessor for the whole branch.

Answer 8

Only the max of connected components will be non-deleted elements. we can have another list/array in weighted quick-union data structure that stores for each root the largest/max element in the deleted/connected components

    class UnionFind:
        def __init__(self, N):
            self.total_nodes = N
            self.nodes = []
            self.size = []
            self.root_max = []
    
            # set default values
            for i in range(N):
                self.nodes.append(i)
                self.size.append(1)
                self.root_max.append(i)
    
        def _root(self, i):
            while self.nodes[i] != i:
                i = self.nodes[i]
            return i
    
    
        def _union(self, node_p, node_q):
            root_p = self._root(node_p)
            root_q = self._root(node_q)
    
            # check size for weighted union operation
            if self.size[root_p] > self.size[root_q]:
                self.nodes[root_q] = root_p
                self.size[root_p] = self.size[root_p] + self.size[root_q]

                # store the max element for each root.
                if self.root_max[root_p] < self.root_max[root_q]:
                    self.root_max[root_p] = self.root_max[root_q]
    
            else:
                self.nodes[root_p] = root_q
                self.size[root_q] = self.size[root_p] + self.size[root_q]
                # store the max element for each root.
                if self.root_max[root_q] < self.root_max[root_p]:
                    self.root_max[root_q] = self.root_max[root_p]
    
    
        def delete(self, node_x):
            if self.nodes[node_x] is node_x:
                node_x_plus_1 = node_x + 1
                self._union(node_x, node_x_plus_1)
            else:
                print("node {} is already deleted.".format(node_x))
    
        def successor(self, node_x):
            if node_x == self.total_nodes - 1:
                return node_x
        
            # delete and successor operations are combined.
            self.delete(node_x)
            return self.root_max[self._root(node_x)]
    
    
    if __name__ == '__main__':
        total_nodes = 10
        uf = UnionFind(total_nodes)
        delete_x = 6
    
        # delete and successor operations are combined.
        print(uf.successor(delete_x))
        print(uf.successor(7))
        print(uf.successor(6))
        print(uf.successor(5))
        print(uf.successor(0))
        print(uf.successor(9))