Lesson 8.3: AVL Insert/Remove
Class Meeting:
Section | Slides | Annotated Slides | Video |
12–1PM | 8.3-avl-insert-remove-203-1221.pdf Download 8.3-avl-insert-remove-203-1221.pdf | PDF Download PDF |
On Zoom Cloud Recordings |
1–2PM | 8.3-avl-insert-remove-203-1221.pdf
Download 8.3-avl-insert-remove-203-1221.pdf (Geoff guest-lecturing; thanks from Steve!) |
PDF Download PDF |
On Zoom Cloud Recordings |
4–5PM | Using Geoff's slides above. Thanks, Geoff! |
8.3-avl-insert-remove-gctien-4pm-annotated.pdf Download 8.3-avl-insert-remove-gctien-4pm-annotated.pdf |
On Zoom Cloud Recordings |
Readings:
- Carrano & Henry : Chapter 21.2.5 (B-Trees)
Summary:
Find in an AVL tree is nothing new; it's just find in a BST! We learn to use small, local tree rotations organized carefully into algorithms for maintaining our AVL balance invariant during insertion and removal operations. Then, we very briefly explore more of the enormous set of balanced trees out there. Finally, we think hard about disk accesses to understand why we might want more out of our trees. (You might also want to think about things like distributed network storage/access or parallel processing in similar ways!)
Learning Outcomes:
- Apply, implement, and justify the insertion and removal algorithms for AVL trees that maintain both their search tree and balance properties efficiently.
-
Motivate "out of core" data structures, specifically B-Trees.