AVL TREE

If you have any queries please leave a message here
Your Message
×


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.


Left Rotation


Right Rotation



Left-Right Rotation



Right-Left Rotation





AVL Tree Construction Process

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.



ABOUT US

QuestionSolves.com is an educational website that helps worldwide students in solving computer education related queries.

Also, different software like Visual Studio, SQL Server, Oracle etc. are available to download in different versions.

Moreover, QuestionSolves.com provides solutions to your questions and assignments also.


MORE TOPIC


Windows Command

UNIX Command

IGNOU Assignment Solution

IGNOU Question Paper Solution

Solutions of Different Questions


WHAT WE DO


Website Devlopment

Training

Home Learning

Provide BCA, MCA Projects

Provide Assignment & Question Paper Solution


CONTACT US


Follow Us