Data Structures and Agorithm: DS 17 AVL Tree.pptx

Data Structures and Agorithm: DS 17 AVL Tree.pptx

1. International Islamic University H-10, Islamabad, Pakistan Data Structure Lecture No. 17 AVL Tree Engr . Rashid Farid Chishti http://youtube.com/rfchishti http://sites.google.com/site/chishti Video Lecture

2. BST for 3 4 5 7 9 14 15 16 17 20 Binary Search Tree 3 20 17 16 15 14 9 7 5 4 Linked List!

3. AVL (Adelson- Velskii and Landis) tree. An AVL tree is identical to a Binary Search Tree except height of the left and right subtrees can differ by 0, -1, or 1. height of an empty tree is defined to be (0). AVL Tree An AVL Tree Not an AVL tree Level Level 2 Level 1 Level 3 14 15 4 9 18 16 20 14 15 4 18 16 20

4. The height of a binary tree is the maximum level of its leaves. Balance F actor = height of its left subtree - height of its right subtree . A balance factor is stored at every node. Here , for example, in a balanced tree. Each node has an indicated balance factor of 1, 0, or –1. AVL Tree: Balance Factor Balanced Trees 3 b = 0 h = 1 9 b = 0 h = 1 b = 1 – 1 = 0 h = 2 4 b = 0 – 2 = – 2 h = 3 15 14 b = 2 – 3 = -1 h = 4 b = 0 h = 2 18 14 b = 0 h = 1 15 14 4 b = 0 h = 2 h = 1 b = 0 h = 1 b = 0 14 4 b = 1 h = 2 15 14 b = - 1 h = 2 16 b = 0 h = 1 20 b = 0 h = 1

5. Insertion and removal may change the balance condition of a tree A rotation is required to restore the balance condition There are two types of rotations Left Rotation Right Rotation AVL Tree: Rotations

6. Let U be the nearest imbalanced node to the inserted one Case 1 ( L - L ): Rotate Right Node U Case 2 ( R - R ): Rotate Left Node U Case 3 ( R - L ): Rotate Right then Rotate Left Case 4 ( L - R ): Rotate Left then Rotate Right In cases 1 and 2, use single rotation to restore the tree In cases 2 and 3, use double rot ation to restore the tree AVL Tree: Imbalance

7. Case 1 ( L - L ): AVL Tree: Case 1 ( Left Left ) Rotate as Right Child b = 2-0 = 2 h = 3 h = 1 h = 2 left left 2 3 Inset(3) Inset(2) Inset(1) Rotate Right Node No. 3 1 2 .5 2 .5 h = 1 b = 1 – 1 = 0 h = 2 3 1 h = 1 2 Balance Factor = height of its left subtree - height of its right subtree . h = 2 h = 1 b = 1-2 = -1 h = 3 The height of a binary tree is the maximum level of its leaves.

8. Case 2 ( R - R ): AVL Tree: Case 2 ( Right Right ) b = -2 h = 3 3 h = 2 right right Inset(1) Inset(2) Inset(3) Rotate as Left Child Rotate Left Node No. 1 1.5 1 2 h = 1 Balance Factor = height of its left subtree - height of its right subtree . The height of a binary tree is the maximum level of its leaves. 1 .5 h = 1 b = 1 – 1 = 0 h = 2 3 1 h = 1 2 h = 2 h = 1 b = 2-1 = 1 h = 3

9. Case 3 ( R - L ): AVL Tree: Case 3 ( Right Left ) Step 1 h = 2 h = 1 b = 0 – 2 = -2 h = 3 left right 1 Inset(1) Inset(3) Inset(2) Step 1: Rotate Right Node No. 3 Rotate as Right Child 3 2 .5 2 2 .5 h = 1 1 b = 0 – 2 = -2 h = 3 h = 2 2 right right 3 Balance Factor = height of its left subtree - height of its right subtree . The height of a binary tree is the maximum level of its leaves.

10. Case 3 ( R - L ): AVL Tree: Case 3 ( Right Left ) Step 2 b = 0 – 2 = - 2 h = 3 3 h = 1 h = 2 right right 1 Rotate as Left Child Step 2: Rotate Left Node No. 1 3 h = 1 h = 2 1 b = 1-1 = 0 2 1.5 1.5 2 Balance Factor = height of its left subtree - height of its right subtree . The height of a binary tree is the maximum level of its leaves.

