Insert and delete program in AVL tree 


 public class AVLTree {
    private static Node root;

    static Node insert(Node node, int data) {
        // if node is null then create a node and return
        if(node == null) {
            return new Node(data);
        } else if(data < node.data) {
            // insert into left sub tree 
            node.left = insert(node.left, data);
        } else if(data > node.data) {
            // insert into right sub tree 
            node.right = insert(node.right, data);
        }

        // set height of current node 
        node.height = getHeightOfNode(node);
        // check the balance factor to perform rotation of tree 
        if(getBalanceFactor(node) == 2) {
            if(getBalanceFactor(node.left) == 1) {
                return performLLRotation(node);
            } else if(getBalanceFactor(node.left) == -1) {
                return performLRRotation(node);
            }
        } else if(getBalanceFactor(node) == -2) {
            if(getBalanceFactor(node.right) == -1) {
                return performRRRotation(node);
            } else if(getBalanceFactor(node.right) == 1) {
                return performRLRotation(node);
            }
        }
        return node;
    }
    
    static Node delete(Node node, int data) {
        // if no elements to delete return null 
        if(node == null) {
            return null;
        }
        // if left and right child null then return null 
        if(node.left == null && node.right == null) {
            // if node is root then assign root as null 
            if(node == root) {
                root = null;
            }
            return null;
        }
        // traverse left or right sub tree 
        if(data < node.data) {
            node.left = delete(node.left, data);
        } else if(data > node.data) {
            node.right = delete(node.right, data);
        } else {
            // we found the node so delete it
            // we found the key, delete it. We can use inorder predecessor or inorder 
            // successor to replace this node to reference it's sub trees
            // we are deciding based on height of left or right sub tree for chosing inorder 
            // predecessor or successor
            Node inorderPredOrSucc = null;
            if(getHeightOfNode(node.left) > getHeightOfNode(node.right)) {
                inorderPredOrSucc = inorderPredecessor(node.left);
                node.data = inorderPredOrSucc.data;
                node.left = delete(node.left, inorderPredOrSucc.data);
            } else {
                inorderPredOrSucc = inorderSuccessor(node.right);
                node.data = inorderPredOrSucc.data;
                node.right = delete(node.right, inorderPredOrSucc.data);
            }
        }
        
        // update height 
        node.height = getHeightOfNode(node);
        
        // balance factor and rotation 
        if(getBalanceFactor(node) == 2) {
            if(getBalanceFactor(node.left) == 1 || getBalanceFactor(node.left) == 0) {
                return performLLRotation(node);
            } else if(getBalanceFactor(node.left) == -1) {
                return performLRRotation(node);
            }
        } else if(getBalanceFactor(node) == -2) {
            if(getBalanceFactor(node.right) == -1 || getBalanceFactor(node.left) == 0) {
                return performRRRotation(node);
            } else if(getBalanceFactor(node.left) == 1) {
                return performRLRotation(node);
            }
        }
        return node;
    }
    
    static Node inorderPredecessor(Node node) {
        while(node != null && node.right != null) {
            node = node.right;
        }
        return node;
    }
    
    static Node inorderSuccessor(Node node) {
        while(node != null && node.left != null) {
            node = node.left;
        }
        return node;
    }

    static int getHeightOfNode(Node node) {
        int leftHeight = node.left != null ? node.left.height : 0;
        int rightHeight = node.right != null ? node.right.height : 0;
        return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;
    }

    static int getBalanceFactor(Node node) {
        int leftHeight = node.left != null ? node.left.height : 0;
        int rightHeight = node.right != null ? node.right.height : 0;
        return leftHeight - rightHeight;
    }

    static Node performLLRotation(Node node) {
        // if will become new root 
        Node newRoot = node.left;
        // set successor sub tree 
        node.left = newRoot.right;
        // assign right child of tree 
        newRoot.right = node;

        // update height of modified nodes
        node.height = getHeightOfNode(node);
        newRoot.height = getHeightOfNode(newRoot);

        if(root == node) {
            root = newRoot;
        }
        return newRoot;
    }

    static Node performLRRotation(Node node) {
        // left child of current root
        Node leftChild = node.left;
        // it will become root after rotation
        Node newRoot = leftChild.right;
        // free new root's left and right
        leftChild.right = newRoot.left;
        node.left = newRoot.right;
        // set left and right sub tree of new root 
        newRoot.left = leftChild;
        newRoot.right = node;
        // update height of modified nodes
        leftChild.height = getHeightOfNode(leftChild);
        node.height = getHeightOfNode(node);
        newRoot.height = getHeightOfNode(newRoot);

        if(root == node) {
            root = newRoot;
        }
        return newRoot;
    }

    static Node performRRRotation(Node node) {
        // make right child as new root
        Node newRoot = node.right;

        // free new root's left 
        node.right = newRoot.left;
        // assign left sub tree of new root
        newRoot.left = node;

        // update height of modified nodes
        node.height = getHeightOfNode(node);
        newRoot.height = getHeightOfNode(newRoot);

        if(root == node) {
            root = newRoot;
        }
        return newRoot;
    }

    static Node performRLRotation(Node node) {
        // get right sub tree 
        Node rightChild = node.right;

        // make node.right.left as new root 
        Node newRoot = node.right.left;

        // free newRoot's left and right 
        node.right = newRoot.left;
        rightChild.left = newRoot.right;

        // assign left and right sub tree of new root 
        newRoot.left = node;
        newRoot.right = rightChild;

        // update height of modified nodes
        node.height = getHeightOfNode(node);
        rightChild.height = getHeightOfNode(rightChild);
        newRoot.height = getHeightOfNode(newRoot);

        if(root == node) {
            root = newRoot;
        }
        return newRoot;
    }

    static void preOrderTraversal(Node root) {
        if(root == null) {
            return;
        }
        System.out.print(root.data + " ");
        preOrderTraversal(root.left);
        preOrderTraversal(root.right);
    }

    static void performAllRotations() {
        // LL Rotation
        root = insert(null, 50);
	    insert(root, 100);
	    insert(root, 30);
	    insert(root, 40);
	    insert(root, 20);
	    insert(root, 10);
	    System.out.println("Test Case LL Rotation : ");
	    preOrderTraversal(root);
	    
	    // LR Rotation
	    root = insert(null, 50);
	    insert(root, 100);
	    insert(root, 30);
	    insert(root, 40);
	    insert(root, 45);
	    insert(root, 35);
	    insert(root, 20);
	    System.out.println("\nTest Case LR Rotation : ");
	    preOrderTraversal(root);

	    // RR Rotation
	    root = insert(null, 50);
	    insert(root, 25);
	    insert(root, 100);
	    insert(root, 60);
	    insert(root, 150);
	    insert(root, 200);
	    System.out.println("\nTest Case RR Rotation : ");
	    preOrderTraversal(root);

        // RL Rotation
	    root = insert(null, 50);
	    insert(root, 25);
	    insert(root, 100);
	    insert(root, 150);
	    insert(root, 60);
	    insert(root, 65);
	    System.out.println("\nTest Case RL Rotation : ");
	    preOrderTraversal(root);
    }

	public static void main (String[] args) {
	    performAllRotations();
	    
	    // create AVL tree 
	    int[] array = new int[] {10, 20, 30, 25,28, 27, 5};
	    root = insert(null, array[0]);
	    for(int i = 1; i < array.length; i++) {
	        insert(root, array[i]);
	    }
	    System.out.println("\nCreate and print pre-order of AVL tree : ");
	    preOrderTraversal(root);
	    
	    // delete 
	    delete(root, 28);
	    System.out.println("After deleting 28 : ");
	    preOrderTraversal(root);
	}

	private static class Node {
	    int data;
	    int height;
	    Node left;
	    Node right;
	    public Node(int data) {
	        this.data = data;
	        this.height = 1;
	    }
	}
}


