Binary search trees provide O(lg n) performance on average for important operations such as item insertion, deletion, and search operations. Balanced trees provide O(lg n) even in the worst case.

GNU libavl is the most complete, well-documented collection of binary search tree and balanced tree library routines anywhere. It supports these kinds of trees:


Plain binary trees:
o Binary search trees
o AVL trees
o Red-black trees

Threaded binary trees:
o Threaded binary search trees
o Threaded AVL trees
o Threaded red-black trees

Right-threaded binary trees:
o Right-threaded binary search trees
o Right-threaded AVL trees
o Right-threaded red-black trees

Binary trees with parent pointers:
o Binary search trees with parent pointers
o AVL trees with parent pointers
o Red-black trees with parent pointers