11. Case 4 ( L - R ): AVL Tree: Case 4 ( Left Right ) Step 1 b = 2 – 0 = 2 h = 3 h = 1 h = 2 right left 3 1 Inset(3) Inset(1) Inset(2) Rotate Left Node No. 1 Rotate as Left Child b = 2 - 0 = 2 h = 3 1 h = 1 h = 2 left left 2 3 1.5 2 1.5 Balance Factor = height of its left subtree - height of its right subtree . The height of a binary tree is the maximum level of its leaves.

12. Case 4 ( L - R ): AVL Tree: Case 4 ( Left Right ) Step 2 2 3 h = 1 1 h = 1 b = 1 - 1 = 0 h = 2 Rotate Right Node No. 3 b = 2 - 0 = 2 h = 3 1 h = 1 h = 2 left left 2 Rotate as Right Child 3 Balance Factor = height of its left subtree - height of its right subtree . The height of a binary tree is the maximum level of its leaves. 2 .5 2 .5

13. Insert(3) AVL Tree Building Example 3 h = 1, b = 0

14. Insert(2) AVL Tree Building Example 2 3 h = 2, b = 1 h = 1

15. Insert(1) AVL Tree Building Example 2 1 Case 1: L-L 3 h = 2 h = 1 h = 3, b = 2 – 0 = 2 Case 1: L-L 2 .5 3 1 2 Rotate as Right Child left left 2 3 1 2 .5

16. AVL Tree Building Example 1 2 3 h = 1 h = 1 h = 2 Case 1: L-L 2 .5 3 1 2 Rotate as Right Child left left 2 3 1 2 .5

17. Insert(4) AVL Tree Building Example 1 2 3 4 h = 1 h = 1 h = 2 h = 1 h = 2 h = 3 , b = 1 – 2 = -1

18. Insert(5) AVL Tree Building Example 1 Case 2: R-R 3 2 5 h = 1 h = 2 h = 1 h = 1 h = 2 h = 3 h = 3 , b = 0 – 2 = -2 4 Case 2: R-R 3 Rotate as Left Child 1.5 1 2 1 .5 3 1 2 right right

19. AVL Tree Building Example 1 2 5 3 4 Case 2: R-R 3 Rotate as Left Child 1.5 1 2 2 .5 3 1 2 right right h = 1 h = 1 h = 1 h = 2 h = 3

20. Insert(6) AVL Tree Building Example 1 4 6 Case 2: R-R 5 3 h = 1 h = 3 2 h = 1 h = 1 h = 2 h = 1 h = 2 h = 3 h = 4, b = 1 – 3 = -2 Case 2: R-R 3 Rotate as Left Child 1.5 1 2 2 .5 3 1 2 right right 3

21. AVL Tree Building Example 5 2 6 1 3 4 h = 2 h = 1 h = 1 Case 2: R-R 3 Rotate as Left Child 1.5 1 2 2 .5 3 1 2 right right h = 1 h = 2 h = 3

22. Insert(7) AVL Tree Building Example 5 2 6 4 7 3 1 h = 1 h = 2 h = 1 h = 1 h = 1 h = 2 h = 3 h = 2 h = 3, b = -2 Case 2: R-R Case 2: R-R 3 Rotate as Left Child 1.5 1 2 2 .5 3 1 2 right right

23. AVL Tree Building Example 2 7 6 3 1 4 5 h = 2 h = 1 h = 1 h = 1 Case 2: R-R 3 Rotate as Left Child 1.5 1 2 1 .5 3 1 2 right right h = 1 h = 2 h = 3

24. Insert(16) AVL Tree Building Example 2 7 6 3 1 4 5 16 h = 1 h = 2 h = 1 h = 1 h = 1 h = 1 h = 2 h = 3 h = 2 h = 3, b = 1 - 2 = 1 h = 4, b = 2 – 3 = – 1

25. Insert(15) AVL Tree Building Example 2 7 6 3 1 4 5 16 Case 3: R-L 15 h = 1 h = 1 h = 2 h = 1 h = 1 h = 1 h = 4 h = 3 h = 2 h = 2 h = 3, b = -2 Case 3: R-L 3 1 2 left right 1 3 2

26. AVL Tree Building Example 2 6 3 1 4 5 16 7 15 h = 2 h = 1 h = 1 h = 1 Case 3: R-L 3 1 2 left right 1 3 2 h = 4 h = 1 h = 1 h = 2 h = 3

27. Insert(14) AVL Tree Building Example 2 6 3 1 4 16 15 5 Case 3: R-L 14 h = 2 h = 1 h = 1 h = 1 h = 4 h = 3 7 h = 1 h = 2 h = 1 h = 1 h = 2 h = 3 h = 4 , b = 1 – 3 = – 2 Case 3: R-L 1 2 left right 1 3 2.5 2.5 3 1.5 2 1.5

