3 ms·
One change I'd make to this structure would be to pack all the children of a node together. That way you could find out the list of all children of a node with
by mihaic 3y ago
One change I'd make to this structure would be to pack all the children of a node together. That way you could find out the list of all children of a node with a binary search, and they'd have some cache-friendly properties.
Inserting a child would need a memmove in O(N), but if edits are rare after an initial build it wouldn't be that bad.
- snovv_crash 3y agoYou could also have extra space allocated for where extra data should go. By aggressively rebalancing you should only need to do a full reallocation when the tree is actually getting pretty full.