Finger Search Trees:Level Linked (2,4)-Trees

Level Linked (2,4)-Trees

In this section we discuss how (2,4)-trees can support efficient finger searches by the introduction of level links. The ideas discussed in this section also applies to the more general class of height-balanced trees denoted (a, b)-trees, for b ≥ 2a. A general discussion of height balanced search trees can be found in Chapter 10. A throughout treatment of level linked (a, b)-trees can be found in the work of Huddleston and Mehlhorn [26, 32].

A (2,4)-tree is a height-balanced search tree where all leaves have the same depth and all internal nodes have degree two, three or four. Elements are stored at the leaves, and internal nodes only store search keys to guide searches. Since each internal node has degree at least two, it follows that a (2,4)-tree has height O(log n) and supports searches in O(log n) time.

An important property of (2,4)-trees is that insertions and deletions given by a finger take amortized O(1) time (this property is not shared by (2, 3)-trees, where there exist sequences of n insertions and deletions requiring Θ(n log n) time). Furthermore a (2,4)-tree with n leaves can be split into two trees of size n1 and n2 in amortized O(log min(n1, n2)) time. Similarly two (2,4)-trees of size n1 and n2 can be joined (concatenated) in amortized O(log min(n1, n2)) time.

To support finger searches (2,4)-trees are augmented with level links, such that all nodes with equal depth are linked together in a double linked list. Figure 11.2 shows a (2,4)-tree augmented with level links. Note that all edges represent bidirected links. The additional level links are straightforward to maintain during insertions, deletions, splits and joins of (2,4)-trees.

To perform a finger search from x to y we first check whether y is to the left or right of x. Assume without loss of generality that y is to the right of x. We then traverse the path from x towards the root while examining the nodes v on the path and their right neighbors until it has been established that y is contained within the subtree rooted at v or v’s right neighbor. The upwards search is then terminated and at most two downwards searches for y is started at respectively v and/or v’s right neighbor. In Figure 11.2 the pointers followed during a finger search from J to T are depicted by thick lines.

The O(log d) search time follows from the observation that if we advance the upwards search to the parent of node v then y is to the right of the leftmost subtree of vts right neighbor, i.e. d is at least exponential in the height reached so far. In Figure 11.2 we advance from the internal node labeled “L N” to the node labeled “H” because from “S” we know that y is to the right of the subtree rooted at the node “Q R”.

The construction for level linked (2,4)-trees generalizes directly to level linked (a, b)-trees that can be used in external memory. By choosing a = 2b and b such that an internal node fits in a block in external memory, we achieve external memory finger search trees supporting insertions and deletions in O(1) memory transfers, and finger searches with O(logb n) memory transfers.