Splay Trees:Optimality of Splay Trees

Optimality of Splay Trees

If w(i) the weight of node i is independent of the number of descendants of node i, then the maximum value of size(i) will be W = ), w(i) and minimum value of size(i) will be w(i).

As size of the root t, will be W , and hence rank log W , so by Lemma 12.1, the amortized

Static Optimality

On any sequence of accesses, a splay tree is as efficient as the optimum binary search tree, up to a constant multiplicative factor. This can be very easily shown.

Let q(i) be the number of times the ith node is accessed, we assume that each item is accessed at least once, or q(i) ≥ 1. Let m = ), q(i) be the total number of times we access any item in the splay tree. Assign a weight of q(i)/m to item i. We call q(i)/m the access frequency of the ith item. Observe that the total (or maximum) weight is 1 and hence the rank of the root r(t) = 0.

REMARK 12.1 The total time, for this analysis is the same as that for the (static) optimal binary search tree.

Static Finger Theorem

REMARK 12.2 f can be chosen as any fixed item (finger). Thus, this out-performs finger-search trees, if any fixed point is used as a finger; but here the finger need not be specified.

Working Set Theorem

Splay trees also have the working set property, i.e., if only t different items are being repeatedly accessed, then the time for access is actually O(log t) instead of O(log n). In fact, if tj different items were accessed since the last access of ij th item, then the amortized time for access of ij th item is only O(log(tj + 1)).

This time, we number the accesses from 1 to m in the order in which they occur. Assign weights of 1, 1/4, 1/9, ··· , 1/n2 to items in the order of the first access. Item accessed earliest gets the largest weight and those never accessed get the smallest weight. Total weight W = ),(1/k2) < 2 = O(1).

It is useful to think of item having weight 1/k2 as being in the kth position in a (some abstract) queue. After an item is accessed, we will be putting it in front of the queue, i.e., making its weight 1 and “pushing back” items which were originally ahead of it, i.e., the weights of items having old weight 1/s2 (i.e., items in sth place in the queue) will have a new weight of 1/(s + 1)2 (i.e., they are now in place s + 1 instead of place s). The position in the queue, will actually be the position in the “move to front” heuristic.

Less informally, we will be changing the weights of items after each access. If the weight of item ij during access j is 1/k2, then after access j, assign a weight 1 to item ij . And an item having weight 1/s2, s < k gets weight changed to 1/(s + 1)2.

Effectively, item ij has been placed at the head of queue (weight becomes 1/12); and weights have been permuted. The value of W , the sum of all weights remains unchanged.

If tj items were accessed after last access of item ij , then the weight of item ij would have been 1/t2, or the amortized time for jth access is O(log(tj + 1)).

After the access, as a result of splay, the ij th item becomes the root, thus the new size of ij th item is the sum of all weights W — this remains unchanged even after changing weights. As weights of all other items, either remain the same or decrease (from 1/s2 to 1/(s + 1)2), size of all other items also decreases or remains unchanged due to permutation of weights. In other words, as a result of weight reassignment, size of non-root nodes can decrease and size of the root remains unchanged. Thus, weight reassignment can only decrease the potential, or amortized time for weight reassignment is either zero or negative.

Hence, by discussions at the beginning of this section, total time for m accesses on a tree of size at most n is O(n log n + ), log(tj +1)) where tj is the number of different items which were accessed since the last access of ij th item (or from start, if this is the first access).

Other Properties and Conjectures

Splay trees are conjectured [13] to obey “Dynamic Optimality Conjecture” which roughly states that cost for any access pattern for splay trees is of the same order as that of the best possible algorithm. Thus, in amortized sense, the splay trees are the best possible dynamic binary search trees up to a constant multiplicative factor. This conjecture is still open.

However, dynamic finger conjecture for splay trees which says that access which are close to previous access are fast has been proved by Cole[5]. Dynamic finger theorem states that the amortized cost of an access at a distance d from the preceding access is O(log(d + 1)); there is however O(n) initialization cost. The accesses include searches, insertions and deletions (but the algorithm for deletions is different)[5].

Splay trees also obey several other optimality properties (see e.g. [8]).