Space-efficient finger search on degree-balanced search trees

Abstract

An extended abstract of this paper has appeared in ACM-SIAM Symposium on Discrete Algorithms (SODA) 2003. This paper was last revised on April 15, 2003. We show how to support the finger search operation on degree-balanced search trees in a spaceefficient manner that retains a worst-case time bound of O(log d), where d is the difference in rank between successive search targets. While most existing tree-based designs allocate linear extra storage in the nodes (e.g., for side links and parent pointers), our design maintains a compact auxiliary 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 auxiliary 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.