3 ms·
Zip trees are great! For a project I made a version that uses the memory location of the entries to construct the (random) rank on the fly. So it’s a binary t
by jpfr 3y ago
Zip trees are great!
For a project I made a version that uses the memory location of the entries to construct the (random) rank on the fly.
So it’s a binary tree structure that requires the same memory as a linked list (two pointers) only!
https://github.com/open62541/open62541/blob/master/deps/ziptree.h https://github.com/open62541/open62541/blob/master/deps/zipt...
- jstanley 3y agoI don't know anything about zip trees, but I'd think in a common scenario the memory addresses are reasonably consecutive. Would that be a problem? If not, why not just assign consecutive ranks in the first place?
- jpfr 3y agoThe address is scrambled (similar to a random-number generator) to produce the rank. So consecutive locations do not hurt performance.
- hinkley 3y agoThis link seems to be more approachable: https://stackoverflow.com/questions/61944198/what-is-a-zip-tree-and-how-does-it-work https://stackoverflow.com/questions/61944198/what-is-a-zip-t...