# Skip List estimate number of elements less than (or greater than) a value

I am looking for a thread safe data structure where

1. an element can be searched in $O(\log n)$,
2. for any value, $x$, the number of elements greater than (or less than) can be estimated in $O(\log n)$,
3. an element can be inserted in $O(\log n)$, and
4. an element can be removed in $O(\log n)$.

Can a skip list or some modification of it be used? Is there an alternative data structures (Parallel Red-Black Tree for example) that can be used?

• Can you use a more "typical" structure like a normal balanced tree (red-black / AVL / 2-3 / etc) with each subtree annotated with a size? – Curtis F Jul 31 '18 at 17:27
• I could use a red-black tree, but it needs to be thread safe. I believe there are concurrent implementations, but they are not that easy to implement. Do you know of a good reference to a thread safe red black tree implementation? – dan b Jul 31 '18 at 19:36

Based on your comment, it sounds like you would also prefer a solution that is not too difficult to understand or implement.

I would suggest a persistent binary tree as one possible approach. Take any standard balanced tree data structure (e.g., red-black tree, AVL tree, 2-3 tree, etc.). Annotate each node with the size of the subtree under that node. Then, make this data structure persistent. This can be done in a straightforward way using path copying.

Hopefully, the principles behind this kind of data structure should be easy to understand, so if you need to implement it yourself, it shouldn't be too bad to work out how to do it.

• Your approach would not handle insert and removes in O(Log n) as it would need to copy the entire tree for each insert – dan b Aug 8 '18 at 10:47
• @danb only single path from the root to the node is copied. All subtrees that haven’t changed are simply referenced. – Dmitri Urbanowicz Aug 8 '18 at 12:14
• @DmitriUrbanowicz I think I get the idea, although the impact of having to retry in the case of clashes is not clear. What about the other part of the question: can one estimate the size using a skip list? – dan b Aug 8 '18 at 14:29
• @danb, I don't know about skiplists. Sorry. – D.W. Aug 8 '18 at 16:08

It is possible to extend skip lists with so called "width of the link". For each link it says how many elements are skipped by follow this link. From Wikipedia (section Indexable skiplist):

   1                               10
o---> o---------------------------------------------------------> o    Top level
1           3              2                    5
o---> o---------------> o---------> o---------------------------> o    Level 3
1        2        1        2              3              2
o---> o---------> o---> o---------> o---------------> o---------> o    Level 2
1     1     1     1     1     1     1     1     1     1     1
o---> o---> o---> o---> o---> o---> o---> o---> o---> o---> o---> o    Bottom level

Head  1st   2nd   3rd   4th   5th   6th   7th   8th   9th   10th  NIL
Node  Node  Node  Node  Node  Node  Node  Node  Node  Node


These links are easy to update during (non-concurrent) traversals of insert and delete operations. It is as well easy to keep track of total number of skipped elements.

So yes, one can extend skip lists to find the position of the element in the list. But concurrent updates of the counters still might be a problem.

• Seems like this would solve the problem if the concurrent updates is possible – dan b Aug 13 '18 at 14:28