Technical Report No. 50, February 1994 - Abstract

Jürgen Eckerle, Otto Nurmi:
Concurrent Perfect Balancing of Binary Search Trees

When a balanced data structure is updated and searched concurrently, updating and balancing should be decoupled so as to make updating faster. The balancing is done by special maintenance processes that run concurrently with the search and update tasks. We show that it is not necessary to use a weak balance condition like AVL or red-black condition, since balancing a binary tree perfectly so that the search paths become as short as possible is not much more expensive, that is, a process must lock only 5 nodes at a time even when perfect balance is desired. In contrast to other algorithms that perfectly balance a binary search tree, our algorithm keeps the tree (weakly) balanced during the further balancing. This is important if the data structure is used by concurrent search and update processes.