AVL tree

self balancing binary search tree
http://en.wikipedia.org/wiki/Self-balancing_binary_search_tree

AVL tree
http://en.wikipedia.org/wiki/AVL_tree

GNU AVL tree library
http://www.msu.edu/~pfaffben/avl/index.html