Disjoint Set - Implemented Using Tree

 Click Me
  • In this implementation of the disjoint set using a tree, every node will have the following structure
                class Node{
                        int rank;
                        int data;
                        Node parent;
                }
  • Each node will contain a single element and will represent a disjoint set containing that single element.
  • Union by rank always attaches the shorter tree to the root of the taller tree. Thus, the resulting tree is no taller than the originals unless they were of equal height, in which case the resulting tree is taller by one node.
  • Time Complexity: O(m), where m is the number of operations
  • Space Complexity: O(n), where n is the total number of nodes/elements
  • rank is also called weight.
  • I would recommend watching this video before going through the code: https://www.youtube.com/watch?v=ID00PMy0-vE

Code:

import java.util.*;

// a node that represent a single disjoint set containing a single data element
class Node{
    int data;
    // we are onl concernd about the rank pf root of the trees
    // we will be using this rank of parent nodes of trees to determine which tree is to be merged to other.
    int rank;
    // this represents the parent node of this node
    // we are going to make this parent equal to current node, initially in makeset() operation
    Node parent;
    
    // constructor
    Node(int x){
        this.data = x;
        this.rank = 1;
        this.parent = null;
    }
}

public class Main {
    
    // A map that will give us the node associated with a given data
    HashMap<Integer,Node> dataNodeMap;
    
    // constructor
    Main(){
        this.dataNodeMap = new HashMap<>();
    }
    
    // Method to do makeset operation
    // 1. We make a new node with given data
    // 2. we make parent  of this node as self
    // 3. finally we put this node in dataNodeMap
    // After running makeSet operation for all nodes/elements, we get individual nodes as individual disjoint sets
    public void makeSet(int data){
        Node node = new Node(data);
        node.parent = node;
        dataNodeMap.put(data,node);
    }
    
    // method to find the disjoint set to which diven element belongs
    public Node find(int x){
        Node node = this.dataNodeMap.get(x);
        Node parent = findSet(node);
        return parent;
    }
    
    // helper method for find method
    // it also uses path compression 
    private Node findSet(Node node){
        Node parent = node.parent;
        if(parent==node){
            return node;
        }
        else{
            parent = findSet(parent);
        }
        // here it is using path compression
        node.parent = parent;
        
        return parent;
    }
    
    // method to merge/ union two disjoint sets on the basis of rank
    // It will first find the disjoint set to which element 'x' belongs
    // Then it will find the disjoint set to which element 'y' belongs.
    // After this it will merge those disjoint sets by comaparing the ranks
    public void union(int x, int y){
        Node nodeX = this.dataNodeMap.get(x);
        Node nodeY = this.dataNodeMap.get(y);
        
        Node parentX = this.find(x);
        Node parentY = this.find(y);
        
        // if 'x' and 'y' are already in the same set, we return
        if(parentX==parentY){
            return;
        }
        
        // else if 'x' and 'y' are in different set, we merge by rank
        // if rank of 'x' is greater than or equal to rank of 'y', we merge y into x and update the rank of X
        // Here we are not concerned with the ranks for non-root nodes of trees
        if(parentX.rank>=parentY.rank){
            parentX.rank = parentX.rank + parentY.rank;
            parentY.parent = parentX;
        }
        // else if rank of 'y' is greater than the rank of 'x', we merge x into y and update rank accordingly
        // Here we are not concerned with the ranks for non-root nodes of trees
        else if(parentX.rank<parentY.rank){
            parentY.rank = parentY.rank + parentX.rank;
            parentX.parent = parentY;
        }
    }
    
    public static void main(String[] args) throws Exception {
        Main ds = new Main();
        
        // running makeSet operation for elements from 1-7
        for(int i=1;i<=7;i++){
            ds.makeSet(i);
        }
      
        // performing union operations
        ds.union(1,2);
        ds.union(2,3);
        ds.union(4,5);
        ds.union(6,7);
        ds.union(5,6);
        ds.union(3,7);
        
        // performing find operation on elements 1-7
        for(int i=1;i<=7;i++){
            System.out.print(ds.find(i).data+" ");
        }
        
        System.out.println();
        System.out.println();
        
        // printing current node and it's parent node from hashmap 'dataNodeMap' values
        for(Map.Entry<Integer,Node> hm : ds.dataNodeMap.entrySet()){
            System.out.print("Current Node: "+hm.getValue().data+" , Parent Node: "+hm.getValue().parent.data);
            System.out.println();
        }
    }
}



Output:

4 4 4 4 4 4 4 

Current Node: 1 , Parent Node: 4
Current Node: 2 , Parent Node: 4
Current Node: 3 , Parent Node: 4
Current Node: 4 , Parent Node: 4
Current Node: 5 , Parent Node: 4
Current Node: 6 , Parent Node: 4
Current Node: 7 , Parent Node: 4

Comments

Post a Comment

Popular posts from this blog

Binary Heap - Introduction

Image
#Image Credit - GeeksForGeeks Types of heap: Min Heap - every node is less than or equal to  its children(s) Max Heap - every node is more than or equal to its children(s) Operations on any heap : create insert extract/delete - we can extract/delete only the top node in any heap traverse delete entire heap get size of heap peek top of heap We should prefer implementing binary heap using arrays and not linked list, as during bottom to top heapify, in reaching the bottom rightmost node we take only 0(1) time in case of array but we take 0(n) time in case of linked list because first, we need to level order traverse the binary heap tree to get bottom-most rightmost element.  Heaps are used to efficiently implement:  Prim's Algorithm Heapsort Priority queue
Read more

Divide and Conquer - Introduction

Image
What is Divide and Conquer? Divide and Conquer is an algorithm paradigm in which we break down a given problem into smaller sub-problems of similar type until the sub-problems are small enough to be solved directly. The solution to these sub-problems are then combined to give a solution to the original problem.  Study the diagram below, it will then make more sense about what we do in Divide and Conquer : Where to Apply Divide and Conquer? The Divide and Conquer can be applied to all those problems that show Optimal Substructure property.  So, What is this Optimal Substructure property now? If we can break down a problem into similar sub-problems and the solution of these sub-problems can be used to create the solution of the whole problem, then that problem is said to have the Optimal Substructure property. For eg. : Fibonacci(n) = Fibonacci(n-1) + Fibonacci(n-2),    In this example, we can see that if we want to find the Fibonacci number at the nth place, we can br...
Read more

Bubble Sort

Time complexity - O(n^2)  || Space Complexity - O(1) Bubble sort is an inplace sorting algorithm, that means we do not any extra space while bubble sorting public class Main {     public static void main(String[] args) throws Exception {         int[] arr={1,4,4,5,6,2,3,90,120,43,0};                  System.out.println("UnSorted Array :");         for(int i=0;i<arr.length;i++){             System.out.print(arr[i]+" ");         }         System.out.println();         // bubble sort         for(int i=0;i<arr.length-1;i++){ // iterates through first to last cell             for(int j=0;j<arr.length-1-i;j++){ // inner loop controls swapping and extent to which swapping is to be performed in array     ...
Read more