9.bst(contd.) avl tree
Download as pptx, pdf0 likes6,658 views
This document discusses balanced binary search trees (BSTs), specifically AVL trees. It begins by explaining that regular BSTs can have heights of O(N) in the worst case, making insertion and deletion operations slow. Balanced BSTs like AVL trees aim to keep the height O(log N) through rebalancing rotations after insertions or deletions. The document then covers AVL tree properties and balancing, the four types of rotations (LL, RR, LR, RL) used to rebalance after insertions, examples of constructing an AVL tree by insertion, and the different rotation types (R0, R1, R-1, L0, L1, L-1) used to rebalance
More Related Content
What's hot (20)
Viewers also liked (7)
Similar to 9.bst(contd.) avl tree (20)
More from Chandan Singh (20)
Recently uploaded (20)
9.bst(contd.) avl tree
- 1. Data Structure and Algorithm (CS-102) Ashok K Turuk
- 2. Consider the insertion of following element A, B, C, , ….,X, Y, Z into the BST A B C X Y Z O(N)
- 3. Consider the insertion of following element Z, X, Y, , ….,C, B, A into the BST Z X Y C B A O(N)
- 4. Balanced binary tree • The disadvantage of a binary search tree is that its height can be as large as N-1 • This means that the time needed to perform insertion and deletion and many other operations can be O(N) in the worst case • We want a tree with small height • A binary tree with N node has height at least (log N) • Thus, our goal is to keep the height of a binary search tree O(log N) • Such trees are called balanced binary search trees. Examples are AVL tree, red-black tree.
- 5. AVL tree Height of a node • The height of a leaf is 1. The height of a null pointer is zero. • The height of an internal node is the maximum height of its children plus 1
- 6. AVL tree • An AVL tree is a binary search tree in which – for every node in the tree, the height of the left and right subtrees differ by at most 1. – An empty binary tree is an AVL tree
- 7. AVL tree TL left subtree of T h(TL ) Height of the subtree TL TR Right subtree of T h(TR ) Height of the subtree TR T is an AVL tree iff TL and TR are AVL tree and |h(TL ) - h(TR ) | <= 1 h(TL ) - h(TR ) is known as balancing factor (BF) and for an AVL tree the BF of a node can be either 0 , 1, or -1
- 9. Insertion in AVL search Tree Insertion into an AVL search tree may affect the BF of a node, resulting the BST unbalanced. A technique called Rotation is used to restore he balance of the search tree
- 12. Rotation To perform rotation – Identify a specific node A whose BF(A) is neither 0, 1, or -1 and which is the nearest ancestor to the inserted node on the path from the inserted node to the root
- 13. Rotation Rebalancing rotation are classified as LL, LR, RR and RL LL Rotation: Inserted node is in the left sub-tree of left sub-tree of node A RR Rotation: Inserted node is in the right sub-tree of right sub-tree of node A LR Rotation: Inserted node is in the right sub-tree of left sub-tree of node A RL Rotation: Inserted node is in the left sub-tree of right sub-tree of node A
- 14. LL Rotation BL : Left Sub-tree of B BR : Right Sub-tree of B AR : Right Sub-tree of A h : Height A B c AR h BL BR (0) (+1) Insert X into BL A B c AR h BL BR (+1) (+2) h+1 x Unbalanced AVL search tree after insertion
- 15. LL Rotation LL Rotation A AR c h BR (0) B BL (0) h+1 x Balanced AVL search tree after rotation A B c AR h BL BR (+1) (+2) h+1 x Unbalanced AVL search tree after insertion
- 16. LL Rotation Example Insert 36(0) (+1) 96 85 110 64 90 (0) (0) (0) (+1) (+2) 96 85 110 64 90 (0) (0) (+1) 36 Unbalanced AVL search tree (0)
- 17. LL Rotation Example LL Rotation (+1) (+2) 96 85 110 64 90 (0) (0) (+1) 36 Unbalanced VAL search tree (0) 85 110 64 (0) (+1) 96 (0) (0) Balanced AVL search tree after LL rotation (0) 9036(0)
- 18. RR Rotation A B c AL h BL BR (0) (-1) Insert X into BR h A B c BL BR (-1) (-2) h+1 x Unbalanced AVL search tree after insertion AL
- 19. RR Rotation RR Rotation B A c BL BR (0) (0) h+1 x Balanced AVL search tree after Rotation AL A B c BL BR (-1) (-2) h+1 x Unbalanced AVL search tree after insertion AL h
- 20. RR Rotation Example Insert 65(0) (-1) 34 26 44 40 56 (0) (0) (0) (0) (-2) 34 26 44 40 56 (-1) (-1) (0) 65 Unbalanced AVL search tree (0)
- 21. RR Rotation Example RR Rotation (0) (-2) 44 34 56 40 65 (0) (-1) (0) 26 Balanced AVL search tree after RR rotation (0) (0) (-2) 34 26 44 40 56 (-1) (-1) (0) 65 (0)
- 22. LR Rotation Insert X into CL B C c BL CL CR (0) (-1) h B C c CL CR (-1) (-1) x Unbalanced AVL search tree after insertion BL A h A(+1) AR (+2) AR
- 23. LR Rotation LR Rotation B C c BL CL CR (-1) (-1) h B A c CL CR (-1) (0) x Balanced AVL search tree after LR Rotation BL A h C(+2) AR (0) AR x
- 24. LR Rotation Example Insert 37(0) (+1) 44 30 76 16 39 (0) (0) (0) (-1) (+2) 44 30 76 16 39 (+1) (0) (+1) 37 Unbalanced AVL search tree (0)
- 25. LR Rotation Example LR Rotation(-1) (+2) 44 30 76 16 39 (+1) (0) (0) (0) (0) 39 30 44 16 37 (0) (-1) (0) 76 Balanced AVL search tree (0) 37 (0)
- 26. RL Rotation Insert X into CR h B C cAL CL CR (0) (0) h A (-1) BR h B C cAL CL CR (-1) (+1) h A (-2) x Unbalanced AVL search tree after insertion BR
- 27. RL Rotation RL Rotation h B C cAL CL CR (-1) (+1) h A (-2) BR x Balanced AVL search tree after RL Rotation x h B A c AL CL CR (+1) (0) h C (0) BR
- 28. RL Rotation Example Insert 41(0) (-1) 34 26 44 40 56 (0) (0) (0) (0) (-2) 34 26 44 40 56 (0) (+1) (-1) 41 Unbalanced AVL search tree (0)
- 29. RL Rotation Example RL Rotation(0) (-2) 34 26 44 40 56 (0) (+1) (-1) (0) (0) (+1) (0) 40 34 44 41 56 (0) (0) (0) Balanced AVL search tree 26 41
- 30. AVL Tree Construct an AVL search tree by inserting the following elements in the order of their occurrence 64, 1, 14, 26, 13, 110, 98, 85
- 31. Insert 64, 1 Insert 14 64 1 (+1) (0) 14 64 1 (+2) (-1) (0) 64 (0) 14 1 (0) (0) LR
- 32. Insert 26, 13, 110,98 64 14 1 (0) (0) (0) 64 14 1 (-1) (-1) (-1) 98 110 26 13 (+1) (0) (0) (0)
- 34. Deletion in AVL search Tree Deletion in AVL search tree proceed the same way as the deletion in binary search tree However, in the event of imbalance due to deletion, one or more rotation need to be applied to balance the AVL tree.
- 35. AVL deletion Let A be the closest ancestor node on the path from X (deleted node) to the root with a balancing factor +2 or -2 Classify the rotation as L or R depending on whether the deletion occurred on the left or right subtree of A
- 36. AVL Deletion Depending on the value of BF(B) where B is the root of the left or right subtree of A, the R or L imbalance is further classified as R0, R1 and R -1 or L0, L1 and L-1.
- 37. R0 Rotation A B c AR h BL BR (0) (+1) Delete node X h x A B c AR h BL BR (0) (+2) Unbalanced AVL search tree after deletion of node x h -1
- 38. R0 Rotation R0 Rotation Balanced AVL search tree after rotation A B c AR h BL BR (0) (+2) Unbalanced AVL search tree after deletion of x A AR c h BR (+1) B BL (-1) BF(B) == 0, use R0 rotation
- 39. R0 Rotation Example Delete 60 Unbalanced AVL search tree after deletion (0) (0) (+1) 46 20 54 18 23 (-1) (-1) (+1) 7(0) (0) 60 24 (0) (+2) 46 20 54 18 23 (-1) (0) (+1) 7(0) (0) 24
- 40. R0 Rotation Example R0 (0) (+2) 46 20 54 18 23 (-1) (0) (+1) 7(0) (0) 24 Balanced AVL search tree after deletion (+1) (-1) 20 18 46 7 23 (-1) (+1) (0) 54 (0) (0) 24
- 41. R1 Rotation A B c AR h -1 BL BR (+1) (+1) Delete node X h x h A B c AR h BL BR (+1) (+2) Unbalanced AVL search tree after deletion of node x h -1 h -1
- 42. R1 Rotation R1 Rotation Balanced AVL search tree after rotation A B c AR h -1 BL BR (+1) (+2) A AR c h-1 BR (0) B BL (0) BF(B) == 1, use R1 rotation h h -1
- 43. R1 Rotation Example Delete 39 Unbalanced AVL search tree after deletion (0) (+1) (+1) 37 26 41 18 28 (0) (+1) (+1) 16(0) 39 (+1) (+2) 37 26 41 18 28 (0) (0) (+1) 16(0)
- 44. R1 Rotation Example R1 Rotation Balanced AVL search tree after deletion (+1) (+2) 37 26 41 18 28 (0) (0) (+1) 16(0) (+1) (0) 26 18 37 16 28 (0) (0) (0) 41 (0)
- 45. R-1 Rotation Delete X B C c BL CL CR (0) (-1) h-1 A h (+1) AR x A B C c CL CR (0) (-1) Unbalanced AVL search tree after deletion BL (+2) AR h-1
- 46. R-1 Rotation R -1 B C c BL CL CR (0) (-1) h-1 A h -1 (+2) AR C B A c CL CR (0) (0) Balanced AVL search tree after Rotation BL (0) AR h -1 h -1 BF(B) == -1, use R-1 rotation
- 47. R-1 Rotation Example Delete 52(-1) (+1) 44 22 48 18 28 (0) (-1) (0) 52 2923 (-1) (+2) 44 22 48 18 28 (0) (0) (0) 23 Unbalanced AVL search tree after deletion (0) 29
- 48. R-1 Rotation Example R-1(-1) (+1) 44 22 48 18 28 (0) (-1) (0) 52 2923 (0) (0) 28 22 4818 23 (0) (0) (0) 44 Balanced AVL search tree after rotation (0) 29
- 49. L0 Rotation A B c AL h BL BR (0) (-1) Delete X h x A B c BL BR (0) (-2) h Unbalanced AVL search tree after deletion AL h-1
- 50. L0 Rotation A B c AL h BL BR (0) (-1) Delete X h -1 B A c BL BR (0) (+1) h Balanced AVL search tree after deletion AL h-1 (-1)
- 51. L1 Rotation A B c AL h-1 CL BR (+1) (-1) Delete X h x C CR h-1 (0) A B c CL BR (+1) (-2) h-1 Unbalanced AVL search tree after deletion AL h-1 C CR (0)
- 52. L1 Rotation A B c AL h-1 CL BR (+1) (-2) L1 h-1 C CR h-1 (0) (0) A C B c CL BR (0) (0) h-1 Unbalanced AVL search tree after deletion AL h-1 CR
- 53. L-1 Rotation A B c AL h BL BR (-1) (-1) Delete X h x h-1 A B c BL BR (-1) (-2) h Unbalanced AVL search tree after deletion AL h-1 h-1
- 54. L-1 Rotation A B c AL h BL BR (-1) (-2) Delete X h-1 B A c BL BR (-1) (0) h Balanced AVL search tree after deletion AL h-1 h-1