News for hackers. Stuff that matters.

A comment on C++ Programming Questions to Ask on Interview (2017). Parent comment

Re:C++ Programming Questions to Ask on Interview (2017) by AstralStorm on Friday October 19, 2018 @04:29AM (#18255077)
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.

[ Parent | on HN ]
Re:C++ Programming Questions to Ask on Interview (2017) by jstimpfle on Friday October 19, 2018 @06:29AM (#18255605)
> 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.

[ Parent | on HN ]