BACSE105 - Data Structures and Algorithms
[Link]
Associate Professor, SCOPE
Cabin: AB3 – First Floor, Room No. 111, Cabin 1
Dr.P.Anandan_Associate Professor_SCOPE_VIT Chennai 1
Module:2
Data Structures Linear and Non Linear
Arrays: 1D and 2D array- Stack, Queue - Types of Queue:
Circular Queue, DoubleEnded Queue (deQueue), List:
Singly linked lists, Doubly linked lists, Circular linkedlists.
Binary Tree: Definition and Properties - Tree Traversals-
Binary Search Trees,Application, Balanced Binary Trees-
AVL Tree, Graphs: representation, Traversal:BFS & DFS,
Hashing
Dr.P.Anandan_Associate Professor_SCOPE_VIT Chennai 2
AVL Tree
• While creating BST, height of the tree is not in our hands. It is
based on the order in which keys are inserted.
• The height of BST may be log(n) or n.
• AVL tree is a balanced BST.
• For every node, the height difference between its left and right
subtrees (balance factor) must be -1 / 0 / 1.
Dr.P.Anandan_Associate Professor_SCOPE_VIT Chennai 3
Dr.P.Anandan_Associate Professor_SCOPE_VIT Chennai 4
Dr.P.Anandan_Associate Professor_SCOPE_VIT Chennai 5
Dr.P.Anandan_Associate Professor_SCOPE_VIT Chennai 6
Dr.P.Anandan_Associate Professor_SCOPE_VIT Chennai 7
Dr.P.Anandan_Associate Professor_SCOPE_VIT Chennai 8
Dr.P.Anandan_Associate Professor_SCOPE_VIT Chennai 9
Dr.P.Anandan_Associate Professor_SCOPE_VIT Chennai 10
AVL Tree deletion
Dr.P.Anandan_Associate Professor_SCOPE_VIT Chennai 11
Different cases in AVL deletion
Left heavy
Parent BF LChild [Link] Case Rotation
+2 +1 L 1 (LL) Right
+2 -1 L -1 (LR) Left + Right
+2 0 L 0 Right
Right heavy
Parent BF RChild [Link] Case Rotation
-2 -1 R -1 (RR) Left
-2 +1 R 1 (RL) Right + Left
-2 0 R 0 Left
Dr.P.Anandan_Associate Professor_SCOPE_VIT Chennai 12
Dr.P.Anandan_Associate Professor_SCOPE_VIT Chennai 13
Algorithm for AVL deletion
1. If (root == NULL)
2. return root 25. // Left Heavy Case
26. If (balance > 1)
3. If (key < root → data)
4. root → left = AVL_Delete(root → left, key) 27. If (height(root → left → left) >= height(root → left → right))
28. return RightRotate(root) // L1 or L0
5. Else if (key > root → data)
6. root → right = AVL_Delete(root → right, key) 29. Else
30. root → left = LeftRotate(root → left)
7. Else // Node found 31. return RightRotate(root) // L-1
8. // Case 1 : Node with no child 32. // Right Heavy Case
9. If (root → left == NULL AND root → right == NULL) 33. If (balance < -1)
10. return NULL
34. If (height(root → right → right) >= height(root → right → left))
11. // Case 2 : Node with one child 35. return LeftRotate(root) // R-1 or R0
12. Else if (root → left == NULL)
13. return root → right 36. Else
37. root → right = RightRotate(root → right)
14. Else if (root → right == NULL) 38. return LeftRotate(root) // R1
15. return root → left
39. return root
16. // Case 3 : Node with two children
17. Else
18. successor = Minimum(root → right)
19. root → data = successor → data
20. root → right = AVL_Delete(root → right, successor → data)
Minimum(node)
1. While (node → left != NULL)
21. // Update Height 2. node = node → left
22. root → height = 1 + max( height(root → left), height(root → right) ) 3. return node
23. // Compute Balance Factor
24. balance = height(root → left) − height(root → right)
Dr.P.Anandan_Associate Professor_SCOPE_VIT Chennai 14
Dr.P.Anandan_Associate Professor_SCOPE_VIT Chennai 15
Time complexity of AVL tree
Operation Time Complexity
Search O(log n)
Insertion O(log n)
Deletion O(log n)
Dr.P.Anandan_Associate Professor_SCOPE_VIT Chennai 16