Donald Bren School of Information and Computer Sciences

We show how binary trees of bounded balance can be maintained so that the time to perform each individual update (insertion or deletion) in a tree of n nodes is 0(log*n), once the location of the update is known. This is the first example of a balanced tree scheme in which the time of each individual insertion/deletion is substantially lower than the height of the tree, which is 0(log n). Such a data structure is useful in situations where the search time may be much lower than 0(log n). The main example of such a situation is the framework of data structures which support fingers. In addition to guaranteed time bounds per update, our structure supports arbitrarily many fingers and approximate range queries.