Re:What Cannot Be Skipped About the Skiplist: A Survey of Sk...
by bonzini on Saturday March 09, 2024 @05:40PM
(#39655259)
Absolutely 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.
Re:What Cannot Be Skipped About the Skiplist: A Survey of Sk...
by hinkley on Sunday March 10, 2024 @06:23PM
(#39662996)
I 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.
[1] https://rtheunissen.github.io/bst