Skip-Splay: Toward Achieving the Unied Bound in the BST Model
Jonathan C. Derryberry and Daniel D. Sleator
Computer Science Department Carnegie Mellon University Abstract. We present skip-splay, the rst binary search tree algorithm known to have a running time that nearly achieves the unied bound. Skip-splay trees require only O(m lg lg n + UB()) time to execute a query sequence = 1. m. The skip-splay algorithm is simple and similar to the splay algorithm.
Introduction and Related Work
Although the worst-case access cost for comparison-based dictionaries is (lg n), many sequences of operations are highly nonrandom, allowing tighter, instancespecic running time bounds to be achieved by algorithms that adapt to the input sequence. Splay trees [1] are an example of such an adaptive algorithm that operates within the framework of the binary search tree (BST) model [2], which essentially requires that all elements be stored in symmetric order in a rooted binary tree that can only be updated via rotations, and requires queried nodes to be rotated to the root. (BST algorithms that do not rotate to the root can usually be coerced into this model with just a constant factor of overhead.) The two most general bounds proven for splay trees are the working set bound [1] and the dynamic nger bound [3], [4]. The working set bound shows that splay trees can have better than O(lg n) cost per operation when recently accessed elements are much more likely to be accessed than random elements, while the dynamic nger bound shows that splay trees have better than O(lg n) performance when each access is likely to be near the previous access. Iacono later introduced the unied bound, which generalized both of these two bounds [5]. Roughly, a data structure that satises the unied bound has good performance for sequences of operations in which most accesses are likely to be near a recently accessed element. More formally, suppose the access sequence is = 1. m and each access j is a query to the set {1,. , n} (we also use j to refer to the actual element that is queried, as context suggests). The unied bound can be dened as follows:

UB() =

min lg(w(j , j ) + |j j |),

j <j

where w(x, j) is, at time j, the number of distinct elements including x that have been queried since the previous query to x, or n if no such previous query exists. For a more formal denition, see the denitions that precede Lemma 1.
F. Dehne et al. (Eds.): WADS 2009, LNCS 5664, pp. 194205, 2009. c Springer-Verlag Berlin Heidelberg 2009
To achieve a running time of O(m + UB ()), Iacono introduced a data structure called the unied structure. The unied structure did not require amortization to achieve this bound, and was later improved by Bdoiu et al. to allow a insertion and deletion [6]. The unied structure was comparison-based but did not adhere to the BST model. Thus, in addition to leaving open questions regarding how powerful the BST model was, it was not clear, for example, how to achieve the unied bound while keeping track of aggregate information on subsets of elements as can be done with augmented BSTs. These unresolved issues motivate the question of whether a BST algorithm exists that achieves the unied bound. Achieving this goal contrasts with the separate pursuit of a provably dynamically optimal BST algorithm in that it is possible for a data structure that achieves the unied bound to have the trivial competitive ratio of (lg n) to an optimal BST algorithm. Conversely, prior to this work, even if a dynamically optimal BST algorithm had been found, it would not have been clear whether it satised the unied bound to within any factor that was o(lg n) since dynamic optimality by itself says nothing about actual formulaic bounds, and prior to this work no competitive factor better than O(lg n) was known for the cost of the optimal BST algorithm in comparison to the unied bound. See [7], [8], and [9] for progress on dynamic optimality in the BST model. The skip-splay algorithm presented in this paper has three important qualities. First, it conforms to the BST model and has a running time of O(m lg lg n + UB ()), just an additive term of O(lg lg n) per query away from the unied bound. Thus, skip-splay trees nearly close the gap between what is known to be achievable in the BST model and what is achieved by the unied structure. Second, the skip-splay algorithm is very simple. The majority of the complexity of our result resides in the analysis of skip-splaying, not in the design of the algorithm itself. The unied structure, though it avoids the additional O(lg lg n) cost per query, is signicantly more complicated than skip-splay trees. Finally, skip-splaying is almost identical to splaying, which suggests that a similar analysis, in combination with new insight, might be used to prove that splay trees satisfy the unied bound, at least to within some nontrivial multiplicative factor or additive term.

The Skip-Splay Algorithm

