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.