Re:C++ Programming Questions to Ask on Interview (2017)
by jstimpfle on Friday October 19, 2018 @03:06AM
(#18254709)
I was wondering the same, and was thinking that maybe the RB needs to touch fewer nodes to rebalance after a remove operaiton, thus resulting in better cache friendliness (although GP said cache _locality_)? But it seems unlikely since the heap property is much weaker than the RB-balanced binary tree property.
[ Parent
| on HN ]
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.
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.
Re:C++ Programming Questions to Ask on Interview (2017)
by SamReidHughes on Friday October 19, 2018 @05:13PM
(#18260115)
A heap tree has a very specific structure, even if value locations have some flexibility. An RB-tree has more flexibility in its structure, with rigidity in value locations.