We assume for simplicity that a skip-splay tree T stores all elements of {1,. , n} k1 where n = for some positive integer k, and that T is initially perfectly balanced. We mark as a splay tree root every node whose height (starting at a height of 1 for the leaves) is 2i for i {0,. , k 1}.1 Note that the set of all of these splay trees partitions the elements of T.
If we allow the ratio between the initial heights of successive roots to vary, we can achieve a parameterized running time bound, but in this version of the paper we use a ratio of 2 for simplicity.
J.C. Derryberry and D.D. Sleator
Fig. 1. An example of a four-level skip-splay tree T at the beginning of a query sequence. The white nodes are the roots of the splay trees that make up T , and the gray edges are never rotated. If the bottom element of the bold path is queried, then each of the boxed nodes is splayed to the root of its splay tree.
The following denitions will help us describe the algorithm more clearly: 1. Let Ti be the set of all keys x whose path to the root of T contains at most i root nodes, including x itself if x is marked as a root. 2. Dene level i of T to be the set of keys x whose path to the root contains exactly i nodes. We will sometimes use the adjective level-i to refer to objects associated with level i in some way. 3. Let tree(x) be the splay tree that contains x. Also, tree(x) can represent the set of elements in tree(x). We assume that all operations are queries, and we use = 1. m to denote the sequence of queries. To query an element j , we rst perform binary search through T to locate j. Then, we splay j to the root of tree(j ) and transfer the relevant root marker to j. If we are at the root of T , we terminate, else we skip to j s new parent x and repeat this process by splaying x to the root of tree(x). The cost of a query is dened to be the number of nodes on the access path to j.2 Figure 1 shows an example of what a skip splay tree looks like at the beginning of an access sequence and depicts how a query is performed. Intuitively, skip-splaying is nearly competitive to the unied bound because if the currently queried element j is near to a recently queried element f , then many of the elements that are splayed while querying j are likely to be the same as the ones that were splayed when f was queried. Therefore, by the working set bound for splay trees, these splays should be fairly cheap. The analysis in Section 3 formalizes this intuition.

Proving Skip-Splay Runs in Time O(m lg lg n + UB())
Our analysis in this section consists of three lemmas that together prove that skip-splay trees run in time O(m lg lg n+UB()). The purpose of the rst lemma
Note that this algorithm can be coerced into the BST Model dened in [2] by rotating j to the root and back down, incurring only a constant factor of additional cost.
is to decompose the cost of skip-splay trees into a series of local working set costs with one cost term for each level in T. The second lemma is the main step of the analysis and it uses the rst lemma to prove that skip-splay trees satisfy a bound that is very similar to the unied bound, plus an additive O(lg lg n) term. The third lemma shows that this similar bound is within a constant factor of the unied bound, so our main analytical result, that skip-splay trees run in O(m lg lg n + UB ()) time, follows immediately from these three lemmas. In the rst lemma and in the rest of this paper, we will use the following custom notation for describing various parts of T : so that i = 2 for i < k 1. 1. Let k = 1 and for i < k let i = 22 i+1 Note that if element x T is in level i for i < k, then |tree(x)| = i 1. 2. Let Ri (x), the level-i region of x T be dened as follows. First, dene the oset i = mod i , where is an integer that is arbitrary but xed for all levels of T. (Our analysis will later make use of the fact that we can choose to be whatever we want.) Then, let Ri (x) = Ri (x) T where

Ri (x) = x+i i

i i ,. ,

i i + i 1.

Note that the level-i regions partition the elements of T and the level-i + 1 regions are a renement of the level-i regions. Two regions R and R are said to be adjacent if they are distinct, occupy the same level, and their union covers a contiguous region of keyspace. Note that |Ri (x)| = i if Ri (x) T. 3. Let Ri (x), the level-i region set of x, be the set of level-i regions that are subsets of Ri1 (x) with R1 (x) dened to be the set of all level-1 regions. Note that |Ri (x)| = i if 1 < i < k and Ri1 (x) T. Additionally, we give the following denitions of working set numbers and some auxiliary denitions that will also be helpful (these denitions assume we are working with a xed query sequence ): 1. Let splays(j) be the set of elements that are splayed during query j. 2. Let p(x, j) represent the index of the previous access to x before time j. More formally, assuming such an access exists, let p(x, j) = max({1,. , j 1} {j | j = x}). We dene p(x, j) = n if the argument to max is the empty set. 3. Let p (x, j) represent the index of the previous access that resulted in a splay to x before time j. More formally, assuming such an access exists, let p (x, j) = max({1,. , j 1} {j | x splays(j )}). We dene p (x, j) = i if the argument to max is the empty set. 4. Let pi (x, j) represent the index of the previous access to region Ri (x). More formally, assuming such an access exists, let pi (x, j) = max({1,. , j 1} {j | Ri (j ) = Ri (x)}). We dene pi (x, j) = i if the argument to max is the empty set. Also, let pi (R, j) be equivalent to pi (x, j) if R = Ri (x).

