AVL TREES
AVL Trees abbreviated as Adelson-Velski and Landis Tree, named
after its inventors are self-balancing binary search tree. In this, the
height of left and right subtrees cannot be more than one for all
nodes. If it exceeds by 1 , rebalancing is performed through
rotations.
For example:-
The above given tree is an AVL tree as it follows the following
property:-
1. It should follow all the rules of Binary Search Tree.
2. The height of nodes should be balanced i.e. should be in
between -1 to 1(-1,0,1).
Formula for calculating the height of tree = H(r)-H(l)
H(r) = Height of right node.
H(l) = Height of left node.
Balance Factor:- h(r)-h(l)
The value of balancing factor should be -1,0,1.
How to check whether the given tree is AVL or not?
1. The height of leaf node is 0.
, 2. If a subtree is like the given figure, the height will be
If this occurs the tree is balanced and is an AVL Tree.
3. It the given situation occurs then also the tree is an AVL tree.
What if the given tree is not an AVL tree and needs to be
rebalanced and made out to an AVL Trees?
If this situation occurs, we need to perform certain rotations so
that the tree balances and transforms to an AVL tree only if the
given tree follows the criteria of Binary Search Tree. The
rotations are as follows:-
1. Left Rotations
2. Right Rotations
Left Rotations:-
AVL Trees abbreviated as Adelson-Velski and Landis Tree, named
after its inventors are self-balancing binary search tree. In this, the
height of left and right subtrees cannot be more than one for all
nodes. If it exceeds by 1 , rebalancing is performed through
rotations.
For example:-
The above given tree is an AVL tree as it follows the following
property:-
1. It should follow all the rules of Binary Search Tree.
2. The height of nodes should be balanced i.e. should be in
between -1 to 1(-1,0,1).
Formula for calculating the height of tree = H(r)-H(l)
H(r) = Height of right node.
H(l) = Height of left node.
Balance Factor:- h(r)-h(l)
The value of balancing factor should be -1,0,1.
How to check whether the given tree is AVL or not?
1. The height of leaf node is 0.
, 2. If a subtree is like the given figure, the height will be
If this occurs the tree is balanced and is an AVL Tree.
3. It the given situation occurs then also the tree is an AVL tree.
What if the given tree is not an AVL tree and needs to be
rebalanced and made out to an AVL Trees?
If this situation occurs, we need to perform certain rotations so
that the tree balances and transforms to an AVL tree only if the
given tree follows the criteria of Binary Search Tree. The
rotations are as follows:-
1. Left Rotations
2. Right Rotations
Left Rotations:-
