In this paper, we prove that only an amortized constant amount of rebalancing is necessary after an update in a chromatic search tree. We also prove that the amount of rebalancing done at any particular level decreases exponentially, going from the leaves towards the root. These results imply that, in principle, a linear number of processes can access the tree simultaneously.
We have included one interesting application of chromatic trees. Based on these trees, a priority queue with possibilities for a greater degree of parallelism than previous proposals can be implemented.
The publication is available from ScienceDirect (subscription may be required).
Other publications by the author.