28. AVL Tree Building Example 2 7 3 1 4 16 14 6 5 15 h = 2 h = 1 h = 1 h = 2 h = 4 h = 3 h = 1 h = 2 Case 3: R-L 1 2 left right 1 3 2.5 2.5 3 1.5 2 1.5 h = 1 h = 1

29. Insert(13) AVL Tree Building Example 2 7 3 4 16 15 6 5 14 13 Case 2 : R-R 1 h = 1 h = 1 h = 1 h = 4, b = 2 – 3 = -1 h = 2 h = 1 h = 1 h = 2 h = 4 h = 3 h = 1 h = 2 h = 2 h = 3 h = 5 , b = 2 – 4 = -2 Case 2: R-R 1 2 3 1.5 right right 1 1.5 3 2

30. AVL Tree Building Example 4 15 7 16 14 13 2 1 3 h = 3 h = 1 h = 1 h = 2 6 5 h = 1 h = 2 h = 2 h = 4 h = 3 h = 1 Case 2: R-R 1 2 3 1.5 right right 1 1.5 3 2 h = 1

31. Insert(12) AVL Tree Building Example 4 15 7 16 14 2 1 3 6 5 12 13 Case 1: L-L h = 3 h = 1 h = 1 h = 1 h = 2 h = 2 h = 1 h = 2 h = 4 h = 3 h = 1 h = 1 h = 2 h = 3, b = 2

32. AVL Tree Building Example 4 15 7 16 13 2 1 3 6 5 12 14 h = 3 h = 1 h = 1 h = 1 h = 2 h = 2 h = 2 h = 4 h = 3 h = 1 h = 1 h = 1

33. Insert(11) AVL Tree Building Example 4 15 7 16 13 2 1 3 6 5 14 12 11 h = 1 Case 1: L-L h = 3 h = 1 h = 1 h = 1 h = 2 h = 2 h = 1 h = 2 h = 4 h = 3 h = 1 h = 1 h = 2 h = 3 h = 4, b = 2

34. AVL Tree Building Example 4 13 7 12 2 1 3 6 5 11 16 15 14 h = 3 h = 1 h = 1 h = 1 h = 2 h = 2 h = 2 h = 4 h = 3 h = 1 h = 2 h = 1 h = 1

35. Insert(10) AVL Tree Building Example 4 13 7 15 12 2 1 3 6 5 14 16 10 11 Case 1: L-L h = 3 h = 1 h = 1 h = 1 h = 2 h = 2 h = 1 h = 2 h = 4 h = 3 h = 1 h = 2 h = 1 h = 1 h = 2 h = 3, b = -2

36. AVL Tree Building Example 4 13 7 15 11 2 1 3 6 5 14 16 10 12 h = 3 h = 1 h = 1 h = 1 h = 2 h = 2 h = 2 h = 4 h = 3 h = 1 h = 2 h = 1 h = 1 h = 1

37. Insert(8) AVL Tree Building Example 4 13 7 15 11 2 1 3 6 5 14 16 12 10 8 h = 3 h = 1 h = 1 h = 1 h = 2 h = 2 h = 1 h = 2 h = 4 h = 3 h = 1 h = 2 h = 2 h = 1 h = 1 h = 1 h = 3 h = 4 h = 5

38. Insert(9) AVL Tree Building Example 4 13 7 15 11 2 1 3 6 5 14 16 12 10 9 8 Case 4: L-R h = 3 h = 1 h = 1 h = 1 h = 2 h = 2 h = 1 h = 3 h = 5 h = 4 h = 1 h = 2 h = 1 h = 1 h = 1 h = 2 h = 2 h = 3, b = 2

39. Insert(9) AVL Tree Building Example 4 13 7 15 11 2 1 3 6 5 14 16 12 9 8 10 h = 3 h = 1 h = 1 h = 1 h = 2 h = 2 h = 1 h = 3 h = 4 h = 3 h = 1 h = 2 h = 1 h = 1 h = 2 h = 1

40. # include < iostream > #include < stdlib.h > using namespace std ; struct Node { int data; Node *left; Node *right; int h; }; // An AVL tree node class AVL_Tree { Node *root; int Max ( int a, int b); int Height (Node* N); Node * New_Node ( int key); Node * Right_Rotate (Node* y); Node * Left_Rotate (Node* x); int Get_Balance (Node* N ); 40 Example 1: Implementation of AVL Tree 1

