Localized Search in Sorted Lists

It is well known that every one of the set operations insert, delete and member can be performed in O(log n) steps, where n is the number of elements currently in the set. Here we implement these operations and a move operation for a sorted list with f fingers (points of reference) established on the list. It is shown that these operations can be performed in O(log d) steps, where d is the distance between the corresponding finger and the key involved.

Authors

• S. Rao Kosaraju

Keywords

No keywords are indexed for this paper.