B-Trees

  • Find, Insert( Mike's notes)
  • Delete (Mike's notes)

    Display:none

    The delete notes are slightly wrong - on page 2 at the top it says to move the value from the sibling to the under-populated node.  This is wrong.  The max from the smaller sibling should be moved up to the shared parent, and the value that was separating the nodes should be moved down to the target node on the next level down.

    Also - double check that this correctly removes stuff from internal nodes.  E.g., we want to remove 200 from an internal node with children that are also internal nodes.  Make sure that the 'replace this with the predecessor / successor' thing works

AVL Trees

Instructor's Handout on AVL trees  (including both Add and Remove)
Instructor notes on AVL tree lecture (including a list of errors in the code)

  • Exercises: Add                          (These are included in the above handout)
  • Exercises: Remove                  (These are included in the above handout)
  • Starter Project for implementing an AVL tree           (Note: this is NOT guaranteed to be "compatible" with the lecture notes)

Other Online resources:

 

 

 

Stuff left for later:

21 Learning C++
(Specifically pointers -
pointers & arrays,
pointer arithmetic,
Linked list with pointers)
  Instructor Slides