PowerPoint Presentation: ISLAMIC UNIVERSITY OF TECHNOLOGY (IUT) Data Structure and Algorithms CSE - 4587 Dhaka,Bangladesh Department of Technical and Vocational Education with Specialization of Computer Science and Engineering Presented By: Md. Abul Hasan B.TECH(CSE)
PowerPoint Presentation: PRESENTATION ON AVL TREES
AVL TREES:: AVL TREES: Defination of AVL trees Why AVL Trees? Properties of AVL trees Construct of AVL trees Insertion and Deletion M.A Hasan, B.Sc.TE -CSE -3 rd Semester, IUT
DEFINATION OF AVL TREES: An AVL tree is another balanced binary search tree AVL Trees = A delson- V elskii and L andis trees comes from its inventors described in 1962 for the organization of information.“ Example: 12 8 18 17 5 11 4 DEFINATION OF AVL TREES
WHY AVL TREES?: When sorted elements inserted into BST than it becomes as degenarated tree Which is insufficient After insertion/deletion its height will be increase And also can be imbalanced That is ensure AVL trees! WHY AVL TREES? 12 13 18 20
AVL TREES:: AVL TREES: 12 8 18 17 5 11 4 12 13 18 20
PowerPoint Presentation: Sub-trees of each node can differ by at most 1 in their height So, h=max(l.h-r.h)+1 h=Height l=left, r=Right PROPERTIES OF AVL TREES:
PowerPoint Presentation: By default, leaf height =0. And empty sub-trees have a Height of -1. 55 32 71 64 86 Height 0 Height 1 Height 2 Height 0 sub-tree L has a height of 0 sub-tree R has a height of 1 Height = max( L .height, R .height) + 1 Height = 0 = max(-1,-1) + 1 Calculate the height
PowerPoint Presentation: YES H=3-2 =1 NO H=4-2 =2 12 8 18 17 5 11 4 7 2 12 8 18 17 5 11 4 Left Sub Tree h=3 Right Sub Tree, h=2 AVL TREES:
PowerPoint Presentation: Rotations are to rearrange nodes to maintain AVLness. They are needed on insert and delete. ROTATIONS:
PowerPoint Presentation: There are four of them Single Left (LL) and Single Right (RR) Double Left (LR) and Double Right (RL) The names describe which way the node moves. For example, a left rotation moves the node down and left. Nodes always move down when rotated. NAME OF ROTATIONS
PowerPoint Presentation: A LR double rotation is to rotate something to the left, and then its former parent to the right. A RL double rotation is to rotate something to the right, and then its former parent to the left. Double Rotation
PowerPoint Presentation: It is performed as in binary search trees After insertion or del if it will be imbalanced, Than we need rotation to correct balance Single Rotation Double Rotation, Both can be Left/Right rotation. For insertions, one rotation is sufficient For deletions, may needed double Insertion and Deletions
PowerPoint Presentation: Now we build an AVL tree: 15, 20, 24 , 10, 13, 7, 30, 36, 25 Construct of AVL Trees: 15 20 24 15 20 24 10 13
PowerPoint Presentation: 15, 20, 24, 10, 13 , 7, 30, 36, 25 15 20 24 13 10 13 20 24 15 10
PowerPoint Presentation: 13 20 24 15 10 7 13 20 24 15 10 7 30 36 15, 20, 24, 10, 13 , 7, 30, 36, 25
PowerPoint Presentation: 13 20 30 15 10 7 36 24 25 13 20 30 15 10 7 36 24 15, 20, 24, 10, 13, 7, 30, 36 , 25
PowerPoint Presentation: 13 24 36 20 10 7 25 30 15 13 20 30 15 10 7 36 24 25 15, 20, 24, 10, 13, 7, 30, 36, 25
PowerPoint Presentation: Removing a node from an AVL Tree is the same as removing from a binary search tree. However, it may unbalance the tree. Similar to insertion, starting from the removed node we check all the nodes in the path up to the root for the first unbalance node. Use the appropriate single or double rotation to balance the tree. May need to continue searching for unbalanced nodes all the way to the root. Remove Operation in AVL Tree
PowerPoint Presentation: Remove 24 from the AVL tree. 13 24 36 20 10 7 25 30 15 13 20 36 15 10 7 25 30 Deletion
PowerPoint Presentation: 13 20 36 15 10 7 25 30 13 30 36 10 7 25 15 Remove 20 from the AVL tree. Deletion
PowerPoint Presentation: 13 15 36 10 7 25 30 13 30 36 10 7 25 15 After Remove 24 and 20 from the AVL tree. Deletion Fig (a):Unbalanced Fig(b): Balanced
Thank you All: T hank you All