Finger Search Trees:Randomized Finger Search Trees.

By -
Randomized Finger Search Trees

Two randomized alternatives to deterministic search trees are the randomized binary search trees, treaps, of Seidel and Aragon [39] and the skip lists of Pugh [36, 37]. Both treaps and skip lists are elegant data structures, where the randomization facilitates simple and efficient update operations.

In this section we describe how both treaps and skip lists can be used as efficient finger search trees without altering the data structures. Both data structures support finger searches in expected O(log d) time, where the expectations are taken over the random choices made by the algorithm during the construction of the data structure. For a general introduction to randomized dictionary data structures see Chapter 13.

Treaps

A treap is a rooted binary tree where each node stores an element and where each element has an associated random priority. A treap satisfies that the elements are sorted with respect to an inorder traversal of tree, and that the priorities of the elements satisfy heap order, i.e., the priority stored at a node is always smaller than or equal to the priority stored at the parent node. Provided that the priorities are distinct, the shape of a treap is uniquely determined by its set of elements and the associated priorities. Figure 11.3 shows a treap storing the elements A,B,.. .,T and with random integer priorities between one and hundred.

The most prominent properties of treaps are that they have expected O(log n) height, implying that they provide searches in expected O(log n) time. Insertions and deletions of elements can be performed in expected at most two rotations and expected O(1) time, provided that the position of insertion or deletion is known, i.e. insertions and deletions given by a finger take expected O(1) time [39].

The essential property of treaps enabling expected O(log d) finger searches is that for two elements x and y whose ranks differ by d in the set stored, the expected length of the path between x and y in the treap is O(log d). To perform a finger search for y starting with a finger at x, we ideally start at x and traverse the ancestor path of x until we reach the least common ancestor of x and y, LCA(x, y), and start a downward tree search for y. If we can decide if a node is LCA(x, y), this will traverse exactly the path from x to y. Unfortunately, it is nontrivial to decide if a node is LCA(x, y). In [39] it is assumed that a treap is extended with additional pointers to facilitate finger searches in expected O(log d) time. Below an alternative solution is described not requiring any additional pointers than the standard left, right and parent pointers.

Assume without loss of generality that we have a finger at x and have to perform a finger search for y ≥ x present in the tree. We start at x and start traversing the ancestor path of x. During this traversal we keep a pointer .e to the last visited node that can potentially

image

Unfortunately, after LCA(x, y) has been visited case (1) can happen ω(log d) times before the search is terminated at the root or by case (3). Seidel and Aragon [39] denote these extra nodes visited above LCA(x, y) the excess path of the search, and circumvent this problem by extending treaps with special pointers for this.

To avoid visiting long excess paths we extend the above upward search with a concurrent downward search for y in the subtree rooted at the current candidate .e for LCA(x, y). In case (1) we always advance the tree search for y one level down, in case (2) we restart the search at the new .e, and in (3) we finalize the search. The concurrent search for y guarantees that the distance between LCA(x, y) and y in the tree is also an upper bound on the nodes visited on the excess path, i.e. we visit at most twice the number of nodes as is on the path between x and y, which is expected O(log d). It follows that treaps support finger searches in O(log d) time. In Figure 11.3 is shown the search for x = I, y = P , LCA(x, y) = K, the path from x to y is drawn with thick lines, and the excess path is drawn with dashed lines.

Skip Lists

A skip list is a randomized dictionary data structure, which can be considered to consists of expected O(log n) levels. The lowest level being a single linked list containing the elements in sorted order, and each succeeding level is a random sample of the elements of the previous level, where each element is included in the next level with a fixed probability, e.g. 1/2. The  pointer representation of a skip is illustrated in Figure 11.4.

image

The most prominent properties of skip lists are that they require expected linear space, consist of expected O(log n) levels, support searches in expected O(log n) time, and support insertions and deletions at a given position in expected O(1) time [36, 37].

Pugh in [36] elaborates on the various properties and extensions of skip lists, including pseudo-code for how skip lists support finger searches in expected O(log d) time. To facilitate backward finger searches, a finger to a node v is stored as an expected O(log n) space finger data structure that for each level i stores a pointer to the node to the left of v where the level i pointer either points to v or a node to the right of v. Moving a finger requires this list of pointers to be updated correspondingly.

A backward finger search is performed by first identifying the lowest node in the finger data structure that is to the left of the search key y, where the nodes in the finger data structure are considered in order of increasing levels. Thereafter the search proceeds downward from the identified node as in a standard skip list search.

Figure 11.4 shows the situation where we have a finger to H, represented by the thick (solid or dashed) lines, and perform a finger search for the element D to the left of H. Dashed (thick and thin) lines are the pointers followed during the finger search. The numbering indicate the other in which the pointers are traversed.

If the level links of a skip list are maintained as double-linked lists, then finger searches can be performed in expected O(log d) time by traversing the existing links, without having a separate O(log n) space finger data structure

Comments

Post a Comment

Popular posts from this blog

0/1 Knapsack Problem Memory function.

By -
Image
0 / 1 Knapsack Problem Memory function Definition: Given a set of n items of known weights w1,…,wn and values v1,…,vn and a knapsack of capacity W, the problem is to find the most valuable subset of the items that fit into the knapsack. Knapsack problem is an OPTIMIZATION PROBLEM Dynamic programming approach to solve knapsack problem Step 1: Identify the smaller sub-problems. If items are labeled 1..n, then a sub-problem would be to find an optimal solution for Sk = {items labeled 1, 2, .. k } Step 2: Recursively define the value of an optimal solution in terms of solutions to smaller problems. Initial conditions: S te p 3: Bottom up computation using iteration Question: Apply bottom-up dynamic programming algorithm to the following instance of the knapsack problem Capacity W= 5 Solution: Using dynamic programming approach, we have: What is the composition of the optimal subset? The composition of the optimal subset if found by tracing back the computations for the...
Read more

Binary Space Partitioning Trees:BSP Tree as a Hierarchy of Regions.

By -
Image
BSP Tree as a Hierarchy of Regions Another way to look at BSP Trees is to focus on the hierarchy of regions created by the recursive partitioning, instead of focusing on the hyperplanes themselves. This view helps us to see more easily how intersections are efficiently computed. The key idea is to think of a BSP Tree region as serving as a bounding volume: each node v corresponds to a convex volume that completely contains all the geometry represented by the sub tree rooted at v . Therefore, if some other geometric entity, such as a point, ray, object, etc., is found to not intersect the bounding volume, then no intersection computations need be performed with any geometry within that volume. Consider as an example a situation in which we are given some test point and we want to find which object if any this point lies in. Initially, we know only that the point lies somewhere space ( Figure 20.12). By comparing the location of the point with respect to the first partitioning hyper pl...
Read more

Drawing Trees:HV-Layout

By -
Image
HV-Layout An hv -layout of a binary tree is an upward (but not strictly upward) straight line orthogonal drawing with edges drawn as rightward horizontal or downward vertical segments. The ”hv” stands for horizontal-vertical. For any vertex v in a binary tree T we either have: 1. A child of v is either • aligned horizontally with v and to the right of v or • vertically aligned below v . 2. The smallest rectangles that cover the area of the subtrees of the children of v in the layout do not intersect. Figure 45.12 shows an example of a hv -layout A hv -layout is generated by applying a dived and conquer approach. The divide step constructs the hv -layout of the left and the right subtrees, while the conquer step either performs a ho rizontal or a ver t i c a l combination . Figure 45.13 shows the two types of com- bination. If the left subtree a node v is placed to the left in a horizontal combination and below in a vertical combination, the layout preserves ...
Read more