When speaking only of the algorithmic complexity of red-black trees and AVL trees, AVL trees are faster for searching and red-black trees are faster for insertion and deletion. For inserting ordered data, though, AVL trees are faster.
The reason that my benchmarks show AVL trees as superior in speed is that the code for balancing an AVL tree is much simpler than that for a red-black tree. Because red-black trees rebalance in amortized constant time and AVL trees rebalance in near logarithmic time, red-black trees should be better at rebalancing for high numbers. However, for low numbers (actually even numbers in the millions), the amortized constant vs. logarithmic is too close, and the simpler code of the AVL tree wins. I have citations of the facts above as well as a couple of proof and some logic to back up my claims:http://nathanbelue.blogspot.com/2012/05/avl-vs-red-black-conclusion.html That post has yet to be fully reviewed, and I would like to ask a favor of anyone good at data structures: can you check my work, please? I have tested my answers, but I would like everything reviewed by a few people before I go to the next step in my master plan. |
