3 ms·
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 ef
by 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 agoWhile 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.