- Amortization Results for Chromatic Search Trees, with an Application to Priority Queues.
- Joan Boyar, Rolf Fagerberg, and Kim S. Larsen.
In 4th International Workshop on Algorithms and Data Structures (WADS), volume 955 of Lecture Notes in Computer Science, pages 270-281. Springer, 1995.
The intention in designing data structures with relaxed balance, such as
chromatic search trees, is to facilitate fast updating on shared-memory
asynchronous parallel architectures.
To obtain this, the updating and rebalancing have been uncoupled,
so extensive locking in connection with updates is avoided.
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 in previous
proposals can be implemented.
- Link to the publication at the publisher's site - subscription may be required.
Text required by the publisher (if any):
The final publication is available at link.springer.com.
Link to the journal version containing all the material and proofs, some of which are usually omitted in the conference version due to space constraints.
Other publications by the author.