10 ms·
Another interesting data structure related to skiplists but not mentioned here are zip trees: https://arxiv.org/abs/1806.06726 https://arxiv.org/abs/1806.06726
by anfelor 3y ago
Another interesting data structure related to skiplists but not mentioned here are zip trees: https://arxiv.org/abs/1806.06726 https://arxiv.org/abs/1806.06726
The are a tree-based version of skiplists and thus more suited to functional programming / immutable datastructures.
- rtheunissen 3y agoZip trees are novel but their performance (and therefore also skip lists, since they are isomorphic) lacks behind other linked structures like Treaps and especially LBSTs. [1] I personally find skip lists to be overhyped binary search trees in disguise. [1] https://rtheunissen.github.io/bst https://rtheunissen.github.io/bst
- bonzini 3y agoAbsolutely trees in disguise, in fact there are deterministic versions of skip lists that are equivalent to B-trees. An 1-2 skip list (where each pointer to next can skip from 1 to 2 pointers on the level below) is isomorphic to a 2-3 tree.
- hinkley 3y agoI always felt like Pugh was pointedly ignoring the cost of inconsistently sized data structures and felt like more transparency there was necessary. It's been a really long time since I dug into them though so I could be out of date. I'd also like to see better investigations into Treaps balanced not for fairness but for average access time, so that more frequently used values are faster to look up than uncommon values.
- jpfr 3y agoZip 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...