5. For x T , let w(x, j) represent the number of elements queried since the previous access to x. More formally, if p(x, j) > 0 let w(x, j) = j | j {p(x, j),. , j 1}.
Else, if p(x, j) 0 then let w(x, j) = p(x, j). 6. For x T , let w (x, j) represent the working set number of x within tree(x) (i.e., the number of elements splayed in tree(x) since the previous query resulting in a splay to x). More formally, if p (x, j) > 0 let w (x, j) = tree(x)

j {p (x,j),.,j1}

splays(j ).
Else, if p (x, j) 0 then let w (x, j) = p (x, j). 7. For x T , let wi (x, j) represent the number of regions in Ri (x) that contain a query since the previous access to a member of Ri (x). More formally, if pi (x, j) > 0 let wi (x, j) = Ri (j ) | j {pi (x, j),. , j 1} Ri (x).
Else, if pi (x, j) 0 then let wi (x, j) = pi (x, j). Also, let wi (R, j) be equivalent to wi (x, j) if R = Ri (x). 8. For x T , let wi (x, j) be the working set number of x within tree(x) that is reset whenever a query is executed to a region that could cause a splay of x. More formally, let R(x) be the set of up to three regions R such that a query to R can cause a splay of x. If pi (R, j) > 0 for some R R(x) let wi (x, j) = tree(x)
j {maxRR(x) pi (R,j),.,j1}
Else, if pi (R, j) 0 for all R R(x) then let wi (x, j) = i. Note that wi (x, j) 3wi (R, j) + 1 for R (R(x) Ri (x)) because accesses to a region in Ri (x) can result in splays of at most three dierent elements of tree(x), and at most one, the minimum element of tree(x), can be splayed as the result of a query to another level-i region set. Also, note that wi (x, j) w (x, j). In the proof of the rst lemma, we will be making use of the working set theorem in Sleator and Tarjans original splay tree paper [1], which shows that the cost of a query sequence on an individual splay tree, for suciently large m n, is bounded by cs (n lg n + j=1 lg(w(j , j) + 1)), for some constant cs. For simplicity, we assume we are starting with a minimum potential arrangement of m each splay tree, so this simplies to j=1 cs lg(w(j , j)+1). In order to make the analysis in Lemma 2 simpler, we move beyond simply associating this working set cost with each splay that is executed in T by proving the following lemma.
Lemma 1. For query sequence in a skip-splay tree T with k levels, the amortized cost of query j is

lg wi (j , j).

Proof. By the denition of the skip-splay algorithm and the working set theorem for splay trees, the amortized cost of query j is xsplays(j) w (x, j), suppressing multiplicative and additive constants. To prove Lemma 1, we will do further accounting for the cost of a query j and focus on the cost associated with an arbitrary level i of T. Note that at level i during query j , one of three cases occurs with regard to which level-i node, if any, is splayed. First, if j resides in a strictly shallower level than i, then no splay is performed in level i. Second, if j resides within level i, then j is splayed in level i. Third, if j resides in a deeper level than i, then either the predecessor or the successor of j in level i is splayed. (We know that at least one of these two nodes exists and is on the access path in this case.) We will use the following potential function on T to prove that the bound in Equation 2 holds regardless of which of these three cases occurs: (T, j) = 1 (T, j) + 2 (T, j), where 1 (T, j) =

(lg w (x, j + 1) lg wi (x, j + 1))

and 2 (T, j) =

