Skip lists vs. red-black trees as a concurrent ordered map

Java's single-threaded sorted map, TreeMap, is a red-black tree, but its concurrent counterpart, ConcurrentSkipListMap, is a lock-free skip list, and many other lock-free ordered sets follow the same pattern. What property of skip lists is the main reason for that choice?

45 of 46 in Data Structures & Algorithms