1. balanced search trees (red/black) junior year (algorithms). heaps freshman year (data structures)

2. red-black, B-trees, heaps

3. yes, all three from scratch, C++

4. also observed existing java applets for first-level understanding

5. two

AVL trees and binary heaps were covered in my freshman year (the class is sophmore year for people without the AP credit). Binary heaps were revisited sophmore year in the junior-level algorithms/data-structures course. In the senior data structures course we covered splay trees, skip lists, b-trees, b+-trees, red-black trees, binomial heaps, and fibonacci heaps. We also covered kd-trees (Bentley-style), quadtrees, PR quadtreees, and PM quadtrees.

Proper coverage of amoritized analysis (splay trees, skip lists, binomial heaps, and fibonacci heaps) isn't done until the first-year grad algorithms course. The geometric analysis of the spatial data structures is reserved for the computational geometry and GIS courses (both grad level).

Stuff implemented: AVL trees, binary heaps, PR quadtreees, PM quadtrees, b+-trees, fibonacci heaps. I also did the really painful implementation of an AVL tree and doubly-linked list combined data structure. The only thing done with existing code was using maps in C++/Java, which are red-black trees in libstdc++ and Sun JVM.

I'm still irritated that the C++ STL spec mandates binary heap implementation of the priority_queue class.