(x,y)A
| lg wi (x, j + 1) lg wi (y, j + 1)|,
where A is the set of pairs of level-i nodes (x, y) such that x is the maximum element in tree(x), y is the minimum element in tree(y), and there are no other level-i elements between x and y. For succinctness below, dene (T, j) to be (T, j) (T, j 1) and dene 1 (T, j) and 2 (T, j) analogously. First, notice that the cost of the splay, if any, that is performed on node x at level i is oset by the change in potential of lg w (x, j + 1) lg w (x, j) = lg w (x, j). Note that this ignores the dierence lg wi (x, j) lg wi (x, j + 1) = lg wi (x, j), which will be accounted for below. Second, dene + (T, j) to be the sum of the positive terms of (T, j) plus lg wi (x, j) in the case in which some node x is splayed during query j. We will show that regardless of whether a splay is performed in level i during query j , it is true that + (T, j) is at most 4 lg(3wi (j , j) + 1) + 2. To see this, let Y be the set of up to three level-i nodes that can be splayed while accessing members of the region Ri (j ), and notice that if a node x is splayed at level i during query j then x Y. Note that the only positive terms of + (T, j) from 1 (T, j) are the ones that use some member of Y as an argument. This is true because lg w (z, j + 1) lg w (z, j) lg wi (z, j + 1) lg wi (z, j)
for z T \Y since w (z, j) wi (z, j) and w (z, j + 1) w (z, j) wi (z, j + 1) wi (z, j). Further, note that + (T, j) contains at most two terms from 2 (T, j) that do not use some member of Y as an argument, and these two terms are at most 1 each. Now, we consider the following two cases. All additional cases are either similar to or simpler than these two cases. First, suppose that Y contains two elements y1 < y2 and tree(y1 ) = tree(y2 ). Note that in this case we know that Ri (j ) = Ri (y1 ). Then, + (T, j) lg wi (y1 , j) + lg wi (y2 , j) | lg wi (y1 , j) lg wi (y2 , j)| + lg wi (y1 , j) + lg(3wi (j , j) + 1) + 2. Second, suppose that Y contains three elements y1 < y2 < y3 that all reside in the same splay tree T , suppose y3 is the maximum element of T , and let z be the successor of y3 among the level-i elements (assuming z exists in this case). Using the fact that | lg wi (y3 , j + 1) lg wi (z, j + 1)| = lg wi (z, j + 1) = lg wi (z, j) and the fact that Ri (y1 ) = Ri (y2 ) = Ri (y3 ) = Ri (j ), we have

+ (T, j)

lg wi (yq , j) + lg wi (z, j) | lg wi (y3 , j) lg wi (z, j)| + 2
lg wi (y1 , j) + lg wi (y2 , j) + 2 lg wi (y3 , j) + lg(3wi (j , j) + 1) + 2. We note that the potential function used in Lemma 1 starts at its minimum value and the splay trees also start at their minimum potential conguration. Therefore, the sum of the amortized costs of each query, according to Lemma 1, is an upper bound on the cost of the sequence. Using Lemma 1, we can prove a bound that is similar to the unied bound, plus an additive O(lg lg n) term per query. This bound diers from the unied bound in that the working set portion of the cost consists not of the number of elements accessed since the previous query to the relevant element, but of the number of queries since the previous query to the relevant element. Before we prove this bound, we give the following denitions, which will be useful in formally describing the bound and proving it: 1. Let fj represent the element j such that j = argmin lg(w(j , j) + |j j |).

Intuitively, fj represents the nger for query j because it represents the previously-queried element that yields the smallest unied bound value for query j. 2. For x T , let t(x, j) represent the number of queries (rather than distinct elements accessed) since the previous access to x. More formally, let t(x, j) = |{p(x, j),. , j 1}| = j p(x, j). Note that the above denition handles the case in which p(x, j) 0.
3. For x T , let ti (x, j) represent the number of queries to all members of Ri (x) since the previous access to a member of Ri (x). More formally, let ti (x, j) = j {max(1, pi (x, j)),. , j 1} | Ri (j ) Ri (x) ,
with an additional pi (x, j) added if pi (x, j) 0. 4. For x T , let ti (x, j) represent the number of queries to all members of Ri (x) since the previous access to x. More formally, let ti (x, j) = j {max(1, p(x, j)),. , j 1} | Ri (j ) Ri (x) ,
with an additional 2 added if p(x, j) 0. Note that t1 (x, j) t(x, j) + 1 by i denition. Next, we dene UB (), a variant of the unied bound, as

UB () =

lg(t(fj , j) + |j fj |),
and we are ready to proceed with our second lemma. Lemma 2. Executing the skip-splay algorithm on query sequence = 1. m costs time O(m lg lg n + UB ()). Proof. In this proof, we will be making use of the bound in Lemma 1 with a randomly chosen oset that is selected uniformly at random from {0,. , 1 1}. We will use induction on the number of levels i from the top of the tree while analyzing the expected amortized cost of an arbitrary query j. In the inductive step, we will prove a bound that is similar to the one in Lemma 2, and this similar bound will cover the cost associated with levels i and deeper. Even though we are directly proving the inductive step in expectation only, because the bound in Lemma 1 is proven for all values of , we know that there exists at least one value of such that the bound holds without using randomization if we amortize over the entire query sequence. Therefore, the worst-case bound on the total cost of the access sequence in Lemma 2 will follow. Our inductive hypothesis is that the cost of skip-splaying j that is associated with levels i + 1 and deeper according to Lemma 1 is at most lg ti+1 (fj , j) + lg min(1 + |j fj |2 , i+1 ) + (k i), (7)

