1
45kviews
What is AVL Tree? Construct the AVL tree for the following set of data: 1,2,3,4,8,7,6,5,11,10,12

Mumbai University > Information Technology > Sem 3 > Data structure and algorithm analysis

Marks: 10M

Year: Dec 2015

1 Answer
1
5.4kviews

AVL Tree: An AVL tree is a binary search tree in which the heights of the left and right subtrees of the root differ by at most 1 and in which the left and right subtrees are again AVL trees. An AVL Tree is a form of binary tree, however unlike a binary tree, the worst case scenario for a search is O(log n). The AVL data structure achieves this property by placing restrictions on the difference in height between the sub-trees of a given node, and re-balancing the tree if it violates these restrictions.

// AVL tree construction:

Step 1:

enter image description here

Step 2:

enter image description here

Step 3:

enter image description here

Step 4:

enter image description here

Step 5:

enter image description here

Step 6:

enter image description here

Step 7:

enter image description here

Step 8:

enter image description here

Step 9:

enter image description here

Step 10:

enter image description here

Step 11:

enter image description here

Please log in to add an answer.