What Cannot Be Skipped About the Skiplist: A Survey of Skiplists and Their Appl

• bst

  3 39 2.8 HTML

  Exploring the design space of binary search trees

Zip 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

• jdk7u-jdk

  15 519 0.0 Java
  

Skip lists are relatively simple to make lock-free, while lock-free (even unbalanced) binary search trees are an absolute nightmare.

https://github.com/openjdk-mirror/jdk7u-jdk/blob/master/src/...

• WorkOS

  workos.com sponsored

  The modern identity platform for B2B SaaS. The APIs are flexible and easy-to-use, supporting authentication, user identity, and complex enterprise features like SSO and SCIM provisioning.

  

• open62541

  5 2,415 9.8 C

  Open source implementation of OPC UA (OPC Unified Architecture) aka IEC 62541 licensed under Mozilla Public License v2.0

  

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/zipt...

Suggest a related project