where k, as before, represents the number of levels of splay trees in T. We choose levels k and k 1 to be our base cases. The inductive hypothesis is trivially true for these base cases as long as we choose the constants appropriately. Also, the bound for the inductive hypothesis at level 1, summed over all queries, is O(m lg lg n + UB ()), so proving the inductive step suces to prove the lemma.
To prove the inductive step, we assume Equation 7 holds for level i + 1 and use this assumption to prove the bound for level i. Thus, our goal is to prove the following bound on the cost that Lemma 1 associates with query j for levels i and deeper: lg ti (fj , j) + lg min(1 + |j fj |2 , i ) + (k i + 1). (8)
As a starting point for the proof of the inductive step, Lemma 1 in addition to the inductive hypothesis allows us to prove an upper bound of lg wi (j , j) + lg ti+1 (fj , j) + lg min(1 + |j fj |2 , i+1 ) + (k i), (9)
where we have suppressed the constant from Lemma 1 multiplying lg wi (j , j). Our proof of the inductive step consists of three cases. First, if |j fj |2 i , then substituting i for i+1 increases the bound in Equation 9 by lg i lg i+1 = lg

= lg (i+1 ) = lg i

lg wi (j , j)1/2 ,
which osets the elimination of the cost lg wi (j , j) as long as 2. The other substitutions only increase the bound, so for this case we have proved the inductive step. Second, if |j fj |2 < i and Ri (j ) = Ri (fj ), then we simply pay lg wi (, j) which is at most lg i. However, we note that the probability of this occurring for 1/2 1/2 a random choice of is at most i /i = i , so the expected cost resulting 1/2 from this case is at most i lg i , which is at most a constant, so it can be covered by. The third and most dicult case occurs when |j fj |2 < i and Ri (j ) = Ri (fj ), and we will spend the rest of the proof demonstrating how to prove the inductive step for this case. First, we note that lg ti (fj , j) lg wi (fj , j) = lg wi (j , j), so we can replace lg wi (j , j) with lg ti (fj , j) and i+1 with i in Equation 9 without decreasing the bound and prove a bound of lg ti (fj , j) + lg ti+1 (fj , j) + lg min(1 + |j fj |2 , i ) + (k i). (11)

It remains only to eliminate the term lg ti (fj , j) by substituting ti (fj , j) for ti+1 (fj , j) while incurring an additional amortized cost of at most a constant so that it can be covered by. Observe that if j satises ti+1 (fj , j) then we have an upper bound of
lg t (f ,j) lg ti (fj , j) + (lg ti (fj , j) i 2 j ) + lg min(1 + |j fj |2 , i ) + (k i), (13) ti (fj ,j) ti (fj ,j) 2
which would prove the inductive step if 2. However, it is possible that ti+1 (fj , j) does not satisfy the bound in Equation 12. In this latter case, we
pessimistically assume that we must simply pay the additional lg ti (fj , j). In the rest of the proof, we show that the amortized cost of such cases is at most a constant per query in this level of the induction, so that it can be covered by the constant. We rst give a few denitions that will make our argument easier. A query b is R-local if Ri (b ) = R. Further, if b is R-local and satises Ri (fb ) = R as 1 well as the bound ti+1 (fb , b) > ti (fb , b)/ti (fb , b) 2 , then we dene b also to be R-dense. Note that if b is R-dense then p(fb , b) > 0. Finally, if b additionally satises the inequality < ti (fb , b) 2 , then we dene b also to be R- -bad. Notice that all queries that have an excess cost at level i due to being in this third case and not meeting the bound in Equation 12 are R- -bad for some level-i region R and some value of (actually a range of values ). Our plan is to show that the ratio of R- -bad queries to R-local queries is low enough that the sum of the excess costs associated with the R- -bad queries can be spread over the R-local queries so that each R-local query is only responsible for a constant amount of these excess costs. Further, we show that if we partition the R-dense queries by successively doubling values of , with some constant lower cuto, then each R-local querys share of the cost is exponentially decreasing in lg , so each R-local query bears only a constant amortized cost for the excess costs of all of the R-dense queries. Lastly, note that in our analysis below we are only amortizing over R-local queries for some specic but arbitrary level-i region R, so we can apply the amortization to each level-i region separately without interference. To begin, we bound the cost associated with the R- -bad queries for arbitrary level-i region R and constant as follows. Let b be the latest R- -bad query. First, note that the number of R- -bad queries a where a {p(fb , b) + 1,. , b} is at most ti (fb , b)/ because there are ti (fb , b) queries to Ri (fb ) in that time period, and immediately prior to each such a , the previous 1 queries to Ri (fb ) are all outside of R so that ti (fa , a) . Second, note that because b was chosen to be R- -bad we have ti+1 (fb , b) >

