AVL Tree.pptx

AVL Tree is a Data Structure.

1. Class Roll: 19CSE001 to 19CSE014 AVL TREE

2. TABLE OF CONTENTS Basic Concept of AVL Tree 01 03 02 04 06 08 Rotation in AVL Tree Insertion in AVL Tree Search in AVL Tree AVL Tree Deletion Advantages, Disadvantages & Applications Code in AVL Tree 05 07 Complexities of AVL Tree

3. Basic Concept of AVL Tree 01

4. Introduction to AVL Named after inventors Adelson-Velsky and Landis invented in 1962. Self Balanced Binary Search Tree(Height Balancing of BST) Solve BST’s worst case situation(Left or Right Skewed BST ) BF = (height of left subtree) - (height of right subtree) Uses “Balancing Factor(BF)” for height balancing BF only allows three values those are - 0 , 1 , -1

5. Fig(a): Balanced BST Fig(b): Left skewed BST

6. AVL Tree Rotation 02

7. The tree is defined as a balanced AVL tree when the balance factor of each node is between -1 and 1. On the other hand, when the balance factor is less than -1 or greater than 1, then the tree is known as an unbalanced tree and needs to be balanced to get the perfect AVL tree. Balance Factor- In AVL tree, Balance factor is defined for every node. Balance factor of a node = Height of its left subtree – Height of its right subtree

8. Rotation Operations in AVL Tree Rotation is performed in AVL Tree to turn the unbalanced tree into a balanced tree by performing various rotation operations. In general, there are four types of Rotations in the AVL tree: Left Rotation Right Rotation Left-Right Rotation Right-Left Rotation The first two rotations are known as single rotations , and the next two are known as double rotations .

9. 1. Right Rotation (RR): When a node is inserted into the left subtree or deleted from the left subtree, the AVL tree becomes unbalanced, and we need to balance it using LL rotation. This LL rotation is also known as clockwise rotation applied on edge, which has the highest balance factor.

10. 2. Left Rotation(LR): When a node gets inserted into the right subtree or deleted from the right subtree, the AVL tree becomes unbalanced, and we need to balance it by rotating the node in the anti-clockwise dir ection.

11. 3. Left-Right Rotation(LR): Left-Right Rotation is the combination of RR rotation and LL rotation. At first, RR rotation is performed on the subtree then, LL rotation is performed on the part of the full tree from inserted node to the first node 4. Right-Left Rotation(RL): Right-left Rotation is the combination of LL rotation and RR rotation. In this case, the first LL rotation is performed on the subtree where the change has been made; then, the RR rotation is performed on the part of the full tree from the inserted node to the top of the tree, that is, the first node.

12. 03 AVL Tree Insertion

13. Insertion is performed in the same way as in a binary search tree. The new node is added into AVL tree as the leaf node. The tree can be balanced by applying rotations. Rotation is required only if, the balance factor of any node is disturbed upon inserting the new node, otherwise the rotation is not required. Insertion

14. S teps to follow for insertion Let the newly inserted node be w Perform standard BST insert for w. Starting from w, travel up and find the first unbalanced node. Let z be the first unbalanced node, y be the child of z that comes on the path from w to z and x be the grandchild of z that comes on the path from w to z. Re-balance the tree by performing appropriate rotations on the subtree rooted with z. There can be 4 possible cases that needs to be handled as x, y and z can be arranged in 4 ways. Following are the possible 4 arrangements: y is left child of z and x is left child of y (Left Left Case) y is left child of z and x is right child of y (Left Right Case) y is right child of z and x is right child of y (Right Right Case) y is right child of z and x is left child of y (Right Left Case)

15. Insertion

16. Insertion

17. Insertion

18. Insertion

19. Deletion in AVL Tree 04

20. Source Code Explanation 05

21. After all There has been included a Implementation of Insertion and deletion procedure in C language. The source code link is: https://drive.google.com/file/d/1m7bzOiNRaZtda6jogbD56n1WS7MCp-p9/view?usp=sharing Let’s describe the code from code blocks-

22. Search in AVL Tree 06

23. The search operation in an AVL tree makes it better than binary search tree. The searching time complexity of the AVL tree is only O(log N). Even in the worst-case, time complexity of searching operation in an AVL tree is O(log(N)), where N is the number of nodes of the tree. Because the height of the AVL tree is always balanced with self-balancing capabilities.

