AVL Tree Algorithm in Java

[14592 views]

What is AVL Tree?

A Self-balancing Binary Search Tree (BST) where difference between heights of left and right subtrees can't be more than 1 for all nodes is said to be an AVL Tree in Data Structures.

Below is a simple implementation of AVL tree in Java.

AVLTree.java

import java.util.LinkedList; import java.util.Queue; class Node { int data, height; Node left; Node right; Node(int d) { data = d; height = 1; } } public class AVLTree { Node root; int height(Node N) { if (N == null) return 0; return N.height; } int max(int a, int b) { return (a > b) ? a : b; } Node rightRotation(Node oldRoot) { Node newRoot = oldRoot.left; Node temp = newRoot.right; //rotation newRoot.right = oldRoot; oldRoot.left = temp; //update heights newRoot.height = max(height(newRoot.left), height(newRoot.right)) + 1; oldRoot.height = max(height(oldRoot.left), height(oldRoot.right)) + 1; return newRoot; } Node leftRotation(Node oldRoot) { Node newRoot = oldRoot.right; Node temp = newRoot.left; //rotation newRoot.left = oldRoot; oldRoot.right = temp; //update heights newRoot.height = max(height(newRoot.left), height(newRoot.right)) + 1; oldRoot.height = max(height(oldRoot.left), height(oldRoot.right)) + 1; return newRoot; } int balFactor(Node root) { if(root == null) return 0; return height(root.left) - height(root.right); } //insertion Node insert(Node root, int data) { if(root == null) return new Node(data); else if(data < root.data) root.left = insert(root.left, data); else if(data > root.data) root.right = insert(root.right, data); else return root; //update height root.height = max(height(root.left), height(root.right)) + 1; int bal = balFactor(root); //left of left if(bal > 1 && data < root.left.data) return rightRotation(root); //right of right if(bal < -1 && data > root.right.data) return leftRotation(root); //right of left if(bal > 1 && data > root.left.data) { root.left = leftRotation(root.left); return rightRotation(root); } //left of right if(bal < -1 && data < root.right.data) { root.right = rightRotation(root.right); return leftRotation(root); } return root; } void preOrder(Node node) { //root -> left -> right if (node != null) { System.out.print(node.data + " "); preOrder(node.left); preOrder(node.right); } } void levelOrder(Node root) { //level by level Queue<Node> q = new LinkedList<Node>(); q.add(root); while(!q.isEmpty()) { Node current = q.peek(); System.out.print(current.data + " "); if(current.left != null) q.add(current.left); if(current.right != null) q.add(current.right); q.poll(); } } public static void main(String[] args) { AVLTree tree = new AVLTree(); tree.root = tree.insert(tree.root, 15); tree.root = tree.insert(tree.root, 20); tree.root = tree.insert(tree.root, 19); tree.root = tree.insert(tree.root, 40); tree.root = tree.insert(tree.root, 50); tree.root = tree.insert(tree.root, 25); /* AVL Tree formed 20 / \ 19 40 / / \ 15 25 50 */ System.out.println("Preorder traversal : "); tree.preOrder(tree.root); System.out.println(); System.out.println("Levelorder traversal : "); tree.levelOrder(tree.root); } }