Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Is there a natural parallel analog to red-black trees with similar or even not-terribly-worse properties for updates while being reasonably work-efficient ?

More generally, what's the best we can do for parallel search with updates ?

share|cite|improve this question
What properties in particular do you wish to preserve or turn "not-terribly-worse"? How important is it that the balance condition is still that of red-black trees? Would expected bounds, as in concurrent skip lists, be acceptable? – jbapple Oct 3 '10 at 15:39
I think expected bounds would be fine. This is a situation where we're hitting the data structure very often with updated key values, so to be precise, even efficient change-key operations a la fibonacci heaps are fine. Do you have a good ref for concurrent skip lists ? – Suresh Venkat Oct 3 '10 at 19:30
Herlihy & Shavit's book, The Art of Multiprocessor Programming, or "Lock-free linked lists and skip lists" or java.util.concurrent or Practical lock-freedom. Have you considered using a concurrent hash table like a hopscotch hash table? – jbapple Oct 3 '10 at 19:58
Actually no. I am sadly illiterate in concurrent methods. Thanks for the refs. – Suresh Venkat Oct 3 '10 at 20:40
up vote 7 down vote accepted

From what I can tell, strategies involve relaxing balance conditions, then performing rebalancing updates in bursts. Here is a paper from Hanke et al., 1997 [PDF], which I think focuses on their technique of aggregating and resolving update operations so that they can be performed concurrently.

share|cite|improve this answer

I think you may find interesting answer in Okasaki's book Purely Functional Data Structures. In this book, many data structures are shown, such that every updates are not expensive (usually only take a constant or logarithm time).

Let say that "d" is a structure just before the time you must rebalance. In a purely functional data structure you have got persistant data structures, hence you can add $n$ things to "d" and need to rebalance $n$ times. This is why amortized complexity does not work in this setting, and he created other way to obtains good algorithm where every step with updates are non-expensive.

share|cite|improve this answer
I think that, without further modification, purely functional search trees serialize all updates, and thus perform poorly under write contention. – jbapple Oct 3 '10 at 20:48

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.