Updated April 4, 2023
Introduction to AVL tree java
AVL tree is also known as a self-balancing binary tree which is used for balancing and calculating the difference between respective heights of left and right subtrees whose result can’t come out as more than one in the entire balanced tree. Binary Search tree operation allows the insertion, deletion, search, max, and min operation which is necessary as part of the AVL tree as well. All these operations are considered costly affairs due to which if the difference between the heights of all BST is maintained then the cost and time complexity associated with it can be maintained.
Syntax:
There is not as such proper syntax but while implementing it in Java AVL tree is considered as a data structure where the syntax is represented as follows:
Class Node_demo
{
int key, height_0;
Node left, right;
Node_demo (int d_1)
{
key = d_1;
height_0 = 1;
}
}
class AVLTree_demo1 {
Node root_0;
int height_0(Node N_1) {
if (N_1== null)
return 0;
return N_1.height;
}Explanation:
In the syntax flow here Class Node_demo contains key, height, and structure which describes the key-value pair where the elements will get stored. Followed by AVL_Tree demo_1 node containing root node and its associated elements with value pairs having a height to be maintained everywhere with values as null.
How does the AVL tree work in java?
- There exists proper flow where AVL tree works in Java and is invented by GM Adelson in 1962.
- AVL tree is defined as a height-balanced binary search tree in which each node is associated with a balance factor that gets calculated by subtracting the height of its right-subtree from that of its left-subtree.
- Tree is called balanced if the balance factor lies between -1 to 1 otherwise the tree will need to be balanced from top to bottom.
- As the balance tree controls the height of the binary search tree then the height comes out to be O(h) whereas there is a provision where it is needed to extend the binary search tree once it gets skewed than in that case it comes out to be (n-1) for its manipulation.
- Once the skewed tree gets limited then in that case it imposes an upper bound on all operations which come out as O (log n) where n is the number of nodes.
- There are ways also to rotate the AVL tree and it happens only in one condition where if the balance factor lies between -1, 1, or 0.
- There are four types of Rotations which are as follows:
- LL Rotations: Node gets inserted if it lies in the left subtree of the tree with node D.
- RR Rotations: Node gets inserted if it lies in the right subtree of the tree with node D.
- LR Rotations: Node gets inserted if it gets inserted in the right subtree of a left subtree with node D.
- RL Rotations: Node gets inserted if it gets inserted in the left subtree of a right subtree with node D.
Where D stands for that node whose height and balance factor lies other than -1, 1, and 0 due to which all these Rotations are required to make them properly in format.
There are many operations that exist and for it, there must have proper rotations with proper analysis for manipulation.
Example: This example demonstrates the AVL tree where the insertion, left and right insertion with a preorder, postorder, and levelorder representation as shown in the output below.
import java. util.LinkedList;
import java.util.Queue;
class Node_8 {
int data_0, height_1;
Node_8 left_nd_0;
Node_8 right_nd_0;
Node_8(int d_2) {
data_0 = d_2;
height_1 = 1;
}
}
public class AVLTree_Demo
{
Node_8 root_0;
int height_1(Node_8 N) {
if (N == null)
return 0;
return N.height_1;
}
int max_2(int a_0, int b_0) {
return (a_0 > b_0) ? a_0 : b_0;
}
Node_8 rightRotation_mode(Node_8 oldRoot_0) {
Node_8 newRoot_0 = oldRoot_0.left_nd_0;
Node_8 temp_0 = newRoot_0.right_nd_0;
newRoot_0.right_nd_0 = oldRoot_0;
oldRoot_0.left_nd_0 = temp_0;
newRoot_0.height_1 = max_2(height_1(newRoot_0.left_nd_0), height_1(newRoot_0.right_nd_0)) + 1;
oldRoot_0.height_1 = max_2(height_1(oldRoot_0.left_nd_0), height_1(oldRoot_0.right_nd_0)) + 1;
return newRoot_0;
}
Node_8 leftRotation_mode(Node_8 oldRoot_0) {
Node_8 newRoot_0 = oldRoot_0.right_nd_0;
Node_8 temp_0 = newRoot_0.left_nd_0;
newRoot_0.left_nd_0 = oldRoot_0;
oldRoot_0.right_nd_0 = temp_0;
newRoot_0.height_1 = max_2(height_1(newRoot_0.left_nd_0), height_1(newRoot_0.right_nd_0)) + 1;
oldRoot_0.height_1=max_2(height_1(oldRoot_0.left_nd_0), height_1(oldRoot_0.right_nd_0)) + 1;
return newRoot_0;
}
int balFactor_c(Node_8 root_0) {
if(root_0 == null)
return 0;
return height_1(root_0.left_nd_0) - height_1(root_0.right_nd_0);
}
Node_8 insert(Node_8 root_0, int data_0) {
if(root_0 == null)
return new Node_8(data_0);
else if(data_0 < root_0.data_0)
root_0.left_nd_0 = insert(root_0.left_nd_0, data_0);
else if(data_0 > root_0.data_0)
root_0.right_nd_0 = insert(root_0.right_nd_0, data_0);
else
return root_0;
root_0.height_1= max_2(height_1(root_0.left_nd_0), height_1(root_0.right_nd_0)) + 1;
int bal = balFactor_c(root_0);
if(bal > 1 && data_0 < root_0.left_nd_0.data_0)
return rightRotation_mode(root_0);
if(bal < -1 && data_0 > root_0.right_nd_0.data_0)
return leftRotation_mode(root_0);
if(bal > 1 && data_0 > root_0.left_nd_0.data_0) {
root_0.left_nd_0 = leftRotation_mode(root_0.left_nd_0);
return rightRotation_mode(root_0);
}
if(bal < -1 && data_0 < root_0.right_nd_0.data_0) {
root_0.right_nd_0 = rightRotation_mode(root_0.right_nd_0);
return leftRotation_mode(root_0);
}
return root_0;
}
void preOrder_traversal(Node_8 node) {
if (node != null) {
System.out.print(node.data_0 + " ");
preOrder_traversal(node.left_nd_0);
preOrder_traversal(node.right_nd_0);
}
}
void levelOrder_traversal(Node_8 root) {
Queue<Node_8> q_1 = new LinkedList<Node_8>();
q_1.add(root);
while(!q_1.isEmpty()) {
Node_8 current = q_1.peek();
System.out.print(current.data_0 + " ");
if(current.left_nd_0 != null)
q_1.add(current.left_nd_0);
if(current.right_nd_0 != null)
q_1.add(current.right_nd_0);
q_1.poll();
}
}
public static void main (String args[]) {
AVLTree_Demo tree = new AVLTree_Demo ();
tree. root_0 = tree.insert(tree.root_0, 15);
tree.root_0 = tree.insert(tree.root_0, 20);
tree.root_0 = tree.insert(tree.root_0, 19);
tree.root_0 = tree.insert(tree.root_0, 40);
tree.root_0 = tree.insert(tree.root_0, 50);
tree.root_0 = tree.insert(tree.root_0, 25);
System.out.println("order_of_Preorder_traversal_representation : ");
tree.preOrder_traversal(tree.root_0);
System.out.println();
System.out.println("Levelorder_of_traversal_representation : ");
tree.levelOrder_traversal(tree.root_0);
}
}Output:
Explanation: This program performs the insertion of elements in the AVL tree post which there is some order in a way where some checks like whether the list taken is empty or not and then if the AVL tree has rotations to be performed in a pre-order, post-order, or level order format. All elements given automatically takes input and arrange them in proper order.
Conclusion
AVL tree in Java is used as a proper data structure which is liked by many developers as it gives an edge in terms of operations and helps in saving and consuming time-complexity created by a big set of codes. AVL tree has the capability to handle major operations like insertion, deletion, rotation, and removal from the entire subtrees if heights are maintained properly.
Recommended Articles
This is a guide to AVL tree java. Here we discuss How does the AVL tree work in java along with the example and output. You may also have a look at the following articles to learn more –
