Over the weekend, I have done a more comprehensive benchmark of various libraries on search trees. Two AVL, seven red-black tree, one Splay tree, two treap implementations are involved, together with seven hash table libraries. As I need to present a big table, I have to write it in a free-style HTML page. You can find the complete benchmark here and all the source codes here. I only copy the “concluding remarks” in the benchmark page as follows:
- Hash table is preferred over search trees if we do not require order.
- In applications similar to my example, B-tree is better than most of binary search trees in terms of both speed and memory.
- AVL tree and red-black tree are the best general-purposed BSTs. They are very close in efficiency.
- For pure C libraries, using macros is usually more efficient than using void* to achieve generic programming.
You can find the result and much more discussions in that page. If you think the source codes or the design of benchmark can be improved, please leave comments here or send me E-mail. In addition, I failed to use several libraries and so you can see some blank in the table. I would also appreciate if someone could show me how to use those libraries correctly.
Attractive Chaos 
Give the Comparative study between AVL tree, BInary Search Tree and B-Tree of order 2.
it r broket