top button
Flag Notify
    Connect to us
      Site Registration

Site Registration

Why would you use a skip list over a binary search tree?

+2 votes
444 views

Guys can someone help me by describing the skip-list and why someone should use it over BST.

posted Nov 11, 2013 by Majula Joshi

Share this question
Facebook Share Button Twitter Share Button LinkedIn Share Button

1 Answer

0 votes

Skip lists are more amenable to concurrent access/modification.

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. The rebalance operation can affect large portions of the tree, which would require a mutex lock on many of the tree nodes. Inserting a node into a skip list is far more localized, only nodes directly linked to the affected node need to be locked.

answer Nov 12, 2013 by Atul Mishra
...