ti (fb ,b) ti (fb ,b)1/2

ti (fb ,b). (2 )1/2
Thus, the ratio of the number of R-local queries in this time period, ti+1 (fb , b), to the number of R- -bad queries in this time period is strictly greater than

ti (fb ,b) (2 )1/2

ti (fb ,b)

= ( )1/2. 2

The constraint that ti (fa , a) 2 for each of the aforementioned R- -bad queries a implies that the excess level-i cost of each is at most lg(2 ), so we charge each R-local query with a time index in {p(fb , b) + 1,. , b} a cost of lg(2 )/( )1/2 to 2 account for the R- -bad queries that occur during this time interval. Notice that we can iteratively apply this reasoning to cover the R- -bad queries with time indices that are at most p(fb , b) without double-charging any R-local query. To complete the argument, we must account for all R-dense queries, not just the R- -bad ones for some particular value of . To do this, for all R-dense queries
j such that ti (fj , j) 0 , for some constant 0 , we simply charge a cost of lg 0 to. Next, let q = 2q 0 for integer values q 0. From above, we have an upper bound on the amortized cost of the R-q -bad queries of lg(2q+)/(2q)1/2 , so the sum over all values of q is at most a constant and can be covered by. To complete the argument that skip-splay trees run in O(m lg lg n + UB()) time, it suces to show that UB () is at most a constant factor plus a linear term in m greater than UB (). Thus, the following lemma completes the proof that skip-splay trees run in time O(m lg lg n + UB ()). Lemma 3. For query sequence = 1. m , the following inequality is true:

lg(t(fj , j) + |j fj |)

m 2 lg e 6

+ lg e +

2 lg(w(fj , j) + |j fj |). (16)
Proof. To begin, we give a new denition of a working set number that is a hybrid between w(fj , j) and t(fj , j) for arbitrary time index j. Let hi (fj , j) = max(w(fj , j)2 , min(t(fj , j), j i)). Note that lg hm (fj , j) = 2 lg w(fj , j) and hn (fj , j) t(fj , j) for all j. Also, note that if p(fj , j) > 0 then lg hn (fj , j) lg h0 (fj , j) = 0, else if p(fj , j) 0, which is true for at most n queries, then lg hn (fj , j) lg h0 (fj , j) lg(n2 + n) lg(n2 ) lg e. n Next, note that lg hi (fj , j) lg hi+1 (fj , j) = 0 if i j or t(fj , j) j i 1 lg e and for all j we have lg hi (fj , j) lg hi+1 (fj , j) w(fj ,j)2. Also, we know that the number of queries for which i < j, t(fj , j) j i, and w(fj , j) w0 is at most w0 for w0 {1,. , n}. This is true because each such query is to a distinct element since they all use a nger that was last queried at a time index of at most i (if two of these queries were to the same element, then the second query could use the rst as a nger). If there were w0 + 1 such queries, the latest such query would have w(f , j) w0 + 1 because of the previous w0 queries after time i to distinct elements, a contradiction. Therefore,

(lg hi (fj , j) lg hi+1 (fj , j))

j=1 k=1

lg e k2

2 lg e 6 ,

so that
(lg t(fj , j) 2 lg w(fj , j))

j=1 j=1

(lg hn (fj , j) lg hm (fj , j))

+ lg e.

The fact that lg(t(fj , j) + d) 2 lg(w(fj , j) + d) lg t(fj , j) 2 lg w(fj , j) for all j and non-negative d completes the proof.
Conclusions and Future Work
The ideal improvement to this result is to show that splay trees satisfy the unied bound with a running time of O(m+UB ()). However, achieving this ideal result
could be extremely dicult since the only known proof of the dynamic nger theorem is very complicated, and the unied bound is stronger than the dynamic nger bound. In light of this potential diculty, one natural path for improving this result is to apply this analysis to splay trees, perhaps achieving the same competitiveness to the unied bound as skip-splay trees. Intuitively, this may work because the skip-splay algorithm is essentially identical to splaying except a few rotations are skipped to keep the elements of the tree partitioned into blocks with a particular structure that facilitates our analysis. Additionally, it may be possible to design a dierent BST algorithm and show that it meets the unied bound, which would prove that we do not need to leave the BST model, and the perks such as augmentation that it provides, to achieve the unied bound. If such an algorithm is to be similar to skip-splaying, it must mix the splay trees together so that all nodes can reach constant depth. To summarize the clearest paths for related future work, it would be signicant progress to show that splay trees meet the unied bound to within any factor that is o(lg n), or to show that some BST algorithm achieves the unied bound to within better than an additive O(lg lg n) term.

