3 ms·

RB tree nodes abuse the interesting and common property that nodes are created next to each other most of the time in typical usage and are not moved far around

RB tree nodes abuse the interesting and common property that nodes are created next to each other most of the time in typical usage and are not moved far around as in some balancing trees and are small. Thus you end up with cache locality even when not directly aiming at it. B+trees have some of that property by only keeping data in leaves, but you need a very smart leaf layer to capitalize on it. You end up with more inner nodes though.

jstimpfle 8y ago
> RB tree nodes abuse the interesting and common property that nodes are created next to each other most of the time in typical usage That's true only if you create the nodes in already sorted order. Furthermore, for the RB version of priority queues, you need pointers, which are not needed for the array based variant (the childs of cell x are always 2* x and 2* x+1), which typically adds another 16 bytes of data per node.