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.

We investigate two lowest common ancestors (LCA) problems on trees. We give a linear time algorithm for the off-line problem, on a random access machine (RAM). The half-line problem is one in which LCA queries on a fixed tree are arriving on line. We extend our RAM algorithm to answer each individual query in 0(1) time, with 0(n) preprocessing time. Tarjan observed that this result helps to explicate the difference in power between RAM and pointer machines. We also show how to modify our algorithm to achieve a linear preprocessing time, optimal query time, algorithm on a reference machine.

A finger is a point in a file near which updates and searches can be conducted particularly efficiently. We present a data structure which supports insertions, deletions, searches, and approximate range queries. In each case both a finger f and a key k are specified as arguments to the appropriate algorithm. The total time bound for n updates (insertion or deletions) in an initiallly empty data structure is the sum over all updates of 0(log d+log*n), where d is the linear distance (i.e., the distance in the linear list being represented) from f to k. By an approximate range query, we mean a query of the form "How many keys lie between the finger f and the key k?", where a predetermined percentage of error is allowed in the number returned. The time for each individual search or range query is 0(log d).