AVL TREE PREPARED BY M V BRAHMANANDA REDDY
Download as PPT, PDF3 likes1,095 views
The document discusses AVL trees, which are self-balancing binary search trees. It explains that AVL trees ensure that the heights of the left and right subtrees of every node differ by at most one. This balancing property is maintained during insertions and deletions by performing single or double rotations if the balancing factor becomes too large. The document provides examples of insertions that require single or double rotations to rebalance the tree. It also notes some pros and cons of using AVL trees compared to other search tree structures.
More Related Content
What's hot (20)
Similar to AVL TREE PREPARED BY M V BRAHMANANDA REDDY (20)
![4.10.AVLTrees[1].ppt](https://cdn.slidesharecdn.com/ss_thumbnails/4-230506160150-db7bb18c-thumbnail.jpg?width=560&fit=bounds)
More from Malikireddy Bramhananda Reddy (20)
AVL TREE PREPARED BY M V BRAHMANANDA REDDY
- 1. AVL Trees Algorithms and Data Structures M V B REDDY GITAM UNIVERSITY
- 2. Balanced and unbalanced BST 4 2 5 1 3 AVL Trees 2 1 5 2 4 3 7 6 4 2 6 1 3 5 7 Is this balanced?
- 3. Perfect Balance Want a complete tree after every operation tree is full except possibly in the lower right This is expensive For example, insert 2 in the tree on the left and then rebuild as a complete tree Insert 2 & complete tree AVL Trees 3 6 4 9 1 5 8 5 2 8 1 4 6 9
- 4. AVL - Good but not Perfect Balance AVL trees are height-balanced binary search trees Balance factor of a node height(left subtree) - height(right subtree) An AVL tree has balance factor calculated at every node For every node, heights of left and right subtree can differ by no more than 1 Store current heights in each node AVL Trees 4
- 5. Node Heights Tree A (AVL) Tree B (AVL) 1 2 6 1 4 9 0 0 0 1 5 8 height of node = h balance factor = hleft-hright empty height = -1 AVL Trees 5 0 0 height=2 BF=1-0=1 0 6 1 4 9 1 5
- 6. Node Heights after Insert 7 2 3 6 1 4 9 0 0 1 1 5 8 height of node = h balance factor = hleft-hright empty height = -1 AVL Trees 6 1 0 2 0 6 1 4 9 1 5 07 07 balance factor 1-(-1) = 2 -1 Tree A (AVL) Tree B (not AVL)
- 7. Insert and Rotation in AVL Trees Insert operation may cause balance factor to become 2 or 2 for some node only nodes on the path from insertion point to root node have possibly changed in height So after the Insert, go back up to the root node by node, updating heights If a new balance factor (the difference hleft-hright) is 2 or 2, adjust tree by rotation around the node AVL Trees 7
- 8. Single Rotation in an AVL Tree 1 AVL Trees 8 2 2 1 0 0 1 6 4 9 1 5 8 07 0 1 0 2 0 6 4 9 8 1 5 07
- 9. Insertions in AVL Trees Let the node that needs rebalancing be a. There are 4 cases: Outside Cases (require single rotation) : 1. Insertion into left subtree of left child of a. 2. Insertion into right subtree of right child of a. Inside Cases (require double rotation) : 3. Insertion into right subtree of left child of a. 4. Insertion into left subtree of right child of a. The rebalancing is performed through four separate rotation algorithms. AVL Trees 9
- 10. AVL Insertion: Outside Case j AVL Trees 10 k X Y Z Consider a valid AVL subtree h h h
- 11. AVL Insertion: Outside Case j AVL Trees 11 k X Y Z Inserting into X destroys the AVL property at node j h h+1 h
- 12. AVL Insertion: Outside Case j Do a right rotation AVL Trees 12 k X Y Z h h+1 h
- 13. Single right rotation j Do a right rotation AVL Trees 13 k X Y Z h h+1 h
- 14. Outside Case Completed j Right rotation done! (Left rotation is mirror symmetric) h AVL Trees 14 k X Y Z AVL property has been restored! h+1 h
- 15. AVL Insertion: Inside Case j AVL Trees 15 k X Y Z Consider a valid AVL subtree h h h
- 16. AVL Insertion: Inside Case Does right rotation restore balance? AVL Trees 16 Inserting into Y destroys the AVL property at node j j k X Y Z h h h+1
- 17. AVL Insertion: Inside Case j Right rotation does not restore balance now k is out of balance h+1 h AVL Trees 17 k X Y Z h
- 18. AVL Insertion: Inside Case Consider the structure of subtree Y j AVL Trees 18 k X Y Z h h h+1
- 19. AVL Insertion: Inside Case j AVL Trees 19 k X V Z W i Y = node i and subtrees V and W h h h+1 h or h-1
- 20. AVL Insertion: Inside Case j AVL Trees 20 k X V Z W i We will do a left-right double rotation . . .
- 21. Double rotation : first rotation j AVL Trees 21 k X V Z W i left rotation complete
- 22. Double rotation : second j AVL Trees 22 k X V Z W i rotation Now do a right rotation
- 23. Double rotation : second rotation k j X V W Z AVL Trees 23 i right rotation complete Balance has been restored h h or h-1 h
- 24. Implementation balance (1,0,-1) key left right No need to keep the height; just the difference in height, i.e. the balance factor; this has to be modified on the path of insertion even if you dont perform rotations Once you have performed a rotation (single or double) you wont need to go back up the tree AVL Trees 24
- 25. Insertion in AVL Trees Insert at the leaf (as for all BST) only nodes on the path from insertion point to root node have possibly changed in height So after the Insert, go back up to the root node by node, updating heights If a new balance factor (the difference hleft-hright) is 2 or 2, adjust tree by rotation around the node AVL Trees 25
- 26. Insert in AVL trees Insert(T : reference tree pointer, x : element) : { if T = null then {T := new tree; T.data := x; height := 0; return;} AVL Trees 26 case T.data = x : return ; //Duplicate do nothing T.data > x : Insert(T.left, x); if ((height(T.left)- height(T.right)) = 2){ if (T.left.data > x ) then //outside case T = RotatefromLeft (T); else //inside case T = DoubleRotatefromLeft (T);} T.data < x : Insert(T.right, x); code similar to the left case Endcase T.height := max(height(T.left),height(T.right)) +1; return; }
- 27. Example of Insertions in an AVL Tree 0 AVL Trees 27 1 0 2 20 10 30 25 0 35 Insert 5, 40
- 28. Example of Insertions in an AVL Tree 0 0 1 AVL Trees 28 1 0 2 20 10 30 25 1 35 0 5 20 10 30 25 1 5 35 40 0 0 2 3 Now Insert 45
- 29. Single rotation (outside case) 2 1 0 0 AVL Trees 29 2 0 3 20 10 30 25 1 35 0 5 20 10 30 25 1 5 40 40 0 0 0 1 2 3 45 Imbalance 35 45 Now Insert 34
- 30. Double rotation (inside case) 2 AVL Trees 30 3 0 3 20 10 30 25 1 40 0 5 20 10 35 30 1 5 40 45 0 1 2 3 Imbalance 0 1 45 Insertion of 34 35 34 0 0 1 0 25 34
- 31. AVL Tree Deletion Similar but more complex than insertion Rotations and double rotations needed to rebalance Imbalance may propagate upward so that many rotations may be needed. AVL Trees 31
- 32. Pros and Cons of AVL Trees Arguments for AVL trees: 1. Search is O(log N) since AVL trees are always balanced. 2. Insertion and deletions are also O(logn) 3. The height balancing adds no more than a constant factor to the AVL Trees 32 speed of insertion. Arguments against using AVL trees: 1. Difficult to program & debug; more space for balance factor. 2. Asymptotically faster but rebalancing costs time. 3. Most large searches are done in database systems on disk and use other structures (e.g. B-trees).