Hacker News Reader

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.

View on HN

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.

Reply on news.ycombinator.com