24. S teps to follow the search operation: Start from the root node. If the root node is NULL , return false . Check if the current node’s value is equal to the value of the node to be searched. If yes, return true . If the current node’s value is less than searched key then recur to the right subtree. If the current node’s value is greater than searched key then recur to the left subtree. If the searched key is not found, then the key is not present in the tree.

25. Search Operation in AVL Search (11), (61) & (22)

26. Implementation of Function to find a key in the AVL tree: bool AVL_search (struct AVL_withparent* root, int key) { if (root == NULL) // If root is NULL return false; else if (root->key == key) // If found, return true return true; // Recur to the left subtree if the current node's value is greater than key else if (root->key > key) { bool val = AVL_search(root->left, key); return val; } else { bool val = AVL_search(root->right, key); // Otherwise, recur to the right subtree return val; }}

27. Implementation of main to find a key in the AVL tree: int main() { struct AVL_withparent* root; root = NULL; root = Insert(root, NULL, 10); // Function call to insert the nodes root = Insert(root, NULL, 20); root = Insert(root, NULL, 30); root = Insert(root, NULL, 40); bool found = AVL_search(root, 40); // Function call to search for a node if (found) cout << "value found"; else cout << "value not found"; return 0; }

28. Time complexity & Space Complexity 07

29. Time Complexity for Insertion Inserting an element into an AVL tree requires rotations , calculating the balance factor and updating the height after insertion . Time for rotation —> constant time Time for calculating the balance factor —> constant time Traversing the tree for updating height —> O(log n) SO the time complexity of insertion is O(log n).

30. Time Complexity for Search For search operation only need to t raversing the tree Traversing the tree —> O(log n) SO the time complexity for search is O(log n).

31. Time Complexity for Deletion Deleting an element from an AVL tree also requires rotations , calculating the balance factor and updating the height after insertion . Time for rotation —> constant time Time for calculating the balance factor —> constant time Traversing the tree for updating height —> O(log n) S O the time complexity of deletion is O(log n).

32. Space Complexity of AVL O(log n)

33. OPERATION BEST CASE AVERAGE CASE WORST CASE Insert O (log n) O (log n) O (log n) Delete O (log n) O (log n) O (log n) Search O (1) O (log n) O (log n) Traversal O (log n) O (log n) O (log n) BEST CASE AVERAGE CASE WORST CASE O (n) O (n) O (n) Space Complexity: Time Complexity:

34. Advantages, Disadvantages & Application 08

35. Advantages of AVL Tree The height of the AVL tree is always balanced. The height never grows beyond log N, where N is the total number of nodes in the tree. It gives better search time complexity when compared to simple Binary Search trees. AVL trees have self-balancing capabilities.

36. Disa dvantages of AVL Tree AVL trees can be difficult to implement. AVL trees have high constant factors for some operations. Most STL implementations of the ordered associative containers (sets, multisets, maps, and multimaps) use red-black trees instead of AVL trees. Unlike AVL trees, red-black trees require only one restructuring for removal or insertion.

37. Application of AVL Tree In-memory sorts of sets and dictionaries. Database applications in which insertions and deletions are fewer but there are frequent lookups for data required. The applications that require improved searching apart from the database applications. AVL tree is a balanced binary search tree which employees rotation to maintain balance. It has application in storyline games as well. It is use mainly used in corporate sectors where the have to keep the information about the employees working there and their change in shifts.

38. Problem-01: In this problem you are given two type of query Insert an integer to the list. Given an integer x , you're about to find an integer k which represent x's index if the list is sorted in ascending order. Note that in this problem we will use 1-based indexing. As the problem title suggest, this problem intended to be solved using Balanced Binary Search Tree, one of its example is AVL Tree. Input The first line contains an integer Q, which denotes how many queries that follows. The next Q lines will be one of the type queries which follow this format: 1 x means insert x to the list 2 x means find x's index if the list is sorted in ascending order. Output For each query type 2, print a line containing an integer as the answer or print "Data tidak ada" no quotes if the requested number does not exist in the current lis. Link –> https://www.spoj.com/problems/SDITSAVL/

39. Problem-01: Solution typedef struct node { int key; struct node *left; struct node *right; int left_child; int right_child; int height; } node; int solve (node *root, int key) { if (root != NULL) { if (key > root -> key) return root -> left_child + 1 + solve(root -> right, key); else if (key < root -> key) return solve(root -> left, key); else return root -> left_child; } else { flag = 1; return -1; }; } Link–> https://ideone.com/wNBots

40. THANKS