AVL TREE

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 -

• Left Rotation
• Right Rotation
• Left-Right Rotation
• Right-Left Rotation

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.

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

WHAT WE DO

 Follow Us 