Fully dynamic distributed searchtrees can be balanced in Oðlg 2 NÞ time
Fabio Barillari, Enrico Nardelli, Massimo Pepe · 2002
In this paper we consider the dictionary problem in a message-passing distributed environment. We introduce a new version, based on AVL-trees, of distributed searchtrees, the first to be fully scalable, that is, able to both grow and shrink as long as keys are inserted and deleted. We prove that in the worst case a key can be inserted, searched, or deleted with Oðlg 2 NÞ messages. We show that for the introduced distributed search tree this bound is tight. Since the defined structure maintains the relative order of the keys, it can also support queries that refer to the linear order of keys, such as nearest neighbor or range queries. r 2002 Published by Elsevier Science (USA).