Amortization Results for Chromatic Search Trees, with an Application to Priority Queues
✍ Scribed by Joan Boyar; Rolf Fagerberg; Kim S Larsen
- Publisher
- Elsevier Science
- Year
- 1997
- Tongue
- English
- Weight
- 396 KB
- Volume
- 55
- Category
- Article
- ISSN
- 0022-0000
No coin nor oath required. For personal study only.
✦ Synopsis
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 toward 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. ] 1997 Academic Press From the sequential case, it is known that in some cases search tree implementations of priority queues give better performance than heap implementations [12]. In our setting of a shared-memory architecture, it turns out that a variation article no.