Fully Dynamic Search Trees can be Balanced in O(log^2 N) Time

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 search trees, the first to be fully scalable, that is capable 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(log^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 support also queries that refer to the linear order of keys, such as nearest neighbor or range queries.