An AVL tree is a self-balancing binary search tree and it was the first such data structure to be invented. In an AVL tree the heights of the two child subtrees of any node differ by at most one, therefore it is also known as height balanced tree. Addition and deletion a node in an AVL tree may require the tree to be rebalanced by one or more tree rotations.
The balance factor of a node is the height of its left subtree minus the height of its right subtree. A node with balance factor 1, 0 or -1 is considered balanced. A node with any other balance factor is considered unbalanced and requires rebalancing the tree.
To balance itself, an AVL tree may perform the following four kinds of rotations -
The first two rotations are single rotations and the next two rotations are double rotations.
Constract a AVL Tree for the following numbers - 45 , 40 , 28 , 60 , 82 , 96 , 32
Figure 1 : Insert 45, (Tree is balanced).
Figure 2 : Insert 40, (Tree is balanced).
Figure 3 : Insert 28, (Tree is unbalanced).
Figure 4 : After perform Right Rotation tree is balanced.
Figure 5 : Insert 60, (Tree is balanced).
Figure 6 : Insert 82, (Tree is unbalanced).
Figure 7 : After perform Left Rotation tree is balanced.
Figure 8 : Insert 96, (Tree is unbalanced).
Figure 9 : After perform Right-Left Rotation.
Figure 10 : After perform Left Rotation tree is balanced.
Figure 11 : Insert 32, (Tree is unbalanced).
Figure 12 : After perform Left-Right Rotation tree is balanced.
IGNOU Assignment Solution
IGNOU Question Paper Solution
WHAT WE DO
Provide BCA, MCA Projects
Provide Assignment & Question Paper Solution