Here is a list of some data-structures assignments done by me...

red black tree - a very efficient balanced binary search tree.
digital tree - a digital search tree (i forgot the details... :) )
avl tree - a balanced binary search tree. The rotation operations used here for balancing the tree are quite costly.
heap - a linked implementation of heap.
2-3 tree - a 2-3 balanced search tree.
sparse matrix - a very efficient implementation of sparse matrix multiplication.