AVL stands for Adel’son – Vel’skii and Landis, These two were the Russian mathematician having full names as G.M. Adel’son Vel’skii and E.M. Landis. They both described the property in 1962 about the height balance tree Which was honored as AVL TREE.
As per their theory or property, a height balance tree is a binary tree in which the difference in heights between the left and right subtree is not more than one for every node. And as an honor to these mathematicians, this resulting binary tree is also known as AVL tree.
In order to maintain the height-balanced property in AVL Tree, it is not necessary to know the height of each subtree. We can get by maintaining at each node a balance factor that indicates the difference in heights of the left and right sub-trees.
Each node is a balanced binary tree has a balance of 1, -1, or 0 depending on whether the height of its left subtree is greater than, less than or equal to the height of its right subtree.
A value of 1 indicates that the left child is heavier and there is a path from the root to leaf in the left child subtree of length n, whereas the longest path in the right child subtree is length n-1.
A balancing factor of 0 will indicate that the longest paths in the two-child subtree are equal. A balancing factor of -1 indicates that the right child possesses the longest path.
Fig1 shows a balanced binary tree with a balance factor of each node or an AVL TREE. In a balanced tree, each node must be in one of the three states -1, 0, or 1. If there exists a node in a tree where this is not true, then such a tree is said to be unbalanced. Fig2 shows an unbalanced binary tree.
What is AVL tree full form?
The full form of the AVL tree is Adelson-Velsky and Landis.
What is the height of AVL tree?
If we consider the n node in the AVL tree then the minimum height of the AVL tree is floor(long), and the maximum height of the AVL tree is 1.44*logn.
Inside this blog post, we have seen What is the AVL tree example? Why the AVL tree is used? We have learned that the AVL tree is a self-balancing binary search tree.
In the case of any queries, you can write to us at [email protected] we will get back to you ASAP.
Hope! you would have enjoyed this post about AVL TREE.
Please feel free to give your important feedbacks in the comment section below.
Have a great time! Sayonara!