3 ms·

I wonder if anyone did a comprehensive benchmark comparing all of these

• eqvinox 6y ago
  There shouldn't be much difference, particularly between the RB and AVL trees. The limiting factor is memory access latency in all cases since the CPU can't effectively prefetch tree node accesses for the next level down.
  • metric10 6y ago
    While both RB and AVL trees grow at O(lg N) height, the constant for AVL trees is smaller. This means that for a large AVL tree it might be 1 or 2 layers shorter than the equivalent RB tree. This comes at the expense of a higher constant for insertion and deletion. In certain contexts saving a node transversal will have a meaningful impact on performance.
• fulafel 6y ago
  These are the most well known tree types in CS and banchmark results are unlikely to differ from what is widely published and written about the algorithms. Benchmark winner would depend on what usage pattern and metric you are interested in. Binary trees are simple, AVL is a bit faster to search and slower to update than RB.
• bcantrill 6y ago
  For whatever it's worth, I did effectively benchmark the illumos AVL implementation against Rust's B-tree implementation[0], though that was certainly not the intent! Benchmarking the relative BSTs would be interesting, but (absent some small cycle count differences in degenerate cases like a single node) one very much expects BST performance to be dominated by memory behavior -- and the memory footprint (and cache behavior) of the relative implementations is much more likely to affect relative performance than other factors. Of course, systems can surprise, so hopefully someone does the experiment! [0] http://dtrace.org/blogs/bmc/2018/09/28/the-relative-performance-of-c-and-rust/ http://dtrace.org/blogs/bmc/2018/09/28/the-relative-performa...