References

1. Sleator, D.D., Tarjan, R.E.: Self-adjusting binary search trees. Journal of the ACM 32, 652686 (1985) 2. Wilber, R.: Lower bounds for accessing binary search trees with rotations. SIAM Journal on Computing 18(1), 5667 (1989) 3. Cole, R., Mishra, B., Schmidt, J.P., Siegel, A.: On the dynamic nger conjecture for splay trees, part I: Splay sorting log n-block sequences. SIAM Journal on Computing 30(1), 143 (2000) 4. Cole, R.: On the dynamic nger conjecture for splay trees, part II: The proof. SIAM Journal on Computing 30(1), 4485 (2000) 5. Iacono, J.: Alternatives to splay trees with o(log n) worst-case access times. In: Proceedings of the 12th ACM-SIAM Symposium on Discrete Algorithms, Philadelphia, PA, USA, pp. 516522. Society for Industrial and Applied Mathematics (2001) 6. Bdoiu, M., Cole, R., Demaine, E.D., Iacono, J.: A unied access bound on a comparison-based dynamic dictionaries. Theoretical Computer Science 382(2), (2007) 7. Demaine, E.D., Harmon, D., Iacono, J., Ptracu, M.: Dynamic optimalityalmost. a s SIAM Journal on Computing 37(1), 240251 (2007) 8. Wang, C.C., Derryberry, J., Sleator, D.D.: O(log log n)-competitive dynamic binary search trees. In: Proceedings of the 17th ACM-SIAM Symposium on Discrete Algorithms, pp. 374383. ACM, New York (2006) 9. Georgakopoulos, G.F.: Chain-splay trees, or, how to achieve and prove loglogncompetitiveness by splaying. Information Processing Letters 106(1), 3743 (2008)

Report

Primary Imaging

Lymphoma Findings

of the CNS in an Infant
J. D. Patet,3 G. Souillet,2 and N. Philippe2

with AIDS:

Douek,1

Y. Bertrand,2

V. A. Tran-Minh,1
CNS lymphoma is a common complication of human immunodeficiency virus-i (HIV-i) infection in adults, in whom more than 400 cases of AIDS-related non-Hodgkin Iymphoma have been reported [1 ]. Only isolated cases of primary lymphoma occurring in children with HIV-i infection and detected by CT have been reported [2, 3]. However, the World Health Organization estimates that during the past decade about 500,000 cases of AIDS occurred in women and children, and that during the 1 990s AIDS will kill approximately 3 million women and children worldwide [4]. We report a case of CNS lymphoma in a 6-month-old infant with HIV-1 infection. The
temporal lobe lesion was detected by transfontanellar sonog-
Sonography showed a round hyperechoic mass in the left temporal lobe (Fig. 1A). The mass was isodense on unenhanced CT. After administration of contrast medium, the mass enhanced irregularly with a ringlike pattern, surrounded by an ill-defined hypodense region
(Fig. 1B). Axial Ti-weighted low signal MR intensity images (Fig. showed 1 C). the mass to have a

poorly

images

needle

defined,

On coronal T2-weighted

(2000/i biopsy
core in a large area of highly
the mass had a persistently low-signal intense signal (Fig. 1 D). CT-guided of the temporal mass disclosed immunoblastic lym-

20 [TR/TE]),

phoma of the brain. Chest radiography,

abdominal

sonography,
bone marrow biopsies showed no evidence of lymphoma apart from that in the CNS. The infants clinical state improved under chemotherapy, but sonography, CT, and MR showed that the lymphoma
raphy and diagnosed Case Report
on the basis of CT-guided

biopsy.

did not regress completely.
The infant died 2 months after initiation

to be AIDS-related

of therapy. The cause of death was believed encephalopathy. Autopsy was not performed.
A 6-month-old girl was admitted for fever and somnolence. mother was an IV drug user, and both the child and her mother
seropositive for HIV-1. Neurologic examination revealed axial

Her were

rigidity

Discussion

Primary compromised

lymphoma persons

is rare in immunocompetent

chilin-

and a mild right hemiparesis. The child had a normal head circumference of 40.5 cm and normal developmental milestones. Moderate hepatomegaly and maculopapular skin rash were noted. Findings on ophthalmoscopy were normal. Electroencephalography showed mild asymmetry between the right and left hemispheres. Cultures of CSF were negative for bacteria, fungi, and mycobacteria. lmmunologic data showed reverse helper lymphocyte/suppressor lymphocyte ratio, hypergammaglobulinemia, positive P24 antigenemia, and a low level of anti-P24 antibodies. Serology was negative for Epstein-Barr virus.
dren, but it has been diagnosed fected with Epstein-Barr

