# Parallel Dynamic Search

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 ?

-
 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

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.