skip-list

Here are some of the differences Skiplist Binary tree Concurrency - Skip lists are more amenable to concurrent access/modification. Inserting a node into a skip list is far more localized, only nodes directly linked to the affected node need to be locked. pressure. The most frequently used implementation of a binary search tree is a red-black tree. The concurrent problems come in when the tree is modified it often needs to rebalance. [Read More]

Goal To understand skiplist. Definition Skiplist is a dynamic search structure, as it is dynamic when it comes to insertion and deletion, which supports search). Other dynamic search structure: Treaps Red black tree B-Trees (2-3 trees etc) Operations on skiplist Search - O(log n) Insert - O(log n) Delete - O(log n) These operations are with high probability, 1/polynomial depending on polynomial number of operation. [Read More]