Space-efficient finger search on degree-balanced search trees

摘要

We show how to support the 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 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.