Avl tree node insertion in java

Java program for Avl tree node insertion. Here more information.

// Java program
// AVL Tree insertion


// Avl Tree Node
class TreeNode
{
    public int data;
    public int height;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int data)
    {
        // Set node value of avl tree
        this.data = data;
        this.height = 1;
        this.left = null;
        this.right = null;
    }
}
class AvlTree
{
    // Tree root node
    public TreeNode root;

    public AvlTree()
    {
        // Set value of root
        this.root = null;
    }
    // Get the height of given node
    public int getHeight(TreeNode node)
    {
        if (node == null)
        {
            return 0;
        }
        return node.height;
    }
    // Get the max value of given two numbers
    public int maxHeight(int a, int b)
    {
        if (a > b)
        {
            return a;
        }
        else
        {
            return b;
        }
    }
    // Perform the Right rotate operation
    public TreeNode rightRotate(TreeNode node)
    {
        // Get left child node
        TreeNode leftNode = node.left;
        // Get left node right subtree
        TreeNode rightSubtree = leftNode.right;
        // Update the left and right subtree 
        leftNode.right = node;

        node.left = rightSubtree;
        // Change the height of modified node
        node.height = maxHeight(
          getHeight(node.left), 
          getHeight(node.right)) + 1;
       
        leftNode.height = maxHeight(
          getHeight(leftNode.left), 
          getHeight(leftNode.right)) + 1;
        
        return leftNode;
    }
    // Perform the Left Rotate operation
    public TreeNode leftRotate(TreeNode node)
    {
        // Get right child node
        TreeNode rightNode = node.right;
        // Get right node left subtree
        TreeNode leftSubtree = rightNode.left;
        // Update the left and right subtree 
        rightNode.left = node;
        node.right = leftSubtree;
        // Change the height of modified node
        node.height = maxHeight(getHeight(node.left), 
                                getHeight(node.right)) + 1;
        rightNode.height = maxHeight(
          getHeight(rightNode.left), 
          getHeight(rightNode.right)) + 1;
        return rightNode;
    }
    // Get the balance factor
    public int getBalanceFactor(TreeNode node)
    {
        if (node == null)
        {
            return 0;
        }
        return getHeight(node.left) - getHeight(node.right);
    }
    // Recursively, add a node in AVL tree
    // Duplicate keys (data) are not allowed
    public TreeNode addNode(TreeNode node, int data)
    {
        if (node == null)
        {
            // Return a new node
            return new TreeNode(data);
        }
        if (data < node.data)
        {
            node.left = addNode(node.left, data);
        }
        else if (data > node.data)
        {
            node.right = addNode(node.right, data);
        }
        else
        {
            // When given key data already exists
            return node;
        }
        // Change the height of current node
        node.height = 1 + maxHeight(getHeight(node.left), 
                                    getHeight(node.right));
        // Get balance factor of a node
        int factor = getBalanceFactor(node);
        // LL Case
        if (factor > 1 && data < node.left.data)
        {
            return rightRotate(node);
        }
        // RR Case 
        if (factor < -1 && data > node.right.data)
        {
            return leftRotate(node);
        }
        // LL Case
        if (factor > 1 && data > node.left.data)
        {
            node.left = leftRotate(node.left);
            return rightRotate(node);
        }
        // RR Case 
        if (factor < -1 && data < node.right.data)
        {
            node.right = rightRotate(node.right);
            return leftRotate(node);
        }
        return node;
    }
    // Print the tree in preorder form
    public void preorder(TreeNode node)
    {
        if (node != null)
        {
            System.out.print("  " + node.data);
            preorder(node.left);
            preorder(node.right);
        }
    }
    // Print the tree in inorder form
    public void inorder(TreeNode node)
    {
        if (node != null)
        {
            inorder(node.left);
            System.out.print("  " + node.data);
            inorder(node.right);
        }
    }
    // Print the tree in postorder form
    public void postorder(TreeNode node)
    {
        if (node != null)
        {
            postorder(node.left);
            postorder(node.right);
            System.out.print("  " + node.data );
        }
    }
    public static void main(String[] args)
    {
        AvlTree tree = new AvlTree();
        // Add tree node
        tree.root = tree.addNode(tree.root, 4);
        tree.root = tree.addNode(tree.root, 7);
        tree.root = tree.addNode(tree.root, 5);
        tree.root = tree.addNode(tree.root, 19);
        tree.root = tree.addNode(tree.root, 17);
        tree.root = tree.addNode(tree.root, 13);
        tree.root = tree.addNode(tree.root, 11);
        tree.root = tree.addNode(tree.root, 3);
        tree.root = tree.addNode(tree.root, 2);
        tree.root = tree.addNode(tree.root, -3);
        /*
          Resultant  AVL Tree
          -----------------
                 7
                /  \ 
               /    \
              4      17
             / \     / \
            2   5  13  19
           / \     /
         -3   3   11


        */
        System.out.print("Resultant AVL Tree");
        System.out.print("\nPreorder  :");
        tree.preorder(tree.root);
        System.out.print("\nInorder   :");
        tree.inorder(tree.root);
        System.out.print("\nPostorder :");
        tree.postorder(tree.root);
    }
}

Output

Resultant AVL Tree
Preorder  :  7  4  2  -3  3  5  17  13  11  19
Inorder   :  -3  2  3  4  5  7  11  13  17  19
Postorder :  -3  3  2  5  4  11  13  19  17  7


Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment







© 2021, kalkicode.com, All rights reserved