AVL Trees: Operations, Insertion, and Deletion
AVL Tree
2014.1.23
Iris Jiaonghong Shi
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.
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
Node’s left-left grandchild is too tall
Node’s right-left grandchild is too tall
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
Insert
Balance
Node’s left-left grandchild is too tall:
rotateWithLeftChild
Node’s right-left grandchild is too tall:
doubleWithLeftChild
Remove: BST+balance
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
Q&A
•
Thank you!
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.
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.
E N D
Presentation Transcript
AVL Tree 2014.1.23 Iris Jiaonghong Shi
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.
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
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
Nodes left-left grandchild is too tall: rotateWithLeftChild
Nodes right-left grandchild is too tall: doubleWithLeftChild
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
Q&A Thank you!
