Understanding AVL Trees: Operations, Insertion, and Deletion

AVL trees, a type of self-balancing binary search tree, require specific operations for finding, insertion, and deletion. Inserting a node involves checking for imbalance in four possible cases. Various rotations are used to maintain the tree's balance. Deletion can either be lazy or involve balancing the tree after removal. Examples and images demonstrate the process step by step.

• AVL Trees
• Operations
• Insertion
• Deletion
• Balancing

yase Follow

Uploaded on Oct 05, 2024 | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

Presentation Transcript

1. AVL Tree 2014.1.23 Iris Jiaonghong Shi

2. AVL tree operations AVL find: Same as BST find AVL insert: First BST insert, then check balance and potentially fix the AVL tree Four different imbalance cases AVL delete: The easy way is lazy deletion Otherwise, do the deletion as binary search tree and check balance.

3. Insert, summarized Insert as in a BST Check back up path for imbalance, which will be 1 of 4 cases: Node s left-left grandchild is too tall Node s left-right grandchild is too tall Node s right-left grandchild is too tall Node s right-right grandchild is too tall Only one case occurs because tree was balanced before insert After the appropriate single or double rotation, the smallest- unbalanced subtree has the same height as before the insertion So all ancestors are now balanced 3

4. Nodes left-left grandchild is too tall

5. Nodes right-left grandchild is too tall

6. Example: Insert Warm up: 2, 5, 6, 8, 9, 7 Example in the book: 3,2,1,4,5,6,7 16,15,14,13,12,11,10,8,9 An avl applet to play with: http://www.site.uottawa.ca/~stan/csi2514/applet s/avl/BT.html

7. Insert

8. Balance

9. Nodes left-left grandchild is too tall: rotateWithLeftChild

10. Nodes right-left grandchild is too tall: doubleWithLeftChild

11. Remove: BST+balance

12. Example(Cont.) Insert: 3,2,1,4,5,6,7 16,15,14,13,12,11,10,8,9 Delete( assume replace by leftMax) 7,5

13. Q&A Thank you!