Output
Test Case LL Rotation : 
30 20 10 50 40 100 
Test Case LR Rotation : 
40 30 20 35 50 45 100 
Test Case RR Rotation : 
100 50 25 60 150 200 
Test Case RL Rotation : 
60 50 25 100 65 150 
Create and print pre-order of AVL tree : 
25 10 5 20 28 27 30 After deleting 28 : 
25 10 5 20 30 27

Comments

Post a Comment

Popular posts from this blog

gsutil Vs Storage Transfer Service Vs Transfer Appliance

When transferring data from an on-premiss location, use gsutil When transferring data from another cloud storage provider, use storage transfer service gsutil is a Python application that lets you access Cloud Storage from the command line. You can use gsutil to do a wide range of bucket and object management tasks, including: Creating and deleting buckets. Uploading, downloading, and deleting objects. Listing buckets and objects. Moving, copying, and renaming objects. Editing object and bucket ACLs. gsutil performs all operations, including uploads and downloads, using HTTPS and transport-layer security (TLS). For a complete list of guides to completing tasks with gsutil, see  Cloud Storage How-to Guides . Storage Transfer Service is a product that enables you to: Move or backup data to a Cloud Storage bucket either from other cloud storage providers or from your  on-premises  storage. Move data from one Cloud Storage bucket to another, so that it is available to differe...
Read more

SQL basic interview question

Image
Question #1) What is SQL? Structured Query Language is a database tool which is used to create and access database to support software application. Question #2) What are tables in SQL? The table is a collection of record and its information at a single view. Question #3) What are different types of statements supported by SQL? There are 3 types of SQL statements 1) DDL (Data Definition Language):  It is used to define the database structure such as tables. It includes three statements such as Create, Alter, and Drop. Some of the DDL Commands are listed below CREATE : It is used for creating the table. 1 CREATE   TABLE &amp;amp;amp;nbsp;table_name 2 column_name1 data_type( size ), 3 column_name2 data_type( size ), 4 column_name3 data_type( size ), ALTER:  The ALTER table is used for modifying the existing table object in the database. ALTER TABLE table_name ADD column_name datatype OR ALTER TABLE table_name DROP ...
Read more