Technical Report No. 90, June 1997 - Abstract

Hanke, Sabine:
Chromatic Search Trees Revisited

Relaxed balancing of search trees was introduced with the aim of speeding up the updates and allowing a high degree of concurrency. In a relaxed version of a search tree the rebalancing operations are uncoupled from the updates and may be delayed. Using local transformations the rebalancing can be performed concurrently with updates and search operations. In this paper we revisit the rebalancing of chromatic trees, a relaxed version of red-black trees. During the rebalancing of a chromatic tree it can occur that the rebalancing operations change the search structure of the tree in order to settle rebalancing requests from the history although the tree is already a balanced red-black tree. We propose how to perform the rebalancing task in such a way that each performed structural change indeed correspond to a real imbalance situation in the tree. The number of rebalancing operations needed to restore the red-black tree balance condition is still O(i+d) pointer changes and O((i+d) * log(n+i)) colour changes, if i insertions and d deletions are applied to a chromatic tree of size n that initially fulfills the balance condition of red-black trees.