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