41. void Pre_Order (Node* node); Node * Insert (Node* node, int key); public : AVL_Tree ( ) {root = NULL;} void Pre_Order ( ); void Insert ( int key); }; // A utility function to get maximum of two integers int AVL_Tree :: Max( int a, int b) { return (a > b)? a : b; } int AVL_Tree :: Height(Node *N) { if (N == NULL) return 0; return N->h; } 41 Example 1: Implementation of AVL Tree 2

42. Node * AVL_Tree :: New_Node ( int key) { Node* node = new Node(); node->data = key; node->left = NULL; node->right = NULL; node->h = 1; // new node is initially added at leaf return (node); } // A utility function to right rotate subtree rooted with y Node* AVL_Tree :: Right_Rotate (Node *y) { Node *x = y->left; Node *T2 = x->right; x- >right = y; y- >left = T2; // Perform rotation y- >h = Max(Height(y->left), Height(y->right)) + 1; // Update heights x->h = Max(Height(x->left), Height(x->right)) + 1; return x; // Return new root } 42 Example 1: Implementation of AVL Tree 3

43. // A utility function to left rotate subtree rooted with x Node* AVL_Tree :: Left_Rotate (Node *x) { Node *y = x->right; Node *T2 = y->left; y- >left = x; x- >right = T2; // Perform rotation // Update heights x->h = Max(Height(x->left), Height(x->right)) + 1; y->h = Max(Height(y->left), Height(y->right)) + 1; return y; // Return new root } // Get Balance factor of node N int AVL_Tree :: Get_Balance (Node *N) { if (N == NULL) return 0; return ( Height(N->left) - Height(N->right) ); } 43 Example 1: Implementation of AVL Tree 4

44. void AVL_Tree :: Insert( int key){ root = Insert(root, key); } // Recursive function to insert a key in the subtree rooted with node // and returns the new root of the subtree. Node* AVL_Tree :: Insert(Node* node, int key) { /* 1. Perform the normal BST insertion */ if (node == NULL) return ( New_Node (key)); if (key < node->data) node->left = Insert(node->left, key); else if (key > node->data) node->right = Insert(node->right, key); else // Equal keys are not allowed in BST return node; /* 2. Update height of this ancestor node */ node->h = 1 + Max(Height(node->left), Height(node->right)); 44 Example 1: Implementation of AVL Tree 5

45. /* 3. Get the balance factor of this ancestor node to check whether this node became unbalanced */ int b = Get_Balance (node); // If this node becomes unbalanced, then there are 4 cases if (b > 1 && key < node->left->data) // Left Left Case return Right_Rotate (node); if (b < -1 && key > node->right->data) // Right Right Case return Left_Rotate (node); if (b > 1 && key > node->left->data) { // Left Right Case node->left = Left_Rotate (node->left); return Right_Rotate (node); } if (b < -1 && key < node->right->data) { // Right Left Case node->right = Right_Rotate (node->right); return Left_Rotate (node); } return node; // return the (unchanged) node pointer } 45 Example 1: Implementation of AVL Tree 6

46. void AVL_Tree :: Pre_Order ( ) { Pre_Order (root ); } // A utility function to print preorder traversal of the tree. void AVL_Tree :: Pre_Order (Node *node) { if (node != NULL) { cout << node->data << " " ; Pre_Order (node->left); Pre_Order (node->right); } } 46 Example 1: Implementation of AVL Tree 7

47. int main() { AVL_Tree atree ; atree.Insert (3 ); atree.Insert (2 ); atree.Insert (1 ); atree.Pre_Order ( ); cout << endl ; atree.Insert (4 ); atree.Pre_Order ( ); cout << endl ; atree.Insert (5 ); atree.Pre_Order ( ); cout << endl ; atree.Insert (6 ); atree.Pre_Order ( ); cout << endl ; atree.Insert (7 ); atree.Pre_Order ( ); cout << endl ; atree.Insert (16 ); atree.Pre_Order ( ); cout << endl ; atree.Insert (15 ); atree.Pre_Order ( ); cout << endl ; atree.Insert (14 ); atree.Pre_Order ( ); cout << endl ; atree.Insert (13 ); atree.Pre_Order ( ); cout << endl ; atree.Insert (12 ); atree.Pre_Order ( ); cout << endl ; atree.Insert (11 ); atree.Pre_Order ( ); cout << endl ; atree.Insert (10 ); atree.Pre_Order ( ); cout << endl ; atree.Insert (8 ); atree.Pre_Order ( ); cout << endl ; atree.Insert (9 ); atree.Pre_Order ( ); cout << endl ; system ( "PAUSE" ); return 0; } 47 Example 1: Implementation of AVL Tree 8