If you are a fan of skip lists, you may want to look into treaps as well. "Treap" is a portmanteau of "tree" and "heap": it is a binary search tree with respec

If you are a fan of skip lists, you may want to look into treaps as well. "Treap" is a portmanteau of "tree" and "heap": it is a binary search tree with respect to the search key, and it is a heap in another random or quasi-random quantity such as a hash of the key. Treaps have essentially all the properties of skip lists, and they are even simpler to implement. One way to look at treaps is to start with a skip list. A skip list has variable-size nodes, which is kind of annoying. If you transform the variable-size node into a linked list, you end up with something that is essentially a binary tree, but now you have redundant information in multiple tree nodes. If you remove all redundancy you get the treap. This is not how one usually thinks of treaps, and it is not how they were invented, but it's good to be aware of the correspondence. For a given set of keys and hash function, the treap is effectively unique (unlike binary search trees) irrespective of the insertion order, which is sometimes a good property to have.