Height-relaxed AVL rebalancing: A unified, fine-grained approach to concurrent dictionaries.

We address the concurrent rebalancing of almost balanced binary search trees (AVL trees). Such a rebalancing may for instance be necessary after successive insertions and deletions of keys. We show that this problem can be studied through the self-reorganization of distributed systems of nodes controlled by local evolution rules in the line of the approach of Dijkstra and Scholten. This yields a much simpler algorithm that the ones previously known. Based on the basic rebalancing framework, we describe algorithms to manage concurrent insertion and deletion of keys. Finally, this approach is used to emulate other well known concurrent AVL algorithms. As a by-product, this solves in a very general setting an old question raised by H.T. Kung and P.L. Lehman: where should rotations take place to rebalance arbitrary search trees? This paper is the extended version of the previous research report RR1997-13Ce rapport présente un algorithme concurrent pour la gestion dynamique d'un arbre binaire de recherche équilibré (arbres AVL). Une série d'insertions et de suppressions de clés dans un tel arbre peut lui donner une forme arbitraire. Nous montrons dans ce papier que le rééquilibrage de la structure peut être vu comme une auto-réorganisation d'un système distribué formé par les noeuds, dirigée par quelques règles d'évolutions locales. Cette approche mène à un algorithme bien plus simple que les solutions précédentes connues. Des règles complémentaires permettent de plus de gérer les insertions et suppressions concurrentes. Ce résultat permet en particulier de répondre à la question posée par H.T. Kung et P.L.Lehman : ``Peut-on effectuer les rotations dans un ordre quelconque pour rééquilibrer un arbre arbitraire ?''. La réponse est : ``Oui''. Ce papier est la version étendue du précédent rapport de recherche RR1997-1