Comment by eqvinox

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.