virus was

more frequently

occurs

in immunoin children

[51. It usually

virus.

negative.

In our case,

serology

Epstein-Barr
Although CNS lymphoma has been seen in adults and older children, its presence in a 6-month-old child is unique. Sonog-

naphy was the screening imaging technique this infant, who had neurologic symptoms.
specific hyperechoic mass. Hemorrhage,
used to examine It showed a nonand tumor

abscess,

Received October 30, 1990: accepted after revision January 7, 1991. 1 Department of Pediatric Radiology, UFR Lyon-Nord and H#{244}pital Debrousse, 29 rue Soeur Bouvier, F.69322 Lyon Cedex to V. A. Tran-Minh. 2 Department of Hematology. H#{244}pital Debrousse, 29 rue Soeur Bouvier, F.69322 Lyon. France. 3 Department of Neurosurgery, Clinique Charcot, 51-53 rue Commandant Charcot, F.0 Sainte Foy Les Lyon, France. AJR 156:1037-1038, May 1991 0361-803X/91/1 565-1037 American Roentgen Ray Society

05, France.

Address

reprint

requests

ET AL.

AJR:156,
Fig. 1.-A, Coronal sonogram shows a hyperechoic mass (solid arrows) displacing left lateral ventricle medially (open arrow). B, CT scan obtained after contrast administration shows peripheral enhancement (arrows) of
C, Axial Ti-weighted (620/20) MR image shows mild dilatation of left occipital horn (solid arrows) behind mass (open arrows). D, Coronal T2-eeighted (2000/120) MR image through mass shows hypointense center (solid arrow) and hyperintense periphery (open arrows).

.-.ag,\,_ _.:

were considered. CT and MR also were nonspecific for lymphoma. In previous reports [6, 7], lymphoma, especially immunoblastic tumors, most often appears on CT as a hyper-

dense mass enhancing

trast medium. Less

homogeneously

after infusion that simulates

of conis

frequently,

as in our case,

lymphoma
infected with HIV-i. Neither imaging able to distinguish between lymphoma and brain to toxoplasmosis. Thus, CNS biopsy under CT useful before initiating chemotherapy, as was patient. in adults
technique is abscess due guidance is done in this

isodense

with a ring enhancement

bacterial,

REFERENCES

1. Haskal

mised human ZJ, Lindan CE, Goodman PC. Lymphoma in the immunocompropatient. Radio! Clin North Am 1990:28:885-899
fungal, or toxoplasmic abscess. with delayed scans may show
Double-dose contrast CT additional lesions, because

CNS lymphomas

in adults with AIDS are typically

multicentnic.

In our case, the tumor was isolated. In CNS lymphoma, MR studies typically show a supratentonal peniventricular mass that is isointense or hypointense on Ti -weighted images. On T2-weighted images, the central tumor cone is isointense on hypointense relative to adjacent
2. Epstein LG, Sharer LR, Oleske JM, et al. Neurologic
immunodeficiency virus infection in

manifestations

Pediatrics

children.

1986:78:678-686 3. Epstein LG, Di Carlo FJ, Joshi VV, et al. Primary
edema. The signal intensity reflects edema and microscopic perivasculan
the relative amount of extension of tumor [8].
In our case, signal intensity was increased around the tumor, which had low signal on T2-weighted images. Other tumors occurring in childhood or adolescence, such as primitive neuroectodermal tumors, may have a similar appearance on MR. In patients infected with HIV-1 or those who are seropositive for HIV, lymphoma is the most likely clinical diagnosis for
lymphoma of the central nervous system in children with acquired immunodeficiency syndrome. Pediatrics 1988:82:355-363 4. Chin J. Current and future dimensions of the HIV/AIDS pandemic in women and children. Lancet 1990:336:221-224 5, Belman AL, Diamond G, Dickson D, et al. Pediatric acquired immunodeficiency syndrome: neurologic syndromes. Am J Dis Child 1988:142:29-35 6. Poon T, Matoso I, Tchertkoff V, Weitzner I, Gade M. CT features of primary cerebral lymphoma in AIDS and non-AIDS patients. J Comput Assist Tomogr 1989:13:6-9 7. Jack CR, ONeill BP, Banks PM, Reese DF. Central nervous system lymphoma: histologic types and CT appearance. Radiology 1988:167:
a mass in the brain. On the other hand, toxoplasmosis
most common cause of space-occupying lesions

is the

of the brain
211-215 8. zimmermann RA. Central nervous system lymphoma. Am 1990:28:697-721

Radio!

Clin North