Space-Efficient Finger Search on Degree-Balanced Search Trees*

We show how to support he finger search operation on degree-balanced search trees in a space-efficient manner that retains a worst-case time bound of O(log d), where d is the difference in rank between successive search tar-gets. While most existing tree-based esigns allocate linear extra storage in the nodes (e.g., for side links and parent pointers), our design maintains a compact auxil-iary data structure called the "hand " during the lifetime of the tree and imposes no other storage requirement within the tree. The hand requires O(log n) space for an n-node tree and has a relatively simple structure. It can be updated synchronously during insertions and deletions with time proportional to the number of structural changes in the tree. The mLxiliary nature of the hand also makes it possible to introduce finger searches into any existing implementation without modifying the underlying data representation (e.g., any implementation of Red-Black trees can be used). Together these factors make finger searches more appealing in practice. Our design also yields a simple yet optimal in-order walk algorithm with worst-case O(1) work per increment (again without any extra storage requirement in the nodes), and we believe our algorithm can be used in database applications when the overall performance is very sensitive to retrieval latency. 1 In t roduct ion The problem of maintaining a sorted list of unique, totally-ordered elements is ubiquitous in computer sci-ence. When efficient element access (insert, delete, or search) is needed, one of the most common solutions is to use some form of balanced search trees to represent the list. Over the years many forms of balanced search trees have been devised, analyzed and implemented. Balanced search trees are very versatile representa