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 TREESAVL 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, IUTDEFINATION 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 TREESWHY 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 20AVL TREES::
AVL TREES: 12 8 18 17 5 11 4 12 13 18 20PowerPoint 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 heightPowerPoint 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 ROTATIONSPowerPoint 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 RotationPowerPoint 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 DeletionsPowerPoint 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 13PowerPoint Presentation:
15, 20, 24, 10, 13 , 7, 30, 36, 25 15 20 24 13 10 13 20 24 15 10PowerPoint Presentation:
13 20 24 15 10 7 13 20 24 15 10 7 30 36 15, 20, 24, 10, 13 , 7, 30, 36, 25PowerPoint 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 , 25PowerPoint 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, 25PowerPoint 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 TreePowerPoint Presentation:
Remove 24 from the AVL tree. 13 24 36 20 10 7 25 30 15 13 20 36 15 10 7 25 30 DeletionPowerPoint Presentation:
13 20 36 15 10 7 25 30 13 30 36 10 7 25 15 Remove 20 from the AVL tree. DeletionPowerPoint 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): BalancedThank you All:
T hank you All