Finger Search Trees:Dynamic Finger Search Trees.

Dynamic Finger Search Trees

A dynamic finger search data structure should in addition to finger searches also support the insertion and deletion of elements at a position given by a finger. This section is devoted to an overview of existing dynamic finger search data structures. Section 11.3 and Section 11.4 give details concerning how three constructions support efficient finger searches: The level linked (2,4)-trees of Huddleston and Mehlhorn [26], the randomized skip lists of Pugh [36, 37] and the randomized binary search trees, treaps, of Seidel and Aragon [39].

Guibas et al. [21] introduced finger search trees as a variant of B-trees [4], supporting finger searches in O(log d) time and updates in O(1) time, assuming that only O(1) movable fingers are maintained. Moving a finger d positions requires O(log d) time. This work was refined by Huddleston and Mehlhorn [26]. Tsakalidis [42] presented a solution based on AVL-trees, and Kosaraju [29] presented a generalized solution. Tarjan and van Wyk [41] presented a solution based on red-black trees.

The above finger search tree constructions either assume a fixed constant number of fin- gers or only support updates in amortized constant time. Constructions supporting an arbitrary number of fingers and with worst case update have been developed. Levcopoulos and Overmars [30] presented a search tree that supported updates at an arbitrary position in worst case O(1) time, but only supports searches in O(log n) time. Constructions supporting O(log d) time searches and O(log∗ n) time insertions and deletions were developed by Harel [22, 23] and Fleischer [19]. Finger search trees with worst-case constant time insertions and O(log∗ n) time deletions were presented by Brodal [7], and a construction achieving optimal worst-case constant time insertions and deletions were presented by Brodal et al. [9].

Belloch et al. [6] developed a space efficient alternative solution to the level linked (2,4)-trees of Huddleston and Mehlhorn, see Section 11.3.

Their solution allows a single finger, that can be moved by the same performance cost as (2,4)-trees. In the solution no level links and parent pointers are required, instead a special O(log n) space data structure, hand, is created for the finger that allows the finger to be moved efficiently.

Sleator and Tarjan introduced splay trees as a class of self-adjusting binary search trees supporting searches, insertions and deletions in amortized O(log n) time [40]. That splay trees can be used as efficient finger search trees was later proved by Cole [15, 16]: Given an O(n) initialization cost, the amortized cost of an access at distance d from the preceding access in a splay tree is O(log d) where accesses include searches, insertions, and deletions.

Notice that the statement only applies in the presence of one finger, which always points to the last accessed element.

All the above mentioned constructions can be implemented on a pointer machine where the only operation allowed on elements is the comparison of two elements. For the Random Access Machine model of computation (RAM), Dietz and Raman [17, 38] developed a finger search tree with constant update time and O(log d) search time. This result is achieve by tabulating small tree structures, but only performs the comparison of elements. In the same model of computation, Andersson and Thorup [2] have surpassed the logarithmic bound in the search procedure by achieving  query time. This result is achieved by considering elements as bit-patterns/machine words and applying techniques developed for the RAM to surpass lower bounds for comparison based data structures. A survey on RAM dictionaries can be found in Chapter 39.