Treap: an elegant Data Structure

Today I'm gonna code a relatively simple and efficient data structure, treap. Basically treap is like a improved Binary Search Tree(BST). Although BST gives lg(n) time performance  on searching and inserting the values but it has a drawback which makes it most of the times impractical. BST could reshape itself in linked list on certain values. To overcome this problem many solutions have been provided like AVL trees, RB(Red-Black) trees, 2-3-4 trees and so on. These trees maintains the height to lg(n) which assures the  lg(n) performance.
   Treap also does the same but in much simple manner. Treap = "Tree" + "Heap". If you've already coded a BST and a heap, treap must be a piece of cake for you. Treap is built on the idea of "Randomized BST". Here randomized means the input for BST is randomly distributed. It doesn't follow any predefined rule. In practice we don't have control over input data so we add the randomness in BST in form the heap priority. Treap nodes have two things, key and priority. Key is used for inserting values exactly as in BST while priority is maintained as in heap. Formally, key of left child should be less than or equal to right child and priority of parent node should be greater than its child nodes.
   Here I've implemented only insert() and delete(). They works as follows:
   Insertion : Insertion in treap works exactly as in BST with the addition that we've to maintain the heap property of nodes. For maintaining the priority in nodes there are two methods, rotateLeft() and rotateRight()
   Deletion : Deletion works in opposite way of insertion. We first locate the node to be deleted and then float it down till it become leaf node and the eventually clip it.

Here's the implementation in Java

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Random;

class Treap{
    // Nodes in treap
    class Node{
        private int key, priority;
        Node left, right;
        Node( int k){
            this.key = k;
            // this.hashCode() is for uniqueness
            this.priority = this.hashCode();
            left = right = null;
        }
    }

    Node root;

    Treap(){root = null;} // Constructor

    public void insert (int key){
        root = insert (root, key);
    }

    private Node insert (Node dummy, int val){
        if (dummy == null){
            return new Node(val);
        }
        else if (val < dummy.key){
            dummy.left = insert(dummy.left, val);
            if (dummy.left.priority > dummy.priority){
                dummy = rotateRight(dummy);
            }
        }
        else if (val > dummy.key){
            dummy.right = insert(dummy.right, val);
            if (dummy.right.priority > dummy.priority){
                dummy = rotateLeft(dummy);
            }
        }
        return dummy;
    }

    private Node rotateRight (Node dummy){
        Node tmp = dummy.left;
        dummy.left = tmp.right;
        tmp.right = dummy;
        return tmp;
    }

    private Node rotateLeft (Node dummy){
        Node tmp = dummy.right;
        dummy.right = tmp.left;
        tmp.left = dummy;
        return tmp;
    }

    public void printTreap(){
        // in-order traversal as in  BinarySearchTree
        print(root);
    }

    private void print(Node n){
        if (n == null)
            return ;
        else {
            print (n.left);
            System.out.print (n.key+" ");
            print (n.right);
        }
    }

    private boolean findNode (Node dummy, int query){
        while (dummy != null){
            if (query == dummy.key){
                return true;
            }
            if (query < dummy.key)
                dummy = dummy.left;
            else dummy = dummy.right;
        }
        return false;
    }

    public void deleteNode(int key){
        // findNode returns true if node exists otherwise false
        if (findNode(root, key))
            root = remove (root, key);
        else System.out.println ("There's no such key in treap.");
        
    }

    private Node remove (Node dummy, int val){
        if (val < dummy.key)    // to locate the node
            dummy.left = remove(dummy.left, val);
        else if (val > dummy.key)       // to locate the node
            dummy.right = remove(dummy.right, val);

        else {     //  node found
            if ((dummy.left == null && dummy.right == null)||                    
                    dummy == null ) return null;   //clip the leaf node

                // make sure both children exists
            else if (dummy.left != null && dummy.right != null){
                if (dummy.left.priority > dummy.right.priority){
                    dummy = rotateRight (dummy);
                    dummy.right = remove (dummy.right, val);

                }
                else {
                    dummy = rotateLeft (dummy);
                    dummy.left = remove (dummy.left, val);
                }
            }


            else if (dummy.left == null){   // node only having right child
                dummy = rotateLeft (dummy);
                dummy.left = remove (dummy.left, val);
            }
            else if (dummy.right == null){  // node only having left child
                dummy = rotateRight (dummy);
                dummy.right = remove (dummy.right, val);
            }

        }
        return dummy;
    }
}

class testDrive{
    public static void main (String [] S)throws IOException{
        Treap t = new Treap();
        Random gen = new Random();
        for (int i=1;i<10;i++){
            int value = gen.nextInt(100);
            // insert values in treap
            t.insert(value);
        }
        System.out.println("Content of treap");
        t.printTreap();
        System.out.println();

        int num;
        BufferedReader br = new BufferedReader (new InputStreamReader(System.in));
        // to test the deletion in treap
        for (int i=0;i<9;i++){
            num = Integer.parseInt(br.readLine());
            t.deleteNode(num);
            t.printTreap();
            System.out.println();
        }
    }
}

All paths from source to destination in simple graph

UPDATE: I've written a new tutorial for this question with more explanation and comments in code. I highly recommend you to go through this new link for better understanding.

https://techienotes.info/2015/09/03/all-paths-between-two-nodes-in-a-graph/

Q: Given a simple graph, print all the paths from source node to destination node.

A: We're going to traverse the graph and try all the possible paths we could get. We'll start DFS(Depth First Search) from the source node and will keep looking the different paths to destination during the course of complete dfs() procedure.
   Input is given as 2-D matrix where 1 represents an edge and 0 represents no edge. In output there will be a path printed per line.


Here's the Java code for the same.

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Arrays;
import java.io.InputStreamReader;

class allpaths {

 static int dim = 5, size = 0; // dim is number of nodes in graph
 // size had been used to keep record of index to remove node from Arraylist
    static boolean[] color = new boolean[dim + 1];      // to remember visit
    static int[][] graph = new int[10][10];
    static ArrayList<Integer> al = new ArrayList<Integer>();

    public static void main(String[] S) throws IOException {
         BufferedReader br = new BufferedReader (new InputStreamReader(System.in));
        for (int I = 1; I <= dim; I++) {
            String[] s = br.readLine().split(" ");
            int len = s.length;
            for (int J = 1; J <= len; J++) {
                graph[I][J] = Integer.parseInt(s[J - 1]);
            }
        }
        Arrays.fill(color, false);      // initially all are unvisited

        int src = Integer.parseInt(br.readLine());      //Source node
        int dst = Integer.parseInt(br.readLine());      //Destination node

        dfs(src, dst);  // backtracking
    }

    static void dfs(int src, int dst) {
        al.add(src);
        size++;
        color[src] = true;
        if (src == dst) {       // tests for base condition to stop
            for (Integer i : al) {
                //     Prints the path
                System.out.print(i + "  ");
            }
            System.out.println();
            return;
        }
        for (int I = 1; I <= dim; I++) {
            if (graph[src][I] == 1) {
                if (color[I] == false) {
                    dfs(I, dst);        // These lines do
                    color[I] = false;   // main job of backtracking
                    size--;
                    al.remove(size);
                }
            }
        }
    }
}

Input is given as

0 1 1 1 1
1 0 1 1 1
1 1 0 1 1
1 1 1 0 1
1 1 1 1 0
1
5

This is complete graph for 5 vertices. Source node is 1 and Destination node is 5. Output would look like this:

1  2  3  4  5  

1  2  3  5  

1  2  4  3  5  

1  2  4  5  

1  2  5  

1  3  2  4  5  

1  3  2  5  

1  3  4  2  5  

1  3  4  5  

1  3  5  

1  4  2  3  5  

1  4  2  5  

1  4  3  2  5  

1  4  3  5  

1  4  5  

1  5

Here each line shows a path from 1 to 5 via other nodes.