written 7.8 years ago by | • modified 7.8 years ago |
Mumbai University > Information Technology > Sem 3 > Data structure and algorithm analysis
Marks: 10M
Year: May 2016
written 7.8 years ago by | • modified 7.8 years ago |
Mumbai University > Information Technology > Sem 3 > Data structure and algorithm analysis
Marks: 10M
Year: May 2016
written 7.8 years ago by |
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.
// creation of AVL Tree
Step 1:
Step 2:
Step 3:
Step 4:
Step 5:
Step 6:
Step 7:
Step 8:
Step 9:
Step 10:
Step 11:
Step 6: insert 6