# Amortized Complexity of Data Structures

Amortized Complexity of Data Structures
Rajamani Sundar
October 1991

A dissertation in the Department of Computer Science submitted to the faculty of the Graduate School of Arts and Science in partial ful llment of the requirements for the degree of Doctor of Philosophy at New York University.

Approved

(Signed)

Ravi Boppana Research Advisor

c Copyright by Rajamani Sundar 1991 All Rights Reserved

Amortized Complexity of Data Structures
Rajamani Sundar Advisor: Ravi Boppana

Abstract
This thesis investigates the amortized complexity of some fundamental data structure problems and introduces interesting ideas for proving lower bounds on amortized complexity and for performing amortized analysis. The problems are as follows:
Dictionary Problem: A dictionary is a dynamic set that supports searches of elements and changes under insertions and deletions of elements. It is open whether there exists a dictionary data structure that takes constant amortized time per operation and uses space polynomial in the dictionary size. We prove that dictionary operations require log-logarithmic amortized time under a multilevel hashing model that is based on Yao's cell probe model. Splay Algorithm's Analysis: Splay is a simple, e cient algorithm for searching binary search trees, devised by Sleator and Tarjan, that uses rotations to reorganize the tree. Tarjan conjectured that Splay takes linear time to process deque operation sequences on a binary tree and proved a special case of this conjecture called the Scanning Theorem. We prove tight bounds on the maximum numbers of various types of right rotations in a sequence of right rotations performed on a binary tree. One of the lower bounds refutes a conjecture of Sleator. We apply the upper bounds to obtain a nearly linear upper bound for Tarjan's conjecture. We give two new proofs of the Scanning Theorem, one of which is a potential-based proof that solves a problem of Tarjan. Set Equality Problem: The task of maintaining a dynamic collection of sets under various operations arises in many applications. We devise a fast data structure for maintaining sets under equality-tests and under creations of new sets through insertions and deletions of elements. Equality-tests require constant time and setcreations require logarithmic amortized time. This improves previous solutions.

i

Acknowledgements
It is a pleasure to acknowledge the help of many people in performing the work of this thesis. I would like to thank my advisor Ravi Boppana for teaching me many useful research skills and teaching/presentation skills. I learnt from him the importance of simple and clear formulation of ideas, and about several useful ideas in Theoretical Computer Science and Discrete Mathematics. The work on the Dictionary Problem owes a great deal to the various things I learnt from him and to his help. He showed me the initial directions to proceed along, he came up with fresh approaches to pursue whenever I failed, and he kept encouraging me to succeed. I would like to thank my co-advisor Richard Cole for initiating me into the area of amortized analysis, for always being a source of inspiration, and for always giving me kind attention and advice when I needed them. The work on the Deque Conjecture owes greatly to the several fruitful discussions I had with him. I would like to thank Mike Fredman, Bud Mishra, and Bob Tarjan for serving on my thesis defense committee and for their role in this work. Mike Fredman and Bob Tarjan supported and guided me during the summer of 1989 when I was a student under them at Bellcore and at Bell labs, respectively. They were always sources of nice problems to work on, and of inspiration and encouragement. The work on the Set Equality Problem is part of a larger joint-work done with Bob Tarjan. Bud Mishra supported me during the academic year 1988-89, and was always a source of encouragement and help. I would like to thank the Courant Institute community for providing a great environment for this work. Finally, I would like to thank IBM Corporation for graciously supporting me during the academic years 1989-91.

ii

Contents
1 Introduction
1.1 Amortized Complexity : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 1.2 Our Work : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :

1
1 3

2 The Dictionary Problem
2.1 Introduction : : : : : : : : : : : : : : : : : : : : : : : : : : : 2.2 Single-level Hashing Model : : : : : : : : : : : : : : : : : : 2.2.1 Uniform Hash Functions and Worst-case Complexity 2.2.2 Nonuniform Hash Functions : : : : : : : : : : : : : : 2.2.3 Amortization : : : : : : : : : : : : : : : : : : : : : : 2.3 Multilevel Hashing Model : : : : : : : : : : : : : : : : : : : 2.3.1 Partial Hashing Model : : : : : : : : : : : : : : : : : 2.3.2 Adversary : : : : : : : : : : : : : : : : : : : : : : : : 2.3.3 Two Random Sampling Lemmas : : : : : : : : : : : 2.3.4 The Worst-case Lower Bound : : : : : : : : : : : : : 2.3.5 Amortization : : : : : : : : : : : : : : : : : : : : : :

5
: : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :
5 9 11 12 13 13 15 16 21 27 30

3 The Deque Conjecture

35

3.1 Introduction : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 35 3.1.1 The Splay Algorithm and Its Conjectures : : : : : : : : : : : : : : 35 3.1.2 Terminology : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 39 iii

3.1.3 Previous Works : : : : : : : : : : : : 3.1.4 Our Results : : : : : : : : : : : : : : 3.2 Counting Twists, Turns, and Cascades : : : 3.2.1 Upper Bounds : : : : : : : : : : : : 3.2.2 Lower Bounds : : : : : : : : : : : : 3.3 An Upper Bound for the Deque Conjecture 3.4 New Proofs of the Scanning Theorem : : : : 3.4.1 A Potential-based Proof : : : : : : : 3.4.2 An Inductive Proof : : : : : : : : : :

: : : : : : : : : : : : :

: : : : : : : : : : : : :

: : : : : : : : : : : : :

: : : : : : : : : : : : :

: : : : : : : : : : : : :

: : : : : : : : : : : : :

: : : : : : : : : : : : :

: : : : : : : : : : : : :

: : : : : : : : : : : : :

: : : : : : : : : : : : :

: : : : : : : : : : : : :

: : : : : : : : : : : : :

: : : : : : : : : : : : :

: : : : : : : : : : : : :

: : : : : : : : : : : : :

: : : : : : : : : : : : :

: : : : : : : : : : : : :

41 41 43 43 51 62 65 66 68

4 Testing Set Equality
4.1 4.2 4.3 4.4 Introduction : : : : : : : : : The Data Structure : : : : The Analysis : : : : : : : : Directions for Further Work

75
: : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :
75 78 79 83

Bibliography

85

iv

Chapter 1

Introduction
1.1 Amortized Complexity
In many applications of data structures, the data structure is embedded within some algorithm that performs successive operations on it. In these applications, we are interested only in the time taken by the data structure to process operation sequences as a whole and not in the time spent on isolated operations. Amortized data structures are data structures tailored to such applications: these data structures may perform poorly on a few individual operations but perform very well on all operation sequences. The natural performance measure for an amortized data structure is its amortized complexity, de ned to be the maximum cost of operation sequences performed on the data structure as a function of the lengths of the sequences. Amortized data structures are appealing because they dispense with complicated constraints and associated information present in data structures that achieve a fast performance on all operations and they use simple reorganizing heuristics, instead, to achieve a fast amortized performance. Some examples of these data structures are the compressed tree data structures for the Union- nd Problem 1,23,32], the Splay Tree 23,28,32], and the Pairing Heap 16]. Amortized data structures are simple to describe but their performance analysis is often quite involved. Since operation sequences on these data structures are mixtures of operations of varying costs that very nely interact with one another it is tricky to accurately estimate their amortized complexity. Of the three amortized data structures mentioned above only the rst one has been analyzed thoroughly; even its analysis was accomplished only several years after the data structure was originally conceived. The 1

2

CHAPTER 1. INTRODUCTION

complete analysis of the other two is still open. A useful framework for performing amortized analysis involves de ning an appropriate potential function for the data structure 34]. In this framework, each state of the data structure is assigned a real number called its potential. The amortized cost of a data structure operation is de ned to be the actual cost incurred by that operation plus the increase in potential it causes through change of state. The total cost of an operation sequence performed on the data structure equals the total amortized cost of the operations in the sequence plus the decrease in potential from the initial state to the state at the end of the operation sequence. Choosing a suitable potential function that yields a sharp estimate on the amortized complexity is a task that demands ingenuity. We illustrate the potential framework through a simple example. A priority queue with attrition (PQA) is a dynamic set of real numbers supporting two operations: Deletemin deletes and returns the smallest element of the set; Insert(x) deletes all elements of the set greater than x and adds x to the set. A PQA can be represented by a sorted list of its elements. In this representation, Deletemin takes constant time, and Insert takes time proportional to the number of deleted elements. If we de ne the potential of the data structure equal to the number of elements it contains then PQA operations take constant amortized time; PQA operation sequences take linear time. The notions of amortized complexity and amortized cost are usually used in a much wider sense than de ned above. Amortized complexity is usually a maximizing function of several parameters of the operation sequences, instead of their length alone. The amortized costs of operations are usually a set of functions of the operation sequence parameters that, when added together, yield a good estimate of the amortized complexity. For example, the compressed tree data structures for the Union- nd Problem have amortized complexity equal to O(n + m (m + n; n)), and take constant time on Union operations and O( (m + n; n)) amortized time on Find operations, where (m; n) is an inverse function of the Ackerman function, and m and n respectively denote the total number of Finds and the total number of Unions in the operation sequence 23,32]. Let us relate amortized complexity to other measures of data structure performance. There exist data structure problems whose amortized complexities are lower than their worst-case complexities; for instance, the Union- nd Problem is solvable in nearly constant amortized time per operation but requires nearly logarithmic worst-case time per

1.2. OUR WORK

3

operation 7,15,32]. There probably exist problems whose randomized (or average-case) complexities are lower than their amortized complexities, but this is yet to be proven; for instance, the Dictionary Problem and certain other problems that involve testing equality of objects appear to be good candidates for this class. The amortized complexity of a dynamic data structure problem is often intimately related to the complexity of its static version via transformations of solutions/adversaries of one problem into another 6,39]. An appropriate model for proving lower bounds on the amortized complexity of a data structure problem is Yao's cell probe model 38]. This model abstracts out the arithmetic and indexing capabilities of random access machines without ignoring their word-size limitations. The model has a memory consisting of an array of b-bit locations. Data structure operations are performed in a series of memory probes in which the next probe location is always computed as a general function of the values so far read. In this model, Fredman and Saks 15] proved tight lower bounds on the amortized complexity of many problems, including the Union- nd Problem. The only other interesting lower bound known in this model is for a static data structure problem, due to Ajtai 3]. The complexity of many other problems, notably, the Dictionary Problem and the Priority Queue Problem, remains unexplored. This completes our introduction to amortized complexity. Further information on this subject can be found in 23,32,34].

1.2 Our Work
This thesis investigates the amortized complexity of some fundamental data structure problems. We introduce interesting ideas for proving lower bounds on amortized complexity and for performing amortized analysis that enable progress towards resolving some open questions. The problems studied are as follows. In Chapter 2, we study the amortized complexity of the Dictionary Problem. A dictionary is a dynamic set that supports searches, insertions, and deletions of elements. It is an open problem whether a dictionary can be maintained in constant amortized time per operation using space polynomial in the dictionary size; we denote the dictionary size by n. While hashing schemes solve the problem in constant amortized time per oper-

4

CHAPTER 1. INTRODUCTION

ation on the average or using randomness, the best deterministic solution (uses hashing and) takes (log n= log log n) amortized time per operation. We study the deterministic complexity of the dictionary problem under a multilevel hashing model that is based on Yao's cell probe model, and prove that dictionary operations require (log log n) amortized time in this model. Our model encompasses many known solutions to the dictionary problem, and our result is the rst nontrivial lower bound for the problem in a reasonably general model that takes into account the limited wordsize of memory locations and realistically measures the cost of update operations. This lower bound separates the deterministic and randomized complexities of the problem under this model. In Chapter 3, we study a problem arising in the analysis of Splay, a rotation-based algorithm for searching binary search trees that was devised by Sleator and Tarjan. Tarjan proved that Splay takes linear time to scan the nodes of a binary tree in symmetric order; this result is called the Scanning Theorem. More generally, he conjectured that Splay takes linear time to process deque operation sequences on a binary tree; this conjecture is called the Deque Conjecture. We prove that Splay takes linear-times-inverse-Ackerman time to process deque operation sequences. In the process, we obtain tight bounds on some interesting combinatorial problems involving rotation sequences on binary trees. These problems arose from studying a conjecture of Sleator that we refute. We give two new proofs of the Scanning Theorem. One proof is a potential-based proof; Tarjan had originally posed the problem of nding such a proof. The other proof uses induction. In Chapter 4, we study the problem of maintaining a dynamic collection of sets under equality-tests of two sets and under creations of new sets through insertions and deletions of elements. We devise a data structure that takes constant time on equality-tests and logarithmic amortized time on set-creations. The data structure derandomizes a previous randomized data structure, due to Pugh and Teitelbaum, that took logarithmic expected amortized time on set-creations. Some of our work has been published before. The work on the Deque Conjecture was reported in 30]. The work on the Set Equality Problem was reported in a joint-paper with Robert E. Tarjan 31] that also dealt with other related problems.

Chapter 2

The Dictionary Problem
The Dictionary Problem is a classical data structure problem arising in many applications such as symbol table management in compilers and language processors. The problem is to maintain a dynamic set under the operations of search, insertion, and deletion of elements. The problem can be solved in constant time per operation using a bit vector that has a separate bit for each element of the universe indicating its prescence in the set. This simple solution is unsatisfactory since it uses space proportional to the universe size and the dictionary is usually very small compared to the universe. Does there exist a constant-amortized-time solution that uses only space polynomial in the dictionary size? In this chapter, we study the amortized complexity of the dictionary problem under a multilevel hashing model that is based on Yao's cell probe model, and prove that dictionary operations require log-logarithmic amortized time in this model.

2.1 Introduction
The Dictionary Problem is to maintain a dynamic set, called a dictionary, over a nite, ordered universe U under the following operations: location storing x.
Search(x): Determine whether element x is in the dictionary; if so, nd a memory

Insert(x): Add element x to the dictionary. Delete(x): Remove element x from the dictionary.

5

6

CHAPTER 2. THE DICTIONARY PROBLEM

The dictionary is initially the empty set. We would like to know how fast the problem can be solved using only space polynomial in the dictionary size (denoted by n) on a RAM with (log jU j)-bit memory words. Here we are restricting the space used in terms of the dictionary size in order to exclude the trivial bit vector solution and a family of its generalizations, due to Willard 37], that process dictionary operations in constant time and use space depending on the size of the universe. The Dictionary Problem has been extensively studied and has a rich variety of solutions. Balanced search trees solve the problem in O(log n) time per operation and use O(n) space 1,21,23,32]. Self-adjusting search trees such as Sleator and Tarjan's Splay Tree 28] and Galperin and Rivest's Scapegoat Tree 18] take O(log n) amortized time per operation. There is no hope of improving the log n behaviour of search trees since they use only comparisons to perform searches. Hashing schemes solve the problem in constant expected time per operation and use O(n) space. Uniform hashing performs dictionary operations in constant expected time when the operations are randomly chosen from a uniform distribution 21,1]; the space used is O(n). Universal hashing is an improved randomized hashing scheme that performs searches in constant expected time and performs updates in constant expected amortized time 8]; the expectation, here, is over the random hash functions chosen by the algorithm and the bounds apply to all possible operation sequences. Dynamic perfect hashing 13] (see also 2,14]) is a further improvement that performs searches in constant worst-case time and performs updates in constant expected amortized time. All of the above hashing schemes fall under the general category of multilevel hashing schemes. Roughly speaking, a multilevel hashing scheme consists of a hierarchically organized system of hash functions that successively partition the dictionary into ner pieces until all elements in the dictionary have been separated plus an algorithm to update the con guration after each dictionary operation. The fastest deterministic solution to the problem, at present, is a multilevel hashing scheme, due to Fredman and Willard 17], that takes O(log n= log log n) amortized time per operation and uses O(n) space. It has been possible to prove nonconstant lower bounds for the problem on certain deterministic hashing models. Dietzfelbinger et al. 13] showed a tight bound of (log n) on

2.1. INTRODUCTION

7

the amortized complexity of dictionary operations under a wordsize-independent multilevel hashing model that does not include search trees. Mehlhorn et al. 24] strengthened this model so that it includes search trees and showed that dictionary operations have (log log n) amortized complexity under their model. These models assume that memory locations have an unbounded wordsize and overestimate the costs of operations; this simpli es the task of proving lower bounds but the models are not realistic. If memory locations have a su ciently large wordsize, the problem is solvable in constant time per operation (Paul and Simon 25]; Ajtai et al. 4]). When memory locations can only represent a single element of the universe, however, the best available solution is Fredman and Willard's O(log n= log log n)-time solution 17]. We prove a nonconstant lower bound for the Dictionary Problem under a multilevel hashing model, based on Yao's cell probe model, that takes into account the limited wordsize of memory locations and realistically measures the costs of operations. We de ne a generic multilevel hashing model for solving the Dictionary Problem from which various lower bound models for the problem can be derived by specifying suitable cost measures for the operations. The model has a vertically organized memory that consists of a root location at level 1 and an array of at most m locations at level i, for each i 2. Memory locations have b bits each, for some b log jU j. Each memory location stores some c di erent elements of the universe plus a (b ? c log jU j)-bit value that guides search operations; here the number of elements stored at a location varies over time, and is not constant. A search operation locates an element in memory by performing a sequence of memory probes: the rst probe of the sequence always reads the root location and the i-th probe, for i 2, reads a location at level i that is computed as a general function of the sequence of i ? 1 values so far read and the element being searched. The operation either locates the element in some location after a series of probes or concludes that the element is not in the dictionary after a series of unsuccessful probes. A search operation nally replaces the current memory con guration by a new con guration, representing the same dictionary, by computing a general function of the current con guration. An update operation simply replaces the current memory con guration by a new con guration that represents the new dictionary by computing a general function of the current con guration.

8

CHAPTER 2. THE DICTIONARY PROBLEM

We de ne a lower bound model for the problem by imposing a measure of operation costs on the generic model. The Hamming cost of an operation is de ned as the maximum number of locations at any level whose contents change due to the operation. The cost of a search operation is de ned as the number of read probes performed by the operation (called the search cost of the operation) plus the Hamming cost of the operation. The cost of an update operation is de ned as its Hamming cost. When this cost measure is imposed on the generic model we get a lower bound model called the Hamming cost model. We prove our lower bound in the following model that has a di erent cost measure from the Hamming cost model. The search path of an element x of U in a memory con guration C is de ned as the sequence of locations probed by a search operation on x performed in con guration C . We say that an operation refreshes a memory location l if there is some element x in the nal dictionary such that l lies on the search path of x after the operation but l did not lie on the search path of x before the operation. The refresh cost of an operation is de ned as the maximum number of locations at any level that get refreshed by the operation. De ne the cost of an operation as the sum of the search cost and the refresh cost of the operation. The lower bound model with this cost measure is called the refresh cost model. The di erence between this model and the Hamming cost model is that the refresh cost measure is sensitive to locations that participate in rerouting the search paths of dictionary elements during an operation, on the other hand, the Hamming cost measure is sensitive to locations whose contents change. A nonconstant lower bound for the Dictionary Problem in the Hamming cost model would translate into a similar lower bound for the problem in the cell probe model. We believe that such a lower bound exists, but we can only prove a lower bound under the refresh cost model. The refresh cost model seems to be incomparable in power to the cell probe model and to the Hamming cost model. The justi cation for the refresh cost model is that, in realistic hashing schemes, an operation might have to read, and, if necessary, modify, the locations it refreshes in order to correctly reroute the search paths of dictionary elements. The refresh cost model encompasses many of the known solutions to the dictionary problem, but not all of them; for instance, the model includes B-trees, red-black trees, and various hashing schemes, but the class of rotations-based

2.2. SINGLE-LEVEL HASHING MODEL
search trees is not included. Our lower bound is given by:

9

ory locations per level, a universe U , and a wordsize b. Let n be a positive integer satisfying jU j mlog log n . Consider dictionary operation sequences during which the maximum dictionary size is n. Under this model, the amortized complexity of dictionary operations equals (log(log n= log b)).

Theorem 2.1 Consider the refresh cost multilevel hashing model with at most m mem-

In a typical situation where jU j = mloglog n , m = poly(n), and b = log jU j, the theorem yields a lower bound of (log log n) on the amortized complexity of dictionary operations. This lower bound separates the deterministic and randomized complexities of hashing schemes in the refresh cost model, since this model encompasses randomized hashing schemes like universal hashing 8] and dynamic perfect hashing 13] that process dictionary operations in constant randomized amortized time. The proof technique of the theorem can be used to show that single-level hashing schemes in the Hamming cost model require (n ) amortized time to process dictionary operations, for some constant . We hope that the proof technique will be helpful in showing a general nonconstant lower bound for the dictionary problem in the Hamming cost model. The chapter is organized as follows. In Section 2.2, we introduce the basic ideas needed to prove Theorem 2.1 by proving a nonconstant lower bound under the simpler model of single-level hashing. In Section 2.3, we prove the theorem.

2.2 Single-level Hashing Model
In this section, we prove a nearly linear lower bound for the Dictionary Problem under the refresh cost single-level hashing model. We de ne the lower bound model. The model consists of an array of m locations each capable of storing an element of U , a family of at most 2b hash functions from U to the array, and a b-bit root location storing a hash function from the family. The root hash function is always chosen so that it sends the elements of the dictionary into di erent locations, and collisions of elements are forbidden; in general, when a hash function sends

10

CHAPTER 2. THE DICTIONARY PROBLEM

the elements of a set into distinct locations it is called a perfect hash function 14] for the set and it is said to shatter the set. Search operations are performed in two probes: the rst probe reads the hash function from the root location; the second probe checks if the element is present in the array location where it is sent by the hash function. An update operation can change the root hash function and can write into some array locations in order to appropriately relocate the dictionary elements. The cost of a search operation is 2 units. The cost of an update operation is its refresh cost, which equals the number of dictionary elements that are relocated during the operation. The lower bound for single-level hashing is given by:
memory locations, a universe U , and a b-bit root location. Assume that jU j 2m. Consider dictionary operation sequences during which the maximum dictionary size is at most n, where n m. Under this model, the amortized complexity of dictionary operations equals (n=b).

Theorem 2.2 Consider the refresh cost single-level hashing model with an array of m

A typical situation to apply this theorem is when b = log jU j and m and jU j are polynomial in n. Under these assumptions, the theorem yields a lower bound of (n= log n) on the amortized complexity of dictionary operations under the single-level hashing model. The main idea behind the proof of the theorem is an adversary who keeps creating random collisions in U . Any hashing scheme with a small hash functions family can not succeed against this adversary. The proof uses the following sampling lemma, due to Hoe ding 20], that a random sample closely behaves like the whole population.
a population of at least k elements of which some -fraction of the elements are colored red. A random k-subset of the population has more than k red elements with probability at least (1 ? e?c ; k ), where

Lemma 2.1 (Binary Sampling Lemma) Let k 1 and let 0 < < < 1. Consider

c

;

=

(

( ? )2 =(2 (1 ? )) if ? < 1 ? 2( ? )2 otherwise.

Let us prove the theorem. Denote the amortized cost per update operation incurred by a hashing scheme by w. We prove that e (n=w) hash functions are needed by the

2.2. SINGLE-LEVEL HASHING MODEL

11

hashing scheme in order to successfully process all sequences of O(n) insertions. This would imply the theorem. The proof of this result is organized in a series of steps. A hash function is called uniform if it sends the same number of elements into each location. In Section 2.2.1, we prove the result for the case when the hash functions used by the hashing scheme are all uniform and the update cost is bounded in the worstcase. In Section 2.2.2, we handle nonuniform hash functions. In Section 2.2.3, we handle amortized update costs.

2.2.1 Uniform Hash Functions and Worst-case Complexity
In this section, we prove that any single-level hashing scheme in the refresh cost model that uses only uniform hash functions and has worst-case update cost w needs at least e (n=w) hash functions in order to handle all sequences of O(n) insertions. The adversary performs two batches of insertions: a large batch followed by a small batch. The large batch is a random n-subset of U . Let h denote the hash function used after the large batch; h is a random variable. The small batch is constructed as follows: Randomly select k = n=cw locations, where c is a constant. For each selected location pick a random pair of elements of U that h sends into that location. The small batch is the union of these pairs. Since we assumed that jU j 2m and that h is uniform, h sends at least two elements of U into each location. The following lemma gives the lower bound on the size of the hash functions family.

Lemma 2.2 Any hashing scheme requires e
the adversary.

(k) hash functions in order to succeed against

The idea behind the proof of this lemma is that any xed pair of hash functions (h; g ) that are respectively used after the two batches has a low probability of success against the adversary. For if h and g are su ciently similar then g can not shatter the small batch. On the other hand if h and g are su ciently dissimilar then too many elements in the large batch will change locations during the small batch. Proof of Lemma 2.2. Consider a pair of hash functions (h; g) that are respectively used after the two batches. We compute the probability of success of the hashing scheme against the adversary using this pair of hash functions. De ne (h; g ) = the number of elements of U in which h and g di er. Two cases have to be considered:

12

CHAPTER 2. THE DICTIONARY PROBLEM

than n=16 elements that di er in h and g with probability at least (1 ? e?c = ; = n ). Thus the update cost incurred by (h; g ) during the small batch exceeds n=16 with this probability. Setting k = n=32w, the maximum update cost allowed during the small batch equals n=16. Hence Pr (h; g ) succeeds] e?c = ; = n . Case 2. (h; g) jU j=8: A location is called similar if g sends into that location greater than (1=2)-fraction of the elements that h sends into it. At least (3=4)-fraction of the locations are similar locations, since h and g di er in at most (1=8)-fraction of U . By the Binary Sampling Lemma, the random set of k locations selected during the small batch contains more than k=2 similar locations with probability at least (1 ? e?c = ; = k ). Consider a set of k locations, comprising at least k=2 similar locations, that are used to construct the small batch. g shatters a random pair of elements sent by h into a similar location with probability at most 3=4. Hence g shatters a random small batch constructed using the above locations with probability at most (3=4)k=2. Combining the above calculations, Pr (h; g ) succeeds] e?c = ; = k + (3=4)k=2. We are ready to compute the constants.
1 8 1 16 1 8 1 16 3 41 2 3 41 2

Case 1. (h; g) jU j=8: By the Binary Sampling Lemma, the large batch has more

c1=8;1=16 = 1=56; c3=4;1=2 = 1=6; (1=2)ln(4=3) > 1=7: For su ciently large k, the success probability of (h; g ) is at most e?k=8 . It follows that at least ek=16 hash functions are needed by the hashing scheme in order to succeed against
the adversary.

2.2.2 Nonuniform Hash Functions
In this section, we extend the lower bound of the previous section to families of nonuniform hash functions. The adversary once again inserts a large batch which is a random n-subset of U and then inserts a small batch. The small batch is constructed based on the hash function h that is used by the hashing scheme after the large batch. A multiple location of h is a location into which h sends two or more elements of U . Focus on the subuniverse U of elements of U that h sends into its multiple locations. Select a random k-subset of U , for k = n=cw. For each element of the subset select a random element of U that collides with it under h. The small batch consists of the subset and the elements selected.

2.3. MULTILEVEL HASHING MODEL

13

Let us see why Lemma 2.2 still holds for this adversary. Once again the idea is to show that any xed pair of hash functions (h; g ) has a low probability of success. The case when (h; g ) jU j=8 is handled as before. Consider the case (h; g ) jU j=8. Since jU j jU j=2, h and g di er in at most (1=4)-fraction of U . An element of U that is sent by both h and g into a similar location is called a similar element. At least (1=4)fraction of U are similar elements. By the Binary Sampling Lemma, we can expect at least k=8 elements of the k-subset from which the small batch is constructed to be similar elements. Now if two of these similar elements collide under h then g fails to shatter the small batch. So suppose that h and g send all the similar elements of the small batch into di erent locations. In this case, as in the previous section, it is easy to see that g fails to shatter the small batch with probability greater than (1=2)k=8. This completes the second case and the proof that e (k) hash functions are needed to succeed against the adversary.

2.2.3 Amortization
In this section, we incorporate amortization into the previous section's argument. Let w denote the amortized cost per update operation incurred by the hashing scheme. The adversary of the previous section is modi ed by performing a greedy sequence of insertions between the two batches. Immediately after the large batch, the adversary performs a maximal sequence of insertions such that incurs an update cost of more than 2wj j. Then the small batch is performed as before based on the hash function h used after . Observe that j j is at most n, so only O(n) insertions are totally performed. The maximality of ensures that the total update cost incurred during the small batch is at most 4wk. Hence we can apply the argument of the previous section to obtain a lower bound on the hash functions family.

2.3 Multilevel Hashing Model
In this section, we prove a log-logarithmic lower bound for the Dictionary Problem under the refresh cost multilevel hashing model. The main idea behind the proof is a randomized adversary who alternately performs greedy searches of the dictionary elements and creates random collisions at the various

14

CHAPTER 2. THE DICTIONARY PROBLEM

levels of the multilevel hashing scheme, descending the levels of the scheme. The collisions force the scheme to either incur a large cost on searches or incur a large cost in compressing the dictionary to few levels. The collisions are created in batches of insertions. Each batch is constructed by selecting a set of locations from the rst i levels, by focusing on the subuniverse of elements of U whose search paths involve just these locations during the rst i probes, and by picking a random subset from the subuniverse of appropriate size; the subset is always chosen to be several times larger than the number of selected locations in order to create collisions. We sketch the lower bound proof. Let us con ne ourselves to worst-case complexity since amortized complexity can be easily handled, as in the single-level hashing lower bound, by appropriately performing greedy searches and greedy insertions during the adversary sequence. The adversary is de ned recursively on levels, and the proof has an inductive structure that is reminiscent of a previous lower bound for a static data structure problem in the cell probe model, due to Ajtai 3]. In order to carry out the induction, we need to prove a stronger result that applies to a more general hashing model, called the partial hashing model. In a partial hashing scheme, each value of the root location determines a working subuniverse of U on which the scheme supports dictionary operations. The lower bound applies to partial hashing schemes that work, occasionally, on a dense subuniverse of U ; we show that such schemes fail, almost surely, against the adversary. The main feature of the proof is the handling of nonuniform root hash functions. The value stored at the root location of the hashing scheme de nes a partial hash function which is essentially the second probe function used by the scheme to perform searches. We say that this hash function is narrow if it sends a constant fraction of the universe into a small set of level-2 locations; otherwise the hash function is said to be wide. The adversary rst recursively performs a narrow phase of insertion batches in U that force the scheme to use narrow hash functions and then recursively performs a wide phase of much smaller insertion batches within a random subuniverse U of U . The wide phase is not always performed; it is performed only if the narrow phase gets prematurely truncated because the hashing scheme has stopped using narrow hash functions. The adversary consists of two di erent phases because the hashing scheme behaves di erently depending on whether it mostly uses narrow hash functions or it mostly uses wide hash

2.3. MULTILEVEL HASHING MODEL

15

functions and two phases are needed to fool all hashing schemes. We show that the probability of success of the hashing scheme through the completion of either of the phases is small. We analyze the narrow phase using induction; we analyze the wide phase by showing that xed sequences of root hash functions used during this phase have a low success probability, using some random sampling lemmas and induction. The proof of the lower bound is organized as follows. In Section 2.3.1, we describe the partial hashing model. In Section 2.3.2, we describe the adversary used for proving a lower bound on worst-case complexity. In Section 2.3.3, we state and prove two technical random sampling lemmas needed to analyze the wide phase. In Section 2.3.4, we prove the worst-case lower bound. In Section 2.3.5, we handle amortized complexity.

2.3.1 Partial Hashing Model
In this section, we describe the partial hashing model. A partial hashing scheme is a hashing scheme that processes dictionary operations in a tower of universes U1 U2 Uk . Uk is called the working universe of the scheme. The scheme has a vertically organized memory consisting of a (Wb)-bit root location and an in nite word-size advice location at level-1, and an array of at most m b-bit locations at each level i 2; we require that b log jU1j so that a location can store any element of the universes. Each possible value v of the root location de nes a tower of subuniverses S1 (v ) S2(v ) Sk (v) such that Si (v) Ui for all i. Sk (v) is called the working subuniverse corresponding to value v . A search operation starts by probing the root location; if the element being searched is in the current working subuniverse, then the search proceeds downwards as in the standard multilevel hashing model; if the element is not in the current working subuniverse, then the search operation probes the advice location and continues downwards in the standard fashion. An update operation changes the memory con guration; a search operation can also change the memory con guration. The search cost of an operation is de ned as the number of read probes performed by the operation, not counting probes on the advice location. The refresh cost of an operation is a suitably de ned number that is at least the maximum number of locations at any level that get refreshed by the operation. The cost of an operation is de ned to be the sum of its search cost and its refresh cost. This completes the description of the model.

16

CHAPTER 2. THE DICTIONARY PROBLEM

In order to prove a lower bound for partial hashing schemes, we have to require these schemes to use dense subuniverses, at least occasionally. The density of a set S T in T equals jS j=jT j; S is said to be -dense in T if S has a density of at least in T . Let = ( 1; 2; . . . ; k ) be a vector of values in the interval 0; 1], let e be a positive integer, and let H be a partial hashing scheme. A con guration C of H is said to be -dense if the subuniverses S1 (v ) S2 (v ) Sk (v) corresponding to con guration C have respective densities 1 ; 2; . . . ; k in universes U1 ; U2; . . . ; Uk . A con guration C of H is said to be ( ; e)-good if there is an extension sequence of at most e insertions in U1, starting from C , after which H is in a -dense con guration; otherwise C is said to be ( ; e)-bad. H is said to be ( ; e)-good if H always uses ( ; e)-good con gurations. Our lower bound applies to partial hashing schemes that are ( ; e)-good.

2.3.2 Adversary
In this section, we describe a randomized adversary for proving a lower bound on the worst-case complexity of good partial hashing schemes. We de ne an adversary Ar ;n;w;b against a partial hashing scheme H with a tower of universes U1 U2 Uk and a working universe U = Uk that has been partitioned into n equal-sized blocks; here = ( 1 ; 2; . . . ; k ). The adversary is tailored against ( ; e)-good partial hashing schemes with worst-case search cost r and worst-case update cost w, but it is de ned against any partial hashing scheme; we will de ne e later. The adversary either performs a complete sequence of O(n) insertions on the initial dictionary leaving H in a -dense con guration or performs a truncated sequence of operations which could not be completed because the hashing scheme has entered an ( ; e)-bad con guration. We need some de nitions. Let p be a positive integer, let 2 0; 1], and let h be a ~ partial hash function from a universe U to an array of locations. The domain of h is denoted by dom(h). A random ( ; p)-sample from h is a random subset R of dom(h) constructed as follows. First delete from dom(h) all the elements that go into locations ~ where h sends less than an ( p)-fraction of U ; then pick a random p-subset S from dom(h); for each location into which h sends k elements of S , pick a random subset with ~ density k in U that h sends into that location; R is the union of the subsets picked from the various locations. A partial hash function is said to be ( ; W )-narrow, for some

2.3. MULTILEVEL HASHING MODEL

17

into any single location. We can prune a partial hash function and make it -biased, for any given 2 0; 1], by deleting su ciently many elements from its domain. We are ready to de ne the adversary. The adversary rst inserts a random n-subset of U that is formed by picking a random element from each block of U (called the rst batch ) and then performs a phase of insertions, called the tail phase. The tail phase is de ned recursively on r: Basis. r = 1: If there exists an extension sequence consisting of at most e = n insertions in U1 taking H to a -dense con guration, perform and announce completion; otherwise H is in a ( ; e)-bad con guration, so announce truncation. Induction Step. r 2: We rst perform a recursive subphase, called the narrow phase; if this phase gets truncated we perform another recursive subphase, called the wide phase. The adversary announces completion if one of the two phases completes; otherwise the adversary announces truncation. The two phases are performed as follows: Narrow Phase: Let W1 be a suitably de ned positive integer. We construct a new hashing scheme H1 from H , having a tower of universes U1 U2 Uk = Uk+1 , by collapsing the top two levels of H into a single level. Each possible value stored at the root location of H de nes a partial hash function from Uk to the set of level-2 locations which equals the second probe function used by search operations when that value is stored at the root. We rank the level-2 locations of H according to each partial hash function h used by H at its root location as follows. The i-th location of a partial hash function h from a domain D U to the set of level-2 locations is de ned to be the location into which h sends the i-th largest subset of D; we resolve ties in favor of the location with the smallest index. The root location of H1, at any time, consists of the root location of H juxtaposed with the rst W1 =2 level-2 locations of the current root partial hash function (this set of locations is denoted by L1 ); the advice location of H1 consists of the advice location of H juxtaposed with the remaining level-2 locations of H ; the i-th level of H1, for i 2, coincides with the (i + 1)-st level of H . The working subuniverse of H1, at any time, is the subset of the working subuniverse of H that the root hash function of H maps into the set of locations L1; the tower of subuniverses of

~ 2 0; 1] and some positive integer W , if it sends at least an -fraction of U into some set of W locations; otherwise the hash function is said to be ( ; W )-wide. A partial hash ~ function is said to be -biased, for some 2 0; 1], if it sends at most a -fraction of U

18

CHAPTER 2. THE DICTIONARY PROBLEM

this de nition of refresh cost is more liberal than the usual de nition of the refresh cost as the maximum number of locations at any level that get refreshed. The narrow phase of the adversary Ar ;n;w;b against H is recursively de ned to be the 1 tail phase of the adversary Ar?;n;w;b against H1, starting from the same con guration as H 's con guration prior to the narrow phase; here 1 = ( 1 ; 2; . . . ; k ; k =2). The narrow phase completes if the recursive adversary announces completion; otherwise the narrow phase is truncated. The narrow phase always forces H to use ( k =2; W1=2)-narrow root hash functions; if the phase gets truncated then H will always use ( k =2; W1=2)wide root hash functions in any -dense con guration during the next e1 insertions in U1 ; we will specify e1 later. Wide Phase: The wide phase consists of two subphases: the rst phase incrementally constructs a random subuniverse Uk+1 U and alternately performs random insertion batches in Uk+1 and extension batches in U1 ; the second phase recursively performs further random insertion batches in Uk+1 and extension batches in U1 . The wide phase completes either if the second phase completes or if the second phase gets truncated but H is in an ( ; e)-good con guration following the phase (in the latter case, the wide phase is completed by performing a suitable extension sequence in U1 that takes H to a -dense con guration); otherwise the wide phase is truncated. We can prune every root hash function used by H in a -dense con guration during the wide phase by deleting from its domain a subset of density at most ( k =2) in U and make it ( k =W1)-biased since these hash functions are ( k =2; W1=2)-wide. Let = k , let W2 and e2 be suitably chosen positive integers, and let = ( 2 =64W2m). The two subphases are performed as follows: First Phase: We maintain a pair of sets U 1 and U 2 U 1 that are initially the empty sets and repeat the following step as many times as possible: Step: If there is an extension sequence of at most e2 insertions in U1 following which H is in a -dense con guration and H 's pruned root hash function has a domain D such that DnU 1 is ( =4)-dense in U , then perform and continue the step; otherwise
1

H1 , at any time, consists of the tower of subuniverses of H followed by H1's working subuniverse. Operations are performed by H1 by simulating the behaviour of H . The search cost of an operation on H1 is de ned in the usual way. The refresh cost of an operation on H1 is de ned equal to the refresh cost of that operation on H . Notice that

2.3. MULTILEVEL HASHING MODEL

19

terminate the step. This ensures that, in any -dense con guration of H during the next e2 insertions in U1 following the rst phase, the domain of H 's pruned root hash function will always intersect U 1 in a ( =4)-dense subset of U . Let h be the pruned root hash function used by H following , and let D0 be a domain of density ( =4) in U that is disjoint to U 1 and on which h is de ned. We insert D0 into U 1 , pick a random ( ; W2=2)sample U 3 from hjD0 and insert it into U2, and, nally, insert a random ( e2=8)-subset S of U 3 into the dictionary. The set S is constructed by uniformly partitioning U 3 into ( e2 =8) equal blocks in any way and picking a random element from each block. This completes the description of the step. Second Phase: Let Uk+1 = the value of set U 2 at the end of the rst phase, let L2 = the set of level-2 locations from which the samples U 3 were constructed during the steps of the rst phase, and let n0 = the total number of random elements inserted into the dictionary during the rst phase. The second phase is performed only if Uk+1 6= ; otherwise the second phase is truncated. We construct a new hashing scheme H2 having a tower of universes U1 U2 Uk Uk+1 by collapsing the top two levels of H , by appending the set of locations L2 to the root location of H , and by appending the remaining level-2 locations to the advice location of H . The working subuniverse of H2, at any time, is the subset of Uk+1 that H 's pruned root hash function sends into the locations of L2 . Operations on H2 are performed by simulating H 's behaviour; the costs of operations on H2 are de ned analogous to H1. 1 The second phase is recursively de ned as the tail phase of adversary Ar?;n0 ;w;b against H2 ; here 2 = ( 1; 2; . . . ; k ; k =32). This essentially completes the de nition of the tail phase and of the adversary. We now mention some details that had been omitted in the de nition of the wide phase. During the wide phase, often, the root hash function has to be restricted to a subdomain such as when pruning a root hash function or when choosing an appropriate subdomain D0 of a pruned root hash function h during a step of the rst phase. These restrictions are performed in a unique way. We prune every root hash function in a unique way depending only on the hash function and on the bias . We choose domain D0 during a step of the rst phase in a unique way depending only on the pruned hash function h and U 1. In the construction of the random subsets S U 3 during the rst phase, we uniformly partition U 3 in a unique way depending only on its value.
2

20

CHAPTER 2. THE DICTIONARY PROBLEM
2

The size of the universe reduces by a factor of 128m= 2 when carrying out the recursion during the wide phase. We need jU j (32)r (128m)rn= 2r to ensure that the universe has at least n elements by the time the adversary reaches the r-th level. The parameters e, e1 , e2 , W1 , and W2 are de ned as functions of the adversary parameters r, , and n using the following recurrence relations: ( r?1 e ( =32; er ( ; n)=8) if r 2 r ( ; n) = 2 (2.1) e n otherwise

er ( ; n) = er?1 ( =2; n) 1 er ( ; n) = W1r ( ; n)=(c0w) 2 W1r ( ; n) = W r?1 ( =2; n) ( r W2 ( ; n) =(crb) if r 2 r ( ; n) = 1 W n=c b otherwise W2r ( ; n) = W r?1 ( =32; er( ; n)=8) 2
1

(2.2) (2.3) (2.4) (2.5) (2.6)

The constants c0 and c1 used in these recurrences will be speci ed later. We obtain a recurrence involving W alone by eliminating the other parameters: 8 r? < W ( =32; W r? w = ;n ) c if r 2 W r ( ; n) = : cr b n=c1b otherwise
1 2 8 0 1( 2 ) 1

This recurrence has the following solution:

W r ( ; n) = n

2r+1 ?3 : 2 (64)(r?1)(5r?8)=2c1r+1 ?r?2 b2r ?1 (8c0w)2r?1?1

Back-substituting this solution into the above recurrences, we nd the values of parameters e, e1 , e2, W1 , and W2 to be approximately n( =wb)2r . The adversary de nition requires all the parameters to be at least 1. We need n to be su ciently large (n (wb= )2r ) to guarantee this. We state some useful facts about the adversary. These facts can be proved using the de nition of the adversary and induction.

Lemma 2.3 i. W r ( ; n) W2r ( ; n)=2 W1r ( ; n)=2, for all r, , and n.
ii. (6= )er ( ; n) er ( ; n), for all r, , and n. 2 1

2.3. MULTILEVEL HASHING MODEL

21

Lemma 2.4 i. The maximum number of insertions performed by Ar ;n;w;b is at most 3n.
ii. The maximum number of random insertion batches performed by Ar ;n;w;b is at most (34)r?1= . iii. The maximum number of insertions performed by Ar ;n;w;b during the second phase is at most e2 . iv. The maximum number of insertions performed by Ar ;n;w;b during the wide phase is at most (6= )e2 e1 .

Lemma 2.5 i. A complete adversary sequence leaves the hashing scheme in an -dense
ii. Whenever the adversary performs a random insertion batch, the hashing scheme is in a -dense con guration.

con guration; a truncated adversary sequence leaves the hashing scheme in an ( ; e)-bad con guration.

iii. The hashing scheme always uses ( =2; W1=2)-wide root hash functions in a -dense con guration during the wide phase of the adversary.

2.3.3 Two Random Sampling Lemmas
The analysis of the wide phase uses two technical lemmas for analyzing the behaviour of random samples under a sequence of partial hash functions, so, rst, in this section, we state and prove these lemmas. We need some de nitions before stating the lemmas. Consider partial hash functions from a universe U to an array of m locations. An -hash function, for any 2 0; 1], is a partial hash function that is de ned on a domain of density in U . A sequence of partial hash functions is called a hashtopy; we think of a hashtopy as a deformation of a partial hash function over time, where time signi es the integers from 1 to the length of the hashtopy. For a hashtopy H, Ht denotes the t-th partial hash function in the hashtopy. A hashtopy consisting of only -hash functions is called an -hashtopy; a -biased hashtopy is de ned analogously. Consider a hashtopy H. A location snap of H is a pair (l; t), where 1 l m and 1 t jHj. A set S U refreshes a location snap (l; t) of H if, for some element x 2 S , H sends x to location l at time t and H had

22

CHAPTER 2. THE DICTIONARY PROBLEM

sent x to a di erent location the last time before t when x appeared in H. The refresh cost incurred by a set S U in H is de ned as the total number of locations snaps of H refreshed by S . The oscillation of an element x 2 U in H is de ned as the refresh cost incurred by x in H. The oscillation of H is de ned as the mean oscillation of an element of U in H. A xed element of H is de ned as an element whose oscillation in H equals 0; a xed subset of H is de ned analogously. Our rst lemma estimates the refresh cost incurred by a random sample in a biased hashtopy when the sample is constructed by uniformly partitioning the universe and sampling each partition independently.
verse U to an array of m locations. Let T = jHj, let n 1= be a positive integer, and let ! = the oscillation of H. Partition U into n equal-sized blocks, and select a random n-subset R from U by picking a random element from each block. R incurs a refresh cost of at least !=4 in H with probability at least (1 ? e?(n! )=(16(T ?1))).

Lemma 2.6 (Refresh Cost Lemma) Consider a -biased hashtopy H from a uni-

Our second lemma says that a random sample from a low oscillation -hashtopy is likely to intersect the domains of the hash functions in the hashtopy in dense xed subsets.
a universe U to an array of m locations in which the domains of h1 ; h2; . . . ; hp are all disjoint. Suppose that the oscillation of H is at most (1=2p). Let k be a positive integer, let (1=4kmp2), and suppose that jU j 1= . Construct a random sample R of U by picking a random ( ; k)-sample from each of the hash functions h1; h2 ; . . . ; hp and taking the union of these samples. Let F = the set of elements of U that are left xed by H. With probability (1 ? 2qe?k=192), F \ R \ dom(hi ) is a (1=8p)-dense subset of R, for all i p + 1.

Lemma 2.7 (Density Lemma) Let H = (h1; h2; . . . ; hp+q) be a (1=p)-hashtopy from

We need some further lemmas for proving the above lemmas.

Lemma 2.8 (Martingale Lemma) Let n be a positive integer and let 0 < < < 1.

Let X1 ; X2; . . . ; Xn be a sequence of random variables in the range 0; 1] that are exposed

2.3. MULTILEVEL HASHING MODEL
one by one and satisfy the following relation:

23

E X1] + E X2jX1] + E X3jX1; X2] +
Pr X1 + X2 + + Xn Sampling Lemma.

+ E XnjX1; X2; . . . ; Xn?1 ]
; n ),

n:

n]

(1 ? e?c

where c

;

was de ned in the Binary

when the random variables are mutually independent and have xed means. We show that E eh(X +X + +Xn )] (1 ? + eh )n; for all h 0,
1 2

Proof. We generalize the proof of Hoe ding's inequality 20] that gives the lemma

and then complete the proof of the lemma as in Hoe ding's inequality. We prove this statement by induction on n using Hoe ding's ideas, namely the convexity of ex and the inequality between arithmetic and geometric means. Basis. n = 1: For any x in the range 0; 1], the convexity of ehx gives

ehx E ehX ]
1

1 ? x + xeh ; so taking expectations, we get 1 ? E X1] + E X1]eh 1 ? + eh ; since h 0.

sequence X2 ; . . . ; Xn:

Induction Step. n 2: The idea is to expose X1 rst and apply induction to the
E eh(X +
1

+Xn ) ]

= EX ehX EX ;...;Xn eh(X + +Xn )jX1]] ?E EX ehX (1 ? n n ? 1X1] (1 ? eh ))n?1 ] (by induction) (1 ? E X1](1 ? eh ))(1 ? n ? E X1] (1 ? eh ))n?1 n?1 hx ) (by convexity of e (1 ? + eh )n (by the arithmetic and geometric means inequality).
1 1 2 2 1 1

This completes the proof of the lemma.

24

CHAPTER 2. THE DICTIONARY PROBLEM

Lemma 2.9 (Fractional Sampling Lemma) Let k1; k2; . . . ; kt be positive integers with
sum k, let 1 ; 2; . . . ; t be values in the interval 0; 1] with weighted mean = (k1 1 + + kt t )=k, and let 0 < < . Consider a family of disjoint populations U1 ; U2; . . . ; Ut of values in the interval 0; 1] with means 1 ; 2; . . . ; t, respectively. Construct a random k-subset R by picking a random ki -subset from Ui , for each i, and taking the union of these subsets. R has a mean greater than with probability at least (1 ? e?c ; k ), where c ; was de ned in the Binary Sampling Lemma.

from U1 , Y21 ; Y22; . . . ; Y2k from U2, and so on. De ne a set of independent random variables fXij j1 j ki g as follows: Xij is simply a random value chosen from Ui . A result of Hoe ding 20] (Theorem 4) says that X X Ef ( Yij ) Ef ( Xij )
2

Proof. Suppose R is constructed by selecting a sequence of random values Y11; Y12; . . . ; Y1k

1

j

j

for any convex function f and for all i. For all real numbers h, we have: P Y h Pj Yij Ee Eeh ij Yij = i P (as f j Yij ji = 1; . . . ; tg are mutually independent) Y h Pj Xij = (by convexity of ehx and by Hoe ding's result) Y hXij (since Xij are mutually independent). We use this inequality and complete the proof of the lemma as in Hoe ding's inequality 20]. We are ready to prove the main lemmas of this section. Proof of the Refresh Cost Lemma. The basic idea behind the proof is to construct the random sample R incrementally and use the Martingale Lemma. Let U1 ; U2; . . . ; Un denote the blocks of the partition of U . Construct R incrementally by randomly selecting elements from the blocks, one by one. Denote the set of rst i elements added to R by Ri . For each i 2 f1; 2; . . . ; ng, de ne a random variable Xi =
ij i

Ee

Ee

2.3. MULTILEVEL HASHING MODEL

25

the refresh cost incurred by Ri in H minus the refresh cost incurred by Ri?1 in H. The refresh cost incurred by R in H equals X1 + X2 + + Xn . In order to apply the Martingale Lemma, we construct a sequence of random variables fYiji = 1; . . . ; ng whose sum has the same distribution as the sum of the Xis for small values of the sums: ( X if X1 + Yi = T i? 1 otherwise. + Xi !=2 P P P P P X always. It Observe that i Yi = i Xi whenever i Xi !=2 and that i Yi i i P Y exceeds !=4 equals the probability that P X follows that the probability that i i i i exceeds !=4 . We normalize the Yi s to the interval 0; 1] and form new random variables Zi = Yi =(T ? 1), for all i. The following lemma says that the Zi s satisfy the condition of the Martingale Lemma.

Lemma 2.10

E Z1] + E Z2jR1] +

+ E ZnjR1; R2; . . . ; Rn?1]

!n : 2(T ? 1)

By the Martingale Lemma and using n 1= , we conclude that the probability that P Z exceeds !=(4 (T ? 1)) is at least (1 ? e?(n! )=(16(T ?1))). The Refresh Cost Lemma i i follows immediately. It remains to prove Lemma 2.10. Proof of Lemma 2.10. We need some de nitions. For any set S U and element x 2 U , the oscillation of x modulo S is de ned as the refresh cost incurred by S fxg minus the refresh cost incurred by S . For any pair of sets S; T U , the oscillation of T modulo S , denoted !S (T ), is de ned as the mean oscillation of an element of T modulo S. Consider the construction of the sample R by adding elements from the blocks, one by one. De ne:

!i = (!Ri? (Ui) + !Ri? (Ui+1) + + !Ri? (Un))=n; and = maxftjX1 + X2 + + Xt !=2 g:
1 1 1

We have

! +1 (n ? )(T ? 1)=n = (E Z +1jR ] + E Z +2jR +1 ] +

+ E Zn jRn?1 ])(T ? 1)=n:

26 For any i , we have

CHAPTER 2. THE DICTIONARY PROBLEM
!i ? !i+1 !Ri? (Ui )=n + !Ri? (U ) ? !Ri (U ) E ZijRi?1](T ? 1)=n + Xi
1 1

(as each newly refreshed location snap at step i reduces the oscillation of at most a -fraction of U ). Summing i from 1 to , we get

! = (!1 ? !2) + (!2 ? !3 ) + + (! ? ! +1 ) + ! +1 (E Z1] + E Z2jR1] + + E ZnjRn?1 ])(T ? 1)=n + (X1 + X2 + (E Z1] + E Z2jR1] + + E ZnjRn?1 ])(T ? 1)=n + !=2:

+X )

The lemma follows from this inequality. This completes the proof of the Refresh Cost Lemma. Proof of the Density Lemma. Since the oscillation of H is at most 1=2p, it follows that jF j (1 ? 1=2p)jU j. Thus F \ dom(hj ) has a density of at least 1=2p in U , for all j . We complete the proof of the lemma by showing that the intersection of R with any xed (1=2p)-dense subset of U is a (1=8p)-dense subset of R with probability (1 ? 2e?k=192 ). Let S be any (1=2p)-dense subset of U . We want to estimate the probability that R \ S is a (1=8p)-dense subset of R. Let D denote the set of elements that are deleted from the domains of hash functions h1 ; . . . ; hp when R is constructed by taking ( ; k)samples of these hash functions. Since (1=4kmp2), it follows that jDj jU j=4p. De ne S1 = S nD; S1 is a (1=4p)-dense subset of U . We show that S1 \ R is likely to be (1=8p)-dense in R using two successive applications of the Fractional Sampling Lemma. Let us review the construction of R. R is constructed by picking a random k-subset from each of the sets Ui = dom(hi )nD, for i p, by forming the union R1 of these subsets, by picking dense subsets of U that go into the same locations as the elements of R1, and by forming the union of these dense subsets. For each element x 2 dom(hi ), de ne ?1 value(x) = jhi (hi (x)) \ S1 j : jh?1(hi(x))j i We have

Ex2Ui value(x)

Ex2dom(hi)value(x); and

2.3. MULTILEVEL HASHING MODEL 27 P E value(x) i x2Ui Ex2U value(x) 1=4p: p By the Fractional Sampling Lemma, it follows that R1 has a mean value of at least 1=6p with probability (1 ? e?k=72 ). We estimate the probability that R \ S1 is (1=8p)-dense in R, given that R1 has a mean value of at least 1=6p. For all i 2 f1; 2; . . . ; pg and all l 2 f1; 2; . . . ; mg, de ne
Ui;l = h?1 l and i ki;l = jR1 \ Ui;l j:
De ne the characteristic function
S1

of set S1: ( (x) = 1 if x 2 S1 0 otherwise
S1

Since the mean value of R1 is at least 1=6p, it follows that P k E i;l i;l x2Ui;l S (x) 1=6p: Since R is formed by picking a random (ki;l jU j)-subset of Ui;l and taking the union of these subsets, by the Fractional Sampling Lemma, it follows that R \ S1 is a (1=8p)-dense subset of R with conditional probability (1 ? e?k=192 ), given that R1 has a mean value 1=6p. We conclude that R \ S1 is a (1=8p)-dense subset of R with probability (1 ? ?k=192). This completes the proof of the lemma. 2e

kp

1

2.3.4 The Worst-case Lower Bound
In this section, we analyze the adversary de ned in Section 2.3.2 and prove a lower bound of (log(log n= log b)) on the worst-case cost of dictionary operations in the refresh cost multilevel hashing model, where n = the maximum dictionary size during the operation sequences. Let H be any partial hashing scheme. We say that H succeeds on a sequence of operations performed by adversary Ar ;n;w;b if is a complete sequence of operations, the maximum cost of an update operation in is at most w, and the maximum level of a dictionary element during is at most r.

28

CHAPTER 2. THE DICTIONARY PROBLEM

The following lemma bounds the success probability of a partial hashing scheme against the adversary.

Lemma 2.11 Let = ( 1; 2; . . . ; k ) be a sequence of values in the interval 0; 1], let
=
k,

and let W = W r ( ; n) 1. Let H be a partial hashing scheme that has a (Wb)-bit root location and b-bit locations at levels 2. H succeeds against Ar ;n;w;b with probability e?W b .

The lemma gives a trade-o between the worst-case costs of search operations and update operations incurred by a hashing scheme. Let H be a multilevel hashing scheme in the refresh cost model with wordsize b that incurs a worst-case cost of r on searches and a worst-case cost of w on updates in processing sequences of O(n) operations. H has the following trade-o between r, w, and b:

w = (n1=2r =b): This trade-o gives a lower bound of (log(log n= log b)) for maxfr; wg.
The rest of this section is devoted to proving Lemma 2.11. The proof is by induction on r. Let U1 U2 Uk = U be the tower of universes of H . Basis. r = 1: Following a successful adversary sequence, the working subuniverse of H has density in U . Let S (v ) be a xed -dense working subuniverse used by H following a successful adversary sequence. By the Fractional Sampling Lemma, the random rst batch has n=4 elements in S (v) with probability (1 ? e? n=16 ). The root location can store at most Wb = n=c1 distinct elements of U , so if c1 > 4, some element of the rst batch is stored at a level 2 with this probability. Since the root location can store at most 2 n=c distinct values v , the success probability of H is 2 n=c e? n=16 . We choose c1 32 so that the success probability of H is e? n=c . Induction Step. r 2: We estimate the probability that H succeeds against the adversary:
1 1 1

Pr success] = Pr narrow phase completes successfully] + Pr wide phase completes successfully] If the narrow phase completes successfully then the induced hashing scheme H1 1 succeeds against its adversary Ar?;n;w;b . Thus, by induction, the rst term is bounded by e?W b .
1 1

2.3. MULTILEVEL HASHING MODEL

29

We bound the second term by showing that any xed sequence of root hash functions H = (h1; h2; . . . ; hl) used before the random insertion batches during the wide phase has a low probability of success; actually, here hl denotes the root hash function used at the end of the adversary sequence and hl?1 denotes the root hash function used before the last random insertion batch. The hash functions hi are all ( =2; W1=2)-wide, so they can be pruned to obtain ( =W1)-biased hash functions gi by deleting subsets of density =2 in U from their domains. The gis are ( =2)-hash functions. We apply the incremental construction of the random subuniverse Uk+1 during the rst phase to the sequence (g1; g2; . . . ; gl) and determine the pre x (g1; g2; . . . ; gp) of the sequence from which Uk+1 is constructed through random sampling. When sampling from a pruned hash function gi , we restrict gi to a subdomain D0 of density =4 in U and sample from the restriction fi = gi jD0 . The domains of the restrictions fi , for 1 i p, are all disjoint and the union of these domains equals U 1 . The domains of the hash functions gj , for j p +1, intersect U 1 in a ( =4)-dense subset of U , since, otherwise, the construction of Uk+1 would have also involved gj . We restrict each hash function gj , for j p +1, to the subdomain dom(gj ) \ U 1 and obtain a ( =4)-hash function fj . Consider the hashtopy F = (f1; f2; . . . ; fl) over universe U 1. Two cases arise: Case 1. The oscillation of F is at least =8: By the Refresh Cost Lemma, since F is a ( =W1)-biased hashtopy, the rst batch of the adversary incurs a refresh cost of at least W1=32 in F with probability at least (1 ? e?(n =128l)). We choose c0 > 192 so that the total refresh cost available during the wide phase is at most 6e2 w= < W1 =32. The probability of success of H is e?(n =128l). Case 2. The oscillation of F is at most =8: Uk+1 is formed by picking (4 = p; W2=2)samples from the hash functions fi , for i p, and taking the union of these samples; here we have scaled to convert densities from U to U 1. F is a (1=p)-hashtopy over U 1, the oscillation of F is at most 1=2p, and (4 = p) (1=4kmp2). Let F = the set of elements of U 1 that are left xed by F . By the Density Lemma, with probability (1 ? 2le?W =384), F \ Uk+1 \ dom(hi ) is ( =32)-dense in Uk+1 , for all i p + 1. We call this property of Uk+1 as the density property. Fix a sequence of insertions performed by the adversary prior to the wide phase and x a subuniverse Uk+1 chosen by the adversary with the density property. Under these conditions, if H succeeds against the adversary, then the induced hashing scheme
2

30

CHAPTER 2. THE DICTIONARY PROBLEM
2

1 H2 succeeds against its adversary Ar?;n0 ;w;b ; the second phase can not get truncated because Uk+1 has a dense xed intersection with dom(hl ). By induction, under the above conditions, H succeeds against the adversary using H with probability e?W b . In both cases, the probability that H succeeds using root hashtopy H is at most
2

maxfe?(
1

n=128l); (2l + 1)e?W2 =384g

e?W =500;
2

for su ciently large c1. The total number of root hashtopies H available is at most 2W b(34)r? = . If we let W (W2 =1000(34)r?1b) (by making c1 large enough), then the probability that H successfully completes the wide phase is at most e?W =1000. The probability that H succeeds against the adversary is at most e?W b + e?W =1000 e?W b , since W is small relative to W1 and W2. This completes the proof of the lemma.
2 1 2

2.3.5 Amortization
In this section, we prove a lower bound of (log(log n= log b)) on the amortized cost of dictionary operations in the refresh cost multilevel hashing model, where n = the maximum dictionary size during the operation sequences. Any hashing scheme H with an amortized cost of r on searches and an amortized cost of w on updates can be converted into a hashing scheme H 0 with a worst-case cost of r on searches and an amortized cost of w on updates. H 0 simulates the behaviour of H in processing all the operations, but always stores the dictionary elements in the rst r levels. A search operation is performed by H 0 by simulating H , but H 0 does not change the memory con guration even if H does. An update operation is performed by H 0 by simulating H and then compressing the dictionary to the rst r levels by performing su ciently many greedy searches that each have a search cost r + 1. Consider a sequence of u update operations performed on H 0 . translates into a sequence of u update operations and g greedy searches on H . Let wi = the refresh cost of the i-th P operation in . The cost of on H is at least i wi + g (r + 1) and at most gr + uw, so P it follows that i wi uw. We conclude that H 0 incurs a worst-case cost of r on search operations and an amortized cost of w on update operations. We complete the proof of Theorem 2.1 by showing that a hashing scheme incurs either a worst-case cost of r on searches or an amortized cost of (n1=2r =22r b) on updates in processing operation sequences of length O(n). We modify the worst-case adversary

2.3. MULTILEVEL HASHING MODEL

31

Ar ;n;w;b by appropriately performing greedy insertion batches following random insertion batches. A con guration C of a partial hashing scheme H is said to be w-amortized, for a positive integer w, if the cost incurred by H in processing any sequence of update operations, starting from con guration C , is at most j jw. The new adversary Ar ;n;w;b is tailored against ( ; e)-good partial hashing schemes that start processing the adversary sequence in a w-amortized con guration; here e is a suitably de ned positive integer. Either the adversary performs a complete sequence of O(n) insertions, or it gets truncated because the scheme has entered a ( ; e)-bad con guration or because the scheme was not in a w-amortized con guration, initially. We de ne adversary Ar ;n;w;b against a partial hashing scheme H ; let denote the last component of . A w-greedy insertion batch performed against a hashing scheme H in a con guration C is de ned to be a maximal sequence of insertions, starting from con guration C , during which H incurs an update cost of at least wj j. The adversary performs a random rst batch just like the worst-case adversary, then performs a (2w)-

greedy insertion batch, and, nally, performs the tail phase; the adversary announces truncation even before performing the rst batch if the initial con guration of H is not w-amortized. The tail phase is de ned recursively, essentially as before, and consists of a narrow phase, possibly, followed by a wide phase; in the case r = 1, as before, the tail phase is a suitable extension batch that takes H to an -dense con guration. 1 The narrow phase consists of the tail phase of the recursive adversary Ar?;n;w;b performed against the induced hashing scheme H1 that is constructed as before. If the narrow phase gets truncated, then H1 has entered an ( ; e1)-bad, (22r? w)-amortized con guration. Equivalently, H has entered a (22r? w)-amortized con guration such that H uses only ( k =2; W1=2)-wide root hash functions in any -dense con guration during the next e1 insertions. The wide phase consists of a rst phase followed by a second phase that are de ned slightly di erently from the worst-case adversary. During the rst phase, following each batch of random insertions, we perform a (22r? +1 w)-greedy insertion batch so that, at the end of the rst phase, H is in a (22r? +1 w)-amortized con guration. 1 The second phase is recursively de ned to be the tail phase of adversary Ar?;n0 ;2 r? w;b performed against the induced hashing scheme H2 that is constructed as before. This completes the de nition of Ar ;n;w;b . We de ne parameters e, e1 , e2 , W , W1, and W2 as functions of r, , n, and w. Only
1 2 2 2 2 2 2 2

32

CHAPTER 2. THE DICTIONARY PROBLEM
er ( ; n; w) = W1r ( ; n; w)=(c022r? w) 2
2

the de nition of er ( ; n; w) has to be modi ed since it depends on w: 2 (2:7) The recurrence for W becomes: 8 r? >W ( < r ( ; n; w) = W > :
1

n=c1b

2 r ?1 =32; W 2( ?=22;n;w) ;22r?2 w) r w 8c0 2 cr b 1

if r 2 otherwise

This recurrence has the following solution:
2r+1 ?3 ; n; w) = n (r?1)(5r?8)=2 2r+1 ?r?2 22r?3 ?2r?2 2r ?1 : (64) 2 b (8c0w)2r?1?1 c1 the values of the parameters is approximately n( =22r wb)2r .

W r(

Hence The Lemmas 2.3, 2.4, and 2.5 still hold for Ar ;n;w;b with the exception of Lemma 2.4, Parts i. and iv. We modify some parts of the lemmas as follows:

Lemma 2.3 ii'. (10= )er ( ; n; w) er ( ; n; w), for all r, , n, and w. 2 1
iv'. The maximum number of insertions performed by Ar ;n;w;b during the wide phase is at most (10= )e2 e1 .
1

Lemma 2.4 i'. The maximum number of insertions performed by Ar ;n;w;b is at most 4n. Lemma 2.5 i'. A complete adversary sequence leaves the hashing scheme in an -dense

con guration; a truncated adversary sequence leaves the hashing scheme in a (22r? w)amortized ( ; e)-bad con guration.

Lemma 2.11 still holds for Ar ;n;w;b :

Lemma 2.12 Let = ( 1; 2; . . . ; k ) be a sequence of values in the interval 0; 1], let
=
k,

and let W = W r ( ; n; w) 1. Let H be a partial hashing scheme that has a (Wb)-bit root location and b-bit locations at levels 2. H succeeds against Ar ;n;w;b with probability e?W b .

This lemma gives a trade-o between the worst-case cost of searches, r, and the amortized cost of updates, w, incurred by a multilevel hashing scheme in the refresh cost

2.3. MULTILEVEL HASHING MODEL
model in processing sequences of O(n) operations:

33

w = (n1=2r =22r b):
The lower bound of Theorem 2.1 follows from this trade-o and our procedure for converting an amortized hashing scheme into a hashing scheme with a worst-case cost guarantee for search operations. Lemma 2.12 is proved in the same way as Lemma 2.11. The only part of the proof that changes due to amortization is Case 1 of the induction step. In this case the total refresh cost available during the wide phase is at most 10e222r? w= . We choose c0 > 320 so that this quantity is less than W1 =32, which is the probable refresh cost incurred by the rst batch. The rest of the proof remains as before.
2

34

CHAPTER 2. THE DICTIONARY PROBLEM

Chapter 3

The Deque Conjecture
Splay is an algorithm for searching binary search trees, devised by Sleator and Tarjan, that reorganizes the tree by means of rotations. Sleator and Tarjan conjectured that Splay is, in essence, the fastest algorithm for processing any sequence of search operations on a binary search tree, using only rotations to reorganize the tree. Tarjan proved a special case of this conjecture, called the Scanning Theorem, and conjectured a more general special case, called the Deque Conjecture. In this chapter, we prove tight bounds for some combinatorial problems involving rotation sequences on binary trees, derive a result that is a close approximation to the Deque Conjecture, and give two new proofs of the Scanning Theorem1.

3.1 Introduction
We review the Splay Algorithm, its conjectures and previous works on them, and describe our results.

3.1.1 The Splay Algorithm and Its Conjectures
Splay is a simple, e cient algorithm for searching binary search trees, devised by Sleator and Tarjan 28]. A splay at an element x of a binary search tree rst locates the element in the tree by traversing the path from the root of the tree to the element (called the access path of the element) and then transforms the tree by means of rotations in order
1
The work of this chapter was reported in 30].

35

36

CHAPTER 3. THE DEQUE CONJECTURE

to speed up future searches in the vicinity of the element. The splay transformation moves element x to the root of the tree along its access path by repeating the following step (See Figure 3.1): Let p and g denote, respectively, the parent and the grandparent of x. Case 1. p is the root: Make x the new root, by rotating the edge x; p]. Case 2. x; p] is a left edge (i:e: an edge to a left child) and p; g] is a right edge, or vice versa: Rotate x; p]; Rotate x; g ]. Case 3. Either both x; p] and p; g] are left edges, or both are right edges: Rotate p; g ]; Rotate x; p]. Sleator and Tarjan proved that Splay is, upto a constant factor, as e cient as the more complex traditional balanced tree algorithms for processing any sequence of binary search tree operations. They also showed that Splay actually behaves even faster on certain special kinds of sequences and conjectured that Splay is, upto a constant factor, the fastest rotation-based binary search tree algorithm for processing any sequence of searches on a binary search tree. We state this conjecture and some closely-related conjectures:
sequence of searches of elements in a given n-node binary search tree. De ne (s) equal to the minimum cost of executing sequence s on the tree using an algorithm that performs searches, incurring a cost equal to (1+ the distance of the element from the root) on each search, and transforms the tree by means of single rotations, incurring unit cost per single rotation. Splay takes O(n + (s)) time to process s.

Splay step.

Conjecture 3.1 (Dynamic Optimality Conjecture 28]) Let s denote an arbitrary

Conjecture 3.2 (Deque Conjecture 33]) Deque operations on a binary tree transform the tree by inserting or deleting nodes at the left or right end of the tree. We perform deque operations on a binary tree using Splay as follows (See Figure 3.2): Pop splays at the leftmost node and removes it from the tree; Push inserts a new node to the left, making the old tree its right subtree; Eject and Inject are symmetric operations performed at the right end. Splay takes O(m + n) time to process a sequence of m deque operations on an n-node binary tree.

3.1. INTRODUCTION

37

Case 1.

r x A B g p A B p D x C g p x C A B
Figure 3.1: A splay step.

x r C A B x g C

Case 2.

A

B

C

D

Case 3.

x p D A B C D g

38

CHAPTER 3. THE DEQUE CONJECTURE

tree to be a sequence of two right single rotations performed on the tree in which the bottom node of the rst rotation coincides with the top node of the second rotation (See Figure 3.3). In a sequence of right 2-turns and right single rotations performed on an n-node binary tree, there are only O(n) right 2-turns.

Conjecture 3.3 (Right Turn Conjecture 33]) De ne a right 2-turn on a binary

5 4 3 1 2 5

Pop
2

3 4

Inject(6)
6 5 3 2 Figure 3.2: The deque operations. 4

The conjectures are related as follows. A stronger form of the Dynamic Optimality Conjecture that allows update operations as well as search operations implies the Deque Conjecture. The Right Turn Conjecture also implies the Deque Conjecture.

3.1. INTRODUCTION

39

3.1.2 Terminology
We de ne the basic terminology used in the chapter. A binary search tree over an ordered universe is a binary tree whose nodes are assigned elements from the universe in symmetric order: that is, for any node x assigned an element e, the elements in the left subtree of x are lesser than e and the elements in the right subtree of x are greater than e. The path between the root and the leftmost node in a binary tree is called the left path. A tree in which the left path is the entire tree is called a left path tree. The edge between a node and its left child in a binary tree is called a left edge. The paths in a binary tree that comprise only left edges are called left subpaths. The left depth of a node in a binary tree is de ned to be the number of left edges on the path between the node and the root. The terms right path tree, right path, right edge, right subpath, and right depth are de ned analogously. A single rotation of an edge x; p] in a binary tree is a transformation that makes x the parent of p by transferring one of the subtrees of x to p (See Figure 3.3). A single rotation is called right or left, respectively, according to whether x; p] was originally a left edge or a right edge. A rotation on a binary tree is a sequence of single rotations performed on the tree. A rotation is called left or right, respectively, if it consists solely of left single rotations or solely of right single rotations. A double rotation on a binary tree is a sequence of two single rotations performed on the tree that have a node in common (as, for instance, by a splay step). A left path rotation on a binary tree is a right single rotation performed on the left path of the tree. A right path rotation is de ned analogously. We de ne the Ackerman hierarchy of functions fAi ji 0g, its inverse hierarchy f ^iji 0g, and inverse functions and of the Ackerman function as follows:

A0 (j ) = 2j for all j 1 A1 (j ) = 2j for all j 1 ( if i 2 and j 1 Ai(j ) = Ai?1 (2) (j ? 1)) if i 2 and j = 2 Ai?1 (Ai ^i (n) = minfk 1jAi (k) ng for all n 1 (n) = minfk 1jAk (1) ng for all n 1 (m; n) = minfk 1jAk ( m=n ) > log ng for all m n 1

40

CHAPTER 3. THE DEQUE CONJECTURE

i. A single rotation

p x C A B
ii. A right 3-twist

x A

p C

B

iii. A right 3-turn

iv. A right 3-cascade

Figure 3.3: The various types of rotations.

3.1. INTRODUCTION
The following table concretizes this de nition:

41 0 2j n=2 1 2j log n 1; 2] 2 22
2

i Ai (j ) ^i (n) fnj (n) = ig

j

3

4

log n 3; 4]

log n log n 2 16 2 5; 16] 17; 2 ]

3.1.3 Previous Works
Previous works on the Dynamic Optimality Conjecture have been mostly directed towards resolving its corollaries. Tarjan 33] proved that Splay requires linear time to sequentially scan the nodes of an n-node binary tree in symmetric order. This theorem, called the Scanning Theorem, is a corollary of all of the above conjectures. He also extended his proof to a proof of the Deque Conjecture when all the output operations are performed at one end of the tree. Lucas 22] obtained an O(n (n)) upper bound for the Deque Conjecture when all the operations are output operations and the initial tree is a simple path between the leftmost and rightmost nodes. Building upon the work of Cole et al. 11], Cole 9,10] recently proved Sleator and Tarjan's Dynamic Finger Conjecture 28] for the Splay Algorithm which is a corollary of the Dynamic Optimality Conjecture. Wilber 36] gave two elegant techniques for lower-bounding (s). The techniques yield optimal lower bounds for some special sequences (such as (s) = (n log n) for the bitreversal permutation), but it is not clear how tight these lower bounds are for general sequences. A related combinatorial question that has been studied is, how many single rotations are needed, in the worst case, to transform one n-node binary tree into another n-node binary tree? Culik and Wood 12] noted that 2n ? 2 rotations su ce and, later, Sleator et al. 29] derived the optimal bound of 2n ? 6 rotations for all su ciently large n.

3.1.4 Our Results
Our work is directed towards resolving the Deque Conjecture. A good understanding of the powers of various types of rotations on binary trees would equip us with the necessary tools to tackle the conjecture. We prove almost tight upper and lower bounds on the maximum numbers of occurrences of various types of right rotations in a sequence of

42

CHAPTER 3. THE DEQUE CONJECTURE

right rotations performed on a binary tree. We study the following types of rotations (See Figure 3.3):

Right twist: For all k

1, a right k-twist is a sequence of k right single rotations performed along a left subpath of a binary tree, traversing the subpath top-down. of k edges in a binary tree into a right subpath.

Right turn: For all k 1, a right k-turn is a right k-twist that converts a left subpath Right cascade: For all k 1, a right k-cascade is a right k-twist that rotates every
other edge lying on a left subpath of 2k ? 1 edges in a binary tree. A right twist sequence is a sequence of right twists performed on a binary tree. De ne Twk (n), Tuk (n) and Ck (n), respectively, to be the maximum numbers of occurrences of k-twists, k-turns and k-cascades in a right twist sequence performed on an n-node binary tree. These numbers are well de ned since a tree is transformed into a right path ! n right single rotations. We derive the following bounds for Tw (n), Tu (n) after 2 k k and Ck (n):

Twk (n) Tuk (n) Ck (n)

(

Upper bound O(kn1+1=k ) O(n ^ k=2 (n)) if k 6= 3 O(n log log n) if k = 3

(

Lower bound (n1+1=k ) ? O(n) (n ^ k=2 (n)) ? O(n) if k 6= 3 (n log log n) if k = 3

The bounds for Tuk (n) and Ck (n) are tight if k 2 (n) ? 5 and the bounds for Twk (n) are nearly tight. The Right Turn Conjecture is refuted by the lower bound of (n log n) for Tu2(n)2 . We apply the upper bound for cascades to derive an O((m + n) (m + n)) upper bound for the Deque Conjecture. Another approach to the Deque Conjecture is to nd new proofs of the Scanning Theorem that might naturally extend to the Deque Conjecture setting. We obtain a simple potential-based proof that solves Tarjan's problem 33] of nding a potentialbased proof of the theorem, and an inductive proof that generalizes the theorem. The new proofs enhance our understanding of the Scanning Theorem, but, so far, have not led to a proof of the Deque Conjecture.
S.R.Kosaraju has independently proved that T u2 (n) = (n log n). While his upper bound proof di ers from ours, the lower bound constructions match.
2

3.2. COUNTING TWISTS, TURNS, AND CASCADES

43

The chapter is organized as follows. In Section 3.2, we prove the bounds for Twk (n), Tuk (n) and Ck (n). In Section 3.3, we derive the upper bound for the Deque Conjecture. In Section 3.4, we describe the new proofs of the Scanning Theorem.

3.2 Counting Twists, Turns, and Cascades
The two subsections of this section derive the upper and lower bounds for Twk (n), Tuk (n) and Ck (n).

3.2.1 Upper Bounds
All our upper bound proofs are based on a recursive divide-and-conquer strategy that partitions the binary tree on which the right twist sequence is performed into a collection of vertex-disjoint subtrees, called block trees. The root and some other nodes within each block are labeled global and the global nodes of all of the block trees induce a new tree called the global tree. Each rotation on the original tree e ects a similar rotation either on one of the block trees or on the global tree. This allows us to inductively count the number of rotations of each type in the sequence. We need the notion of blocks in binary trees 33]. Consider an n-node binary tree B whose nodes are labeled from 1 to n in symmetric order. A block of B is an interval i; j ] 1; n] of nodes in B. Any block i; j ] of B induces a binary tree Bj i;j] , called the block tree of block i; j ], which comprises exactly the nodes i to j . The root of B j i;j ] is the lowest common ancestor of nodes i and j in B . The left child of a node x in B j i;j ] is the highest node in the left subtree of x in B which lies in block i; j ]. The right child of a node in B j i;j ] is de ned analogously. Notice that, for the subtree rooted at any node of B , the highest node of the subtree which lies in block i; j ] is unique whenever it exists: if two equally highest nodes exist, then their lowest common ancestor in the subtree would be higher than the two nodes, resulting in a contradiction. How does a rotation on B a ect a block tree B j i;j ] ? If both of the nodes involved in the rotation are in B j i;j ] , then the rotation translates into a rotation on B j i;j ] involving the same pair of nodes. Otherwise, B j i;j ] is not a ected. The functions Twk , Tuk and Ck are superadditive:

44

CHAPTER 3. THE DEQUE CONJECTURE

Lemma 3.1 For all k 1 and m n 1, we have:
a. m=n Twk (n) Twk (m), b. m=n Tuk (n) Tuk (m), and c. m=n Ck (n) Ck (m):

S for an n-node binary tree B that comprises Twk (n) right k-twists, construct a new tree of size m=n n m by starting with a copy of B and successively inserting a new copy of B as the right subtree of the rightmost node in the current tree m=n ? 1 times. Since S can be performed on each of the copies of B one after another, there exists a right twist sequence with m=n Twk (n) k-turns for a tree of size m. Part a. follows
The upper bound for twists is the simplest to derive. De ne Li (j ) = i + ji ? 1 for all i 1 and j 1. The upper bound for Twk (n) for n of the form Lk (j ) is given by: immediately.
!

Proof. We prove Part a.; Parts b. and c. are similar. Given a right twist sequence

j Lemma 3.2 Twk (Lk (j )) k k + + ? 1 for all k 1 and j 1. k 1

!

and a right block of Lk (j ? 1) nodes. A right twist sequence on the tree translates into corresponding right twist sequences on the left and right block trees. We classify the k-twists in the original sequence into three categories and count the number of k-twists of each type separately. In the rst type of k-twist, the lowest k ? 1 single rotations involve only left block nodes. Such a k-twist translates into a (k ? 1)-twist on the left block tree. Applying induction to the induced right twist sequence performed on the left ! k + j ? 2 k-twists of the rst type block tree, we see that there are at most (k ? 1) k in the original right twist sequence. Similarly, the number of k-twists that involve only ! k + j ? 2 . Consider a k-twist that does not belong to right block nodes is at most k k + 1 these two categories. The highest single rotation of such a twist must involve only right

Proof. We use double induction on k and j . Case 1. k = 1 or j = 1: Straightforward. Case 2. k 2 and j 2: The tree is partitioned into a left block of Lk? (j ) nodes
1

3.2. COUNTING TWISTS, TURNS, AND CASCADES

45

block nodes; also, the lowest node involved in the twist must be a left block node. This implies that the highest node of the twist is a right block node that leaves the left path of its block as a result of the twist. Right rotations never add nodes to a block's left path, so the number of k-twists in the last category is at most the initial size of the left ! k + j ? 2 . It follows that the total number of path of the right block Lk (j ? 1) = k right k-twists in the right twist sequence is bounded by

j j j (k ? 1) k + k ? 2 + k k + + ? 2 + k + k ? 2 k 1 ! ! k+j ?2 +k k+j ?2 = k k k+1 ! j = k k ++ ? 1 : k 1

!

!

!

A simple calculation using the above lemma and Lemma 3.1a gives the upper bound for Twk (n) for all n:

Theorem 3.1 Twk (n) kn

1+1

=k for all

k 1 and n 1. k + i g. Then we have k
! !

Proof. Fix k and de ne j = minfijn
Tk (n)
!

Tk ( k + j )= k + j =n (By Lemma 3.1a) k k ! ! k + j n= k + j (By Lemma 3.2) 2k k + 1 k kn1+1=k :

We derive!the upper bounds for turns and cascades. It is easy to see that Tu1(n) = C1(n) = n n ^0 (n). Let us prove that Tu2 (n) = O(n ^1 (n)). Consider any right 2 twist sequence performed on a binary tree B . We divide B into a left block 1; n=2 ] and a right block n=2 + 1; n]. Every 2-turn either involves nodes from only one block (intrablock) or involves nodes from both blocks (interblock). An intrablock 2-turn e ects a 2-turn in the corresponding block tree and gets counted in the right twist sequence for

46

CHAPTER 3. THE DEQUE CONJECTURE

the block tree. Every interblock 2-turn either adds a node to the right path of the left block tree or deletes a node from the left path of the right block tree (See Figure 3.4). Right rotations never remove nodes from a block's right path or add nodes to a block's left path, so the number of interblock 2-turns is at most n ? 2. This leads to the following recurrence for Tu2(n):

Tu2(n)

(

0

Tu2 ( n=2 ) + Tu2( n=2 ) + n ? 2 if n 3 if 1 n 2

Solving the recurrence yields the desired bound for Tu2 (n):

Tu2 (n) n log n ? 2 log n ? n + 2 n ^1 (n):
With a slight modi cation the same proof works for 2-cascades also. An interblock 2-cascade either decreases the size of the left path of the right block tree or increases the number of left block nodes whose left depth relative to the block is at most 1 (See Figure 3.5). Right rotations never increase the left depth of a node, so the number of interblock 2-cascades is at most n ? 3. The bound C2(n) n ^1 (n) follows. * * * * * * * * Figure 3.4: The two types of interblock right 2-turns. Circles denote left block nodes and squares denote right block nodes. The stars identify the nodes that lie on the left/right path of a block. * *

3.2. COUNTING TWISTS, TURNS, AND CASCADES

47

* # # # # * * # # * * * # # * * # # * # *

Figure 3.5: The three types of interblock right 2-cascades. The sharps identify the left block nodes that have a left depth of at most 1; the stars identify the right block nodes lying on the left path of their block.

48

CHAPTER 3. THE DEQUE CONJECTURE

In order to extend the above argument to k-turns and k-cascades for k 3, we need an Ackerman-like hierarchy of functions fKi ji 1g:

K1 (j ) = 8j for all j 1 K2 (j ) = 24j for all j 1 ( if i 3 and j 1 iKi ( i=2 Ki(j ) = K (?2? 1)K ) (K (j ? 1)=4)=2 if i 3 and j = 2 ij i?2 i
The function Ki grows faster than the Ackerman function A i=2 :

Lemma 3.3

1. A(2)(j ) K3(j ) for all j 1

1. 1.

2. A i=2 (j ) Ki (j ) for all i 6= 3 and j

The upper bound for Tuk (n) for n of the form Kk (j ) is given by:

Lemma 3.4 Tuk (Kk (j )) 4jKk(j ), for all k 1 and j 1. Proof. We use double induction on k and j . Case 1. 1 k 2: The lemma follows from the bounds Tu (n) n ^ (n) and
1 0

following types: Type A. All of the nodes involved in the k-turn belong to a single block: Since a block has only 2k nodes, there can be at most one such k-turn per block. Type B. Some two nodes of the k-turn belong to a single block, but not all of the nodes of the turn are in that block: Let C denote the block tree of this block. The k-turn causes either an increase in the size of the right path of C , or a decrease in the size of the left path of C , or both. Hence the number of Type-B k-turns is at most 2Kk (1). Type C. Each node of the k-turn belongs to a di erent block: To handle this case, we label the root of each block global. The global nodes in B induce a binary tree G, called the global tree. The root of G is identical to the root of B . The left child of a

Tu2(n) n ^1(n). Case 2. k 3 and j = 1: We need to show that Tuk (Kk (1)) 4Kk(1). Consider a binary tree B having Kk (1) nodes on which a right twist sequence is performed. Divide B into a sequence of Kk?2 ( k=2 )=2 blocks of size 2k each. Each k-turn is of one of the

3.2. COUNTING TWISTS, TURNS, AND CASCADES

49

node x in G is the highest global node in the left subtree of x in B . The right child of a node is de ned similarly. It is easy to see that the left and right children of any node in G are unique. The e ect on G of a rotation on B is analogous to the e ect of such a rotation on a block tree of B : A rotation on B translates into a rotation on G if both of the nodes of the rotation are global; otherwise, G is una ected. (If a rotation changes the root of a block then the global role passes from the old root to the new root but this does not a ect the global tree.) Suppose that the k-turn turns the left subpath x1 ? x2 ? ? xk+1 of B into a right subpath. Since all the xi s are from di erent blocks, the nodes x2 ; x3; . . . ; xk are all global. Therefore, the k-turn results in a (k ? 2)-turn on G (if x1 or xk+1 is also global, then some right single rotations are also performed on G.) The number of (k ? 2)-turns that can be performed on G is at most

Tuk?2 (Kk?2 ( k=2 )=2)

Tuk?2 (Kk?2( k=2 ))=2 (By Lemma 3.1b) 2 k=2 Kk?2 ( k=2 ) (By the induction hypothesis) < Kk (1):

This gives an upper bound of Kk (1) for the number of Type-C k-turns performed on B . Summing together the above bounds for the three types of k-turns, we obtain a bound of Kk?2 ( k=2 )=2 + 2Kk (1) + Kk (1) 4Kk (1) for the total number of k-turns in the right twist sequence. This completes Case 2. Case 3. k 3 and j 2: We divide the binary tree on which the right twist sequence is executed into Kk (j )=Kk(j ? 1) blocks of size Kk (j ? 1) each. We split the k-turns into the three types de ned in Case 2 and obtain the following tally for each type of turn: Number of Type-A k-turns Kk (j ) :4(j ? 1)K (j ? 1) (By the induction hypothesis) k Kk (j ? 1) 4(j ? 1)Kk (j ): Number of Type-B k-turns 2Kk (j ): Number of Type-C k-turns

50

CHAPTER 3. THE DEQUE CONJECTURE
Tuk?2 (Kk?2 (Kk (j ? 1)=4)=2) Tuk?2 (Kk?2 (Kk (j ? 1)=4))=2 (By Lemma 3.1b) Kk (j ? 1)Kk?2 (Kk (j ? 1)=4)=2 (By the induction hypothesis) = Kk (j ):

Hence the total number of k-turns in the sequence is at most 4(j ? 1)Kk (j ) + 2Kk (j ) + Kk (j ) < 4jKk (j ): This nishes Case 3. Combining the above lemma with Lemmas 3.1b and 3.3, we obtain the upper bound for Tuk (n) for all k and n:

Theorem 3.2
Tuk (n)

(

8n ^ k=2 (n) if k 6= 3 8n log log n if k = 3

The upper bound for cascades is derived analogously:

Theorem 3.3
Ck (n)

(

8n ^ k=2 (n) if k 6= 3 8n log log n if k = 3

and j 1. Referring to the proof of Lemma 3.4, only the handling of Cases 2 and 3 has to be modi ed. Consider Case 2. As before, the blocks have size 2k each. The k-cascades are categorized as follows: Type A. All nodes involved in the cascade belong to a single block: There is at most one Type-A cascade per block. Type B. One of the cascade rotations involves a pair of nodes belonging to a single block, but not all of the nodes of the cascade are in that block: If the cascade rotates an edge that lies on the left path of some block, then the length of the left path of the block decreases by at least 1. Alternately, if the lowest three nodes involved in the cascade are from the same block, then the number of nodes in that block whose left depth is at most 1 increases. We conclude that the number of Type-B cascades falling under the above

Proof. It su ces to prove Lemma 3.4 for Ck (n): Ck (Kk (j )) 4jKk(j ), for all k 1

3.2. COUNTING TWISTS, TURNS, AND CASCADES

51

categories is at most 2Kk (1) ? Kk?2 ( k=2 ). In every remaining Type-B k-cascade, only the lowest cascade rotation is intrablock and the lowest three nodes do not belong to the same block. Each such cascade behaves like a Type-C cascade in that it causes a (k ? 2)-cascade on the global tree (de ned below) which accounts for it. Type C. Each cascade rotation involves a pair of nodes belonging to di erent blocks: In this case for each block, in addition to the root of the block, we also label the left child of the root within the block global, if it exists; if the root has no left child, then the right child of the root is labeled global. Right rotations are propagated from the original tree to the global tree as described in Lemma 3.4 except in the following situation: When the edge joining the root and its left child, say l, in a block is rotated, the left child of l, say ll, now becomes global, and if ll is not adjacent to l in B , this results in a series of right single rotations on the global tree (See Figure 3.6). Under this de nition of global tree, the (k ? 2) interior rotations performed by any Type-C k-cascade are all global. Hence, each Type-C k-cascade translates into a right (k ? 2)-cascade and a sequence of right single rotations on the global tree. Therefore the total number of k-cascades in the sequence is at most

Kk?2 ( k=2 )=2 + 2Kk (1) ? Kk?2 ( k=2 ) + Ck?2 (Kk?2 ( k=2 )) < 4Kk (1):
This completes Case 2 in the proof of Lemma 3.4 for cascades. Case 3 is handled similarly.

3.2.2 Lower Bounds
The lower bound right twist sequences are inductively constructed by mimicking the divide-and-conquer strategy used to derive the upper bounds. The lower bound sequences always transform a left path tree into a right path tree. The tree is partitioned into a collection of vertex-disjoint block trees and a global tree is formed by selecting nodes from each block tree. The lower bound sequence for a tree is constructed by inductively constructing similar lower bound sequences for the block trees and for the global tree and weaving these sequences together. Actually, we rst inductively construct a sequence of right twists as well as deletions having su ciently many rotations of the given type and then remove the deletions to obtain the lower bound sequence. We need some de nitions. For all positive integers k, a right k-twist-deletion sequence

52

CHAPTER 3. THE DEQUE CONJECTURE

* *

*

The original tree * * * * * * *

The global tree

Figure 3.6: The e ect of a right single rotation involving the root of a block and its left child within the block on the global tree. Circles denote the nodes of the block; other symbols denote the nodes from other blocks. The starred nodes in the original tree are the global nodes.

3.2. COUNTING TWISTS, TURNS, AND CASCADES

53

is de ned to be an intermixed sequence of right single rotations, right k-twists and deletions of the leftmost node performed on a binary tree. Right k-turn-deletion sequences and right k-cascade-deletion sequences are de ned analogously. Consider a right twist that is performed on some left subpath x0 ? x1 ? ? xl of a binary tree, where x0 is the lowest node on the subpath. x0 is called the base of the twist. If xk is the left child of a node y (say) in the tree, then the twist is called an apex twist and y is the apex of the twist. Otherwise, the twist is called apexless. ! k + j ? 1 is given by: The lower bound for Tw (n) for n of the form L (j ) =
k k

k

Lemma 3.5 Twk (Lk (j ))

k + j ? 1 for all k 1 and j 1. k+1

!

twist-deletion sequence for a left path tree of Lk (j ) nodes having the following properties: 1. The sequence deletes all the nodes from the tree. 2. A right k-twist always involves the leftmost node of the tree. 3. A deletion always deletes the root of the tree. ! k + j ? 1 k-twists. 4. The sequence has exactly k + 1 The removal of the deletions from the sequence would yield a right twist sequence having the desired number of k-twists. Case 1. k = 1 or j = 1: Easy. Case 2. k 2 and j 2: Divide the left path tree into a lower block of size Lk?1(j ) and an upper block of size Lk (j ? 1). Recursively perform a right (k ? 1)-twist-deletion ^ ^ sequence, say S , on the lower block tree. For each (k ? 1)-twist in S , rst rotate the edge joining the root of the lower block with its parent and then perform the (k ? 1)-twist on the block. This is equivalent to a k-twist involving the leftmost node of the tree. Each ^ deletion in S is modi ed by rst making the deleted node the root of the tree using right ^ rotations and then deleting ! node. By property 4 of S , the number of (k ? 1)-twists the j ^ in S is exactly k + k ? 2 . The initial depth of the root of the lower block equals

Proof. For any pair of positive integers k and j , we inductively construct a right k-

54
!

CHAPTER 3. THE DEQUE CONJECTURE

j ^ Lk (j ? 1) = k + k ? 2 . Since each (k ? 1)-twist in S reduces the depth of the root of ^ the lower block by 1 and no other operation in S a ects the depth, it is always possible to ^ rotate the root of the lower block just before the execution of any (k ? 1)-twist in S . The construction is completed by recursively performing a right k-twist-deletion sequence, say S , on the upper block. The sequence obviously satis es properties 1{3. The total number of k-twists performed by the sequence equals ^ (the number of (k!? 1)-twists in S ) + (the number of k-twists in S ) ! j j = k + k ? 2 + k + + ? 2 (By the induction hypothesis) k 1 ! j = k ++ ? 1 : k 1 This proves property 4. Combining Lemma 3.1a with the above lemma yields:

Theorem 3.4 Twk (n) n

1+1

=k =2e ? O(n) for all

k 1 and n 1.

We construct the lower bound sequences for turns. As in the upper bound proof, we need a new Ackerman-like hierarchy of functions. De ne:

B1(j ) = j for all j 1 B2(j ) = 2j ? 1 for all j 1 ( Bi (j ) =

1 if i 3 and j = 1 ((i + 1)jBi(j ? 1) + 1)Bi?2 ((i + 1)jBi(j ? 1)) if i 3 and j 2 1. 1.

The function Bi grows essentially at the same rate as the Ackerman function A i=2 :

Lemma 3.6

1. B3 (j ) A(2)(2j ), for all j 1

2. Bi (j ) A i=2 (3j ) for all i 6= 3 and j

The lower bound for Tuk (n) for n of the form Bk (j ) is given by:

Lemma 3.7 Tuk (Bk (j )) (1=2)(j ? 3)Bk (j ) for all k 1 and j 1.

3.2. COUNTING TWISTS, TURNS, AND CASCADES

55

erties:

k-turn-deletion sequence for the left path tree of Bk (j ) nodes having the following prop1. The sequence deletes all the nodes from the tree. 2. A right k-turn always involves the leftmost node of the tree. 3. A deletion always deletes the root of the tree. 4. The sequence comprises at least (1=2)(j ? 3)Bk (j ) apex k-turns. Further, if k 3, there are no apexless k-turns in the sequence. 5. For any node x, the number of apex k-turns with base x is at most j . 6. For any node x, the number of apex k-turns with apex x is at most j . deletes it.

Proof. For any pair of positive integers k and j , we inductively construct a right

Case 1. k = 1: The sequence repeatedly rotates the leftmost node to the root and
1

nodes, a middle node, and an upper left subpath comprising 2j ?1 ? 1 nodes. Recursively perform a right 2-turn-deletion sequence on the lower subpath. Modify each deletion in this sequence as follows: Perform a 2-turn on the subpath de ned by the deleted node, say x, its parent (the middle node), and its grand parent; make x the root of the tree by successively rotating the edge joining it and its parent; delete x from the tree (this also deletes x from the lower subpath.) Next, delete the middle node which is currently the root of the tree. Finally, recursively perform a right 2-turn-deletion sequence on the upper subpath (See Figure 3.7). This sequence performs (j ? 2)2j ?1 + 1 2-turns of which exactly j ? 1 are apexless. Therefore the number of apex 2-turns is at least (j ? 3)2j ?1 (1=2)(j ? 3)B2 (j ). This proves property 4. The remaining properties are easy to check.

Case 2. k = 2: Divide the left path tree into a lower left subpath comprising 2j? ? 1

sequences of operations performed on the block trees of the tree:

Case 3. k 3 and j = 1: Just delete the only node in the tree. Case 4. k 3 and j 2: Let s = (k + 1)jBk(j ? 1). We inductively construct the

56

CHAPTER 3. THE DEQUE CONJECTURE

2j ?1 ? 1 Recurse on the subpath of circles right 2-turn r.rotations

2j ?1 ? 2

2j ?1 ? 1

2j ?1 ? 2 r.2-turn; r.rotations

Recurse on the subpath of ellipses

2j ?1 ? 3

2j ?1 ? 3 Figure 3.7: The lower bound construction for right 2-turns. The construction recursively transforms a left path tree of size 2j ? 1 into a right path tree.

3.2. COUNTING TWISTS, TURNS, AND CASCADES
satisfying properties 1 and 2 and the following properties:

57

Lemma 3.8 There exists a right k-turn-deletion sequence for a left path tree of size s +1
3. A deletion that is not the last operation in the sequence always deletes the left child of the root. 4. The sequence comprises at least (1=2)(j ? 4)s + j right k-turns all of which are apex turns. 5. For any node x, the number of apex k-turns with base x is at most j ? 1. 6. For any node x, the number of apex k-turns with apex x is at most j ? 1. 7. The root of the tree is always the rightmost node.

blocks of size Bk (j ? 1) each. Perform a right k-turn-deletion sequence obeying properties 1{6 on the lowest block. (The inductive hypothesis implies the existence of such a sequence.) Denote this sequence by S . Each deletion in S except the last is modi ed by rotating the deleted node up the tree until it is adjacent to the root and then deleting it. The deletion of the last node in the block, say x1, is implemented di erently. x1 is rotated up the tree until it is in contact with the root of the next higher block, say x2. x2 is rotated upwards in a similar fashion in order to make it adjacent to the root of the next higher block, say x3 . In this manner we create a left subpath x1 ? x2 ? ? xk+1 containing the roots of the lowest k + 1 blocks. Next, a right k-turn is performed on this subpath and then x1 is rotated up the tree and deleted. Following this, S is executed on the blocks of nodes x2; x3 . . . ; xk+1 in succession. Each deletion is modi ed by rst making the deleted node adjacent to the root and then deleting it. At the conclusion of this sequence of operations, all the nodes in the lowest k + 1 blocks of the tree have been deleted and at least (1=2)(j ? 4)(k + 1)Bk (j ? 1) + 1 apex k-turns have been performed. The above sequence of operations is repeated on each group of k + 1 consecutive blocks, choosing the lowest group of blocks currently in the tree each time. The nal operation of the sequence deletes the root. It is obvious that the right k-turn-deletion sequence constructed above satis es properties 1,2,3 and 7. Since there are j groups of k + 1 blocks each, the total number of

Proof. Divide the nodes of the tree excluding the root into a sequence of (k + 1)j

58

CHAPTER 3. THE DEQUE CONJECTURE

apex k-turns executed by the sequence is at least (1=2)(j ? 4)s + j . Further, by property 4 of S , the sequence performs only apex k-turns. This proves property 4. Properties 5 and 6 are easy to show using properties 5 and 6 of sequence S . We construct a right k-turn-deletion sequence for the left path tree of size Bk (j ) satisfying the six properties. The tree is partitioned into Bk?2 (s) blocks of size s + 1 each. The root of each block is labeled global. The global nodes form a global tree as described in the proof of Lemma 3.4. By the induction hypothesis, there exists a right (k ? 2)-turn-deletion sequence, say S , for the global tree, satisfying properties 1-6. We construct the right k-turn-deletion sequence, denoted S , for the original tree by mapping each global tree operation in S onto a sequence of original tree operations, preserving the correspondence between the two trees. The following invariants de ne the relationships between the two trees: A. Let B denote the block containing the leftmost node of the tree and let x denote the root of B . Suppose that d nodes have been deleted from B so far. Then, i. The number of apex (k ? 2)-turns performed so far on the global tree that had x as their base is exactly d. ^ ii. Denote by S the right k-turn-deletion sequence constructed by Lemma 3.8 that deletes all the nodes from the left path tree of size s + 1. Let T denote ^ the tree that results when the pre x of S up to the dth deletion is executed on the left path tree. The block tree of B equals T . B. Consider any block B that does not contain the leftmost node of the tree. Let x denote the root of B . The block tree of B is a left path tree which is divided into the root and two subpaths. The nodes in the lower subpath, called black nodes, are the nodes in B that have participated in a k-turn. The nodes in the upper subpath are called white nodes. i. If b denotes the number of black nodes currently in B , then exactly b of the apex (k ? 2)-turns performed so far on the global tree had x as their apex. C. If x is a global node with a right child y in the global tree, y is also the right child of x in the original tree.

3.2. COUNTING TWISTS, TURNS, AND CASCADES

59

D. If x is a global node with a left child y in the global tree, there is a left subpath x = x0 ? x1 ? . . . ? xk+1 = y in the original tree such that x1; x2; . . . ; xk are the set of white nodes in the block of x. Each global tree operation in S is simulated as follows:

Right rotation: Suppose that a global tree edge x; y], such that y is a left child of x,

is rotated. In the original tree we repeatedly rotate the edge connecting y and its parent until x becomes the right child of y . Only invariants C and D are a ected by the rotations. It is not hard to see that both these invariants are true after the last rotation.

Deletion: Suppose that a global node x is deleted. Since x is the root of the global tree,

it is also the root of the original tree. Let d denote the number of nodes deleted so ^ far from the block of x. We perform S (the sequence constructed by Lemma 3.8) on the block tree of x starting immediately after the dth deletion. Each deletion is modi ed so that the deleted node is rst made the root of the tree and then deleted. Invariant A.ii ensures that this is valid and that this will result in the deletion of all the nodes in the block of x from the tree. Therefore this sequence of operations reestablishes the correspondence between the global tree and the original tree. simulate each global rotation as speci ed above.

Apexless (k ? 2)-turn: Break up the turn into a sequence of k ? 2 global rotations and Apex (k ? 2)-turn: Suppose that a global tree subpath x ? x ? ? xk? is turned
and that x1 is the base of the turn. Let x0 denote the leftmost node in the block of x1 and let xk denote the parent of xk?1 in the original tree. We create the subpath x0 ? x1 ? . . . ? xk in the original tree and perform a k-turn on this subpath. This is implemented as follows:
1 2 1

1. Let d denote the number of nodes deleted so far from the block of x1 . Exe^ cute the segment of sequence S between the dth and the (d + 1)st deletions (excluding the deletions) on the block tree of x1 . By Lemma 3.8, property 3, this makes node x0 the left child of x1 . 2. Rotate x1 up the tree until its parent is x2 . Continuing in this fashion, rotate the nodes x2; x3; . . . ; xk?1 upwards, creating a left subpath x0 ? x1 ? ? xk .

60

CHAPTER 3. THE DEQUE CONJECTURE
3. Perform a k-turn on the subpath x0 ? x1 ? ? xk . 4. Rotate x0 up the tree, making it the root, and delete it. 5. Since xk has become black due to the k-turn, the edge joining xk and its left child is repeatedly rotated until the left child of xk is not a global node. Invariant B.i and property 6 of S guarantee that xk is white at the beginning of this sequence of operations. Similarly, invariant A.i and property 5 of S guarantee that x0 is well de ned. Observe that all invariants are true at the end of the simulation.

The sequence of operations performed on the original tree during the simulation of S constitutes sequence S . S deletes all the nodes in the original tree since S deletes all the nodes in the global tree. This proves that S satis es property 1. Properties 2 and 3 of S are apparent from the simulation procedure. By Lemma 3.8, at least (1=2)(j ? 4)s + j apex k-turns (local turns ) are performed ^ during the execution of S on any particular block. Hence the total number of local turns summed over all blocks is at least (1=2)(j ? 4)sBk?2 (s)+ jBk?2 (s). The number of turns involving global nodes (global turns ) equals the number of (k ? 2)-turns in S which, by the induction hypothesis, is at least (1=2)(s ? 3)Bk?2 (s). Therefore the total number of k-turns in S is at least (1=2)(j ? 4)sBk?2 (s) + jBk?2 (s) + (1=2)(s ? 3)Bk?2 (s) = ((1=2)(j ? 3)s + j ? (3=2))Bk?2(s) > (1=2)(j ? 3)Bk (j ): Evidently, every k-turn in S has an apex. This proves property 4. For any node x, there is at most one global turn with x as the base since x is deleted from the tree immediately after the turn. By Lemma 3.8, there are at most j ? 1 local turns with x as the base. We conclude property 5. Property 6 is proved analogously. Combining the above lemma with Lemma 3.1b yields:

Theorem 3.5

Tuk (n)

(

(1=12)n ^ k=2 (n) ? O(n) if k 6= 3 (1=8)n log log n ? O(n) if k = 3

3.2. COUNTING TWISTS, TURNS, AND CASCADES
The lower bound for cascades is given by:

61

Theorem 3.6
Ck (n)

(

(1=12)n ^ k=2 (n) ? O(n) if k 6= 3 (1=8)n loglog n ? O(n) if k = 3

Proof. We modify the lower bound proof for Tuk (n) given above. De ne:
0 B1 (j ) = j for all j 1 0 B2 (j ) = 3:2j ? 2 for all j 1 (

Bi0 (j ) =

It is easy check that Lemma 3.6 holds for the new hierarchy fBi0 g. We prove the analogue 0 0 of Lemma 3.7 for Ck (n), which states that Ck (Bk (j )) (1=2)(j ? 3)Bk (j ) for all k 1 and j 1. We construct a right k-cascade-deletion sequence that converts a left path 0 tree of size Bk (j ) into a right path tree and satis es the analogues of properties 1{6 for cascades. Case 1. k = 1 or j = 1: Easy. Case 2. k = 2: Divide the left path tree into a lower subpath and an upper subpath, each having 3:2j ?1 ? 2 nodes, and two middle nodes. The right 2-cascadedeletion sequence is constructed by recursing on the lower and upper subpaths in turn and performing a 2-cascade involving the deleted node and the middle nodes for each deletion in the rst recursive step. The sequence comprises (3j ? 4)2j ?1 ? j + 2 (1=2)(3:2j ? 2)(j ? 3) apex 2-cascades and satis es all the properties. 0 Case 3. k 3 and j 2: Let s = 4kjBk (j ? 1). A p; q-zigzag tree is a tree that is constructed from a p-node left path tree by inserting a q -node left path tree as the right subtree of the leftmost node. We extend Lemma 3.8 to cascades and construct a right ^ k-cascade-deletion sequence, say S , for a 3; s-zigzag tree that comprises (1=2)(j ? 4)s +2j apex k-cascades. Each deletion in the sequence, except for the last two deletions, deletes the leftmost grandchild of the root. The proof divides the tree into 2j groups of 2k 0 blocks each, each block, in turn, of size Bk (j ? 1), and recursively performs a right kcascade-deletion sequence on each block, choosing the blocks in bottom-to-top order. A k-cascade is performed on the roots of the blocks within each group, yielding 2j extra cascades.

1 if i 3 and j = 1 (4ijBi0(j ? 1) + 3)Bi0?2 (4ijBi0(j ? 1)) if i 3 and j 2

62

CHAPTER 3. THE DEQUE CONJECTURE

0 The tree is partitioned into Bk?2 (s) blocks of size s + 3 each. The global tree is constructed from the roots of the blocks and a right (k ? 2)-cascade-deletion sequence, say S , satisfying properties 1{6 is recursively performed on it. The simulation of S on the original tree maintains the invariants A (with expression s + 3 replacing s + 1), C and D and the following modi cation of invariant B :

B. Consider any block B that does not contain the leftmost node of the tree. Let x denote the root of B . Block B induces a connected subtree in the original tree. Further, if exactly b of the (k ? 2)-cascades performed so far on the global tree had x as their apex, then the block tree of B is a (s ? b + 3); b-zigzag tree. The simulation of global tree operations other than apex (k ? 2)-cascades is as before. Consider an apex (k ? 2)-cascade in S involving a global tree subpath x1 ? x2 ? ? x2k?4 , such that x1 is the base of the cascade. Let y1 and y2 denote, respectively, the leftmost node in the block of x1 and the left child of x1 . Let z1 and z2 denote, respectively, the parent and the grandparent of x2k?4 in the original tree. The global tree cascade is simulated on the original tree by creating the subpath y1 ?y2 ?x1 ?x2 ? ?x2k?4 ?z1 ?z2 in the original tree, performing a k-cascade on this subpath, and nally deleting y1 from the tree. We verify that the resulting sequence, say S , satis es property 4: # k-cascades in S = # local cascades + # global cascades 0 0 ((1=2)(j ? 4)s + 2j )Bk?2(s) + (1=2)(s ? 3)Bk?2 (s) 0 > (1=2)(j ? 3)Bk (j ): The rest of the properties of S are easy to check. This completes the proof of Lemma 3.7 for cascades. The theorem follows.

3.3 An Upper Bound for the Deque Conjecture
In this section, we show that Splay takes O((m + n) (m + n)) time to process a sequence of m deque operations on an n-node binary tree. We reduce a deque operation sequence to right cascade sequences on auxiliary trees and apply the upper bounds for cascades. De ne the cost of a deque operation or a right twist operation to be the number of single rotations performed by the operation.

3.3. AN UPPER BOUND FOR THE DEQUE CONJECTURE
The cost of a set of right cascades in a right twist sequence is given by:

63

tree. The total cost of any m right cascades in the sequence equals O((m + n) (m + n; n)).

Lemma 3.9 Consider an arbitrary right twist sequence executed on an n-node binary Proof. Let l = 2 (m + n; n) + 2. Split each of the m right cascades into a sequence

of right l-cascades followed by a sequence of at most l ? 1 rotations. By Theorem 3.3, the total number of right l-cascades is at most 8n ^ l=2 (n). This yields a bound of (m + 8n ^ l=2 (n))l for the number of rotations performed by the m right cascades. We bound ^ l=2 (n) as follows:

A

(

m+n;n)+1 (

m=n + 2) = A (m+n;n) (A (m+n;n)+1 ( m=n + 1)) A1 (A (m+n;n) ( (m + n)=n )) n:

Therefore ^ l=2 (n) = ^ (m+n;n)+1 (n) m=n + 2. The lemma follows. Remark. Hart and Sharir 19] proved a result similar to Lemma 3.9 concerning sequences of certain path compression operations on rooted ordered trees. Their result can be derived from the analogue of Lemma 3.9 for turns by interpreting turns in a binary tree as path compressions on the rooted ordered tree representation of the binary tree. It is interesting that they also use ideas similar to blocks and global tree in their proof. We estimate the cost of a sequence of deque operations performed at one end of a binary tree that also has left and right path rotations:

Lemma 3.10 Consider an intermixed sequence of Pops, Pushs, left path rotations and right path rotations performed on an arbitrary n-node binary tree. The total cost of Pop operations equals O((m + n) (m + n)), where m denotes the number of Pops and Pushs
in the sequence.

Proof. We simplify the sequence through a series of transformations without undercounting Pop rotations. Simpli cation 3.1 The rst operation of the sequence is a Pop.

64

CHAPTER 3. THE DEQUE CONJECTURE

and modify the initial tree by executing the deleted pre x of the sequence on it.

Transformation. Delete the operations preceding the rst Pop from the sequence

Simpli cation 3.2 The sequence does not contain Push operations. Transformation. For each Push operation, insert a node into the initial tree as the symmetric order successor of the last node that was popped before the Push. The Push operation itself is implemented by just rotating its corresponding node to the root
through right rotations. De ne a Partialpop to be a sequence of arbitrarily many right 2-turns performed on the leftmost node of a binary tree followed by deletion of the node.

Simpli cation 3.3 The sequence consists of only Partialpops and left path rotations; the lemma is true if the total cost of Partialpop operations equals O((m + n) (m + n)), where m denotes the number of Partialpops in the sequence and n denotes the size of
the initial tree.

the root into the left path and consider the resulting sequence.

Transformation. Normalize the tree by rotating the nodes on the right path across

Simpli cation 3.4 The sequence comprises only right cascades; the lemma is true if
the total cost of any m cascades in the sequence equals O((m + n) (m + n)).

upwards to the right path. The lemma follows from Simpli cation 4 and Lemma 3.9. The upper bound for the Deque Conjecture is given by:

Transformation. Instead of deleting nodes at the end of Partialpops, rotate them

Theorem 3.7 The cost of performing an intermixed sequence of m deque operations on
an arbitrary n-node binary tree using splay equals O((m + n) (m + n)).

rst epoch comprises the rst maxf n=2 ; 1g operations in the sequence. For all i 1, if the tree contains k nodes at the end of epoch i, then epoch i + 1 consists of the

Proof. Divide the sequence of operations into a series of epochs as follows: The

3.4. NEW PROOFS OF THE SCANNING THEOREM

65

next maxf k=2 ; 1g operations in the sequence. The last epoch might consist of fewer operations than speci ed. It su ces to show that the cost of an epoch that starts with a k-node tree is O(k (k)), since the sum of the sizes of the starting trees over all epochs is O(m + n). Consider an epoch whose initial tree, say T , has k 2 nodes. Divide T into a left block of k=2 nodes and a right block of k=2 nodes. This partitioning ensures that neither block gets depleted before the epoch completes. The total cost of Pushs and Injects is 0, since only rotations contribute to the operation cost. We show that the total cost of Pops is O(k (k)). The same proof will apply to Ejects. A Pop on T translates into a Pop on the left block. The e ect of a Pop on the right block is a series of left path rotations. It is easy to see that the total number of single rotations performed by a Pop is at most (the number of single rotations performed by the Pop on the left block) + 2(the number of left path rotations performed on the right block) + 2: A Push operation on the tree propagates as a Push on the left block. An Eject performs only right path rotations on the left block. An Inject does not a ect the left block. Hence by Lemma 3.10, the total number of single rotations performed by all the Pops on the left block equals O(2 k=2 (2 k=2 )) = O(k (k)). A left path rotation on the right block decreases the size of the left path of the block by 1. The initial size of this path is at most k=2 and the size increases by at most 1 per deque operation. Therefore the total number of left path rotations performed on the right block due to Pops is at most k + 1. This leads to an O(k (k)) upper bound on the total cost of all the Pops performed during the epoch.

3.4 New Proofs of the Scanning Theorem
In the two subsections of this section, we describe a simple potential-based proof of the Scanning Theorem and an inductive proof that generalizes the theorem.

66

CHAPTER 3. THE DEQUE CONJECTURE

3.4.1 A Potential-based Proof
The proof rests on the observation that a certain subtree of the binary tree, called the kernel tree, which is mainly involved in the splay operations always has a very nice shape. As the nodes of the original tree are accessed using splays, the kernel tree evolves through insertions and deletions of nodes at the left end, and left path cascades caused by the splays. Each node of the kernel tree is assigned a unimodal potential function, that is, a potential function that initially steadily increases to a maximum value and then steadily decreases once the node has progressed su ciently through the kernel tree. The nice shape of the kernel tree guarantees that most of the nodes involved in each splay are in their potential decrease phase, enabling their decrease in potentials to pay for all the rotations and the small increase in potentials of the nodes in their potential increase phase. We need some de nitions. A binary tree is called rightist if the depths of the leaves of the tree increase from left to right. The left and right heights of a binary tree are de ned, respectively, to be the depths of the leftmost and rightmost nodes. The right inner height of a node x is de ned to be the depth of the successor of x within x's subtree if x has a right subtree and 0 otherwise. We are ready to describe the proof. At any time during the sequence of splays, the set of nodes in the current tree that have been involved in a splay rotation form a connected subtree of the tree, called the kernel tree, whose root coincides with the root of the right subtree of the tree. Initially, the kernel tree is empty. The sequence of splays on the the original tree propagates into an intermixed sequence of n Pushs and n Pops on the kernel tree, where a Push inserts a new node at the bottom of the left path of the tree and a Pop splays at and deletes the leftmost node of the tree. Our goal is to show that the cost of the sequence of operations on the kernel tree equals O(n). The theorem would then follow immediately. The argument focuses on the sequence of operations on the kernel tree. Since the kernel tree is created by a sequence of Pushs and Pops, it satis es the following two properties: 1. The subtrees hanging from the left and right paths of the tree are rightist. 2. If T1 and T2 are subtrees hanging from the left path with T1 to the left of T2 , then

3.4. NEW PROOFS OF THE SCANNING THEOREM
rightheight(T1) leftheight(T2 ).

67

This can be easily shown using induction. We use the following potential function. The potential of the kernel tree equals the sum of the potentials of all its nodes. The potential of a node consists of an essential component and a nonessential component. For any node x, let ld(x) and rih(x) denote, respectively, the left depth and the right inner height of x. The essential potential of x equals minf log ld(x) ; rih(x)g unless x is on the right path in which case its essential potential equals 0. The essential potential of a node is a unimodal function of time, since the potential rst monotonely increases from 0 until the node's right inner height overtakes the logarithm of its left depth and then monotonely decreases. The nonessential potential of x equals 2 units if x is not on the right path and x's left child has the same right inner height as x, and equals 0 otherwise. We compute the amortized cost of kernel tree operations. Push has amortized cost 2, to provide for the nonessential potential that may be needed by the parent of the inserted node. Consider a Pop. Let x denote the lowest node on the left path such rih(x). Every double rotation of a splay step that involves two that log ld(x) nodes with identical right inner heights is paid for using the nonessential potential of the node leaving the left path. The number of remaining double rotations is at most ld(x)=2 + log(ld(x) + 1) . The rst term accounts for the double rotations involving two proper ancestors of x and the second term accounts for the double rotations involving the descendents of x. Each latter category rotation increases the potential by at most 1, contributing to a net increase of at most log(ld(x) + 1) units of potential. The halving of the left depths of the ancestors of x caused by the splay operation decreases the potential by exactly ld(x) ? 1. The amortized cost of Pop is therefore bounded by

ld(x)=2 + 2 log(ld(x) + 1) ? (ld(x) ? 1) 5:
We conclude that at most 7n double rotations, hence at most 15n single rotations, are performed by the sequence of operations on the kernel tree. This proves the Scanning Theorem.

68

CHAPTER 3. THE DEQUE CONJECTURE

3.4.2 An Inductive Proof
In this section, we describe an inductive proof of a generalization of the Scanning Theorem. The proof technique is similar to the method used to derive the upper bounds in Section 3.2.1. The binary tree is partitioned into blocks of constant size so that the total number of single rotations within blocks is linear. The induction is applied to a global tree consisting of a constant fraction of the tree nodes. Since a splay on the original tree translates into a much weaker rotation on the global tree, we have to incorporate the strength of the rotations into the inductive hypothesis. We state the result. For any positive integer k and real number d, such that 1 d n, a right k-twist is called d-shallow if the lowest node involved in the twist has a left depth of at most dk. Let S (d) (n) denote the maximum number of single rotations performed by d-shallow right twists in any right twist sequence executed on an n-node binary tree. We prove that S (d)(n) = O(dn). The Scanning Theorem follows from S (2)(n) = O(n). We estimate the number of d-shallow right twists in a right twist sequence:
twist sequence is at most 4dn.

Lemma 3.11 For any d 1, the total number of d-shallow right twists in any right Proof. Consider any d-shallow right twist that rotates a sequence of edges, say

x1; y1 ], x2; y2], . . ., xk; yk ], such that the left depths of the sequence of nodes xk , yk , xk?1 , yk?1 , . . ., x1, y1 is nonincreasing. Let ld(z) and ld0(z) denote, respectively, the left depths of any node z before and after the twist. For all i 2 k=2 ; k], we have ld0(xi ) = 1 ? i i 1 ? kd 1 ? 21d : ld(xi) ld(xi) In order to pay unit cost for a twist, we charge each node xi , such that i 2 k=2 ; k], minf2d=ld(xi); 1g debits. Let us prove that the total charge is at least 1. If ld(x k=2 ) 2d, then x k=2 is charged 1 debit. Otherwise, we have 1 2d=ld(xi) 2=k for all i k=2 . Since k=2 + 1 nodes are each charged at least 2=k debits, the net charge to
all the nodes is at least 1. Now, we bound the total charge to a node over the entire sequence. Call a node deep if its left depth is greater than 2d and shallow otherwise. Suppose that a node receives

3.4. NEW PROOFS OF THE SCANNING THEOREM
a sequence of charges 2d=Lk ,2d=Lk?1; . . . ; 2d=L0 while it is deep. Then Li > (1 ?2d 2d)i for all i 0. 1= Therefore the total charge to a node while it remains deep is at most (1 ? 1=2d)k + (1 ? 1=2d)k?1 + + 1 2d:

69

A node receives at most 2d debits while it is shallow. This implies that any node is charged at most 4d debits, giving a bound of 4dn for the total number of d-shallow right twists. The upper bound for S (d)(n) is given by:

Theorem 3.8 S d (n) 87dn for all d 1 and n 1.
( )

block except the rst contains exactly K = 29d nodes. The rst block may contain fewer nodes. In each block except the rst, the nodes with preorder numbers 1 to 4d within the block are global. The rst block does not contain any global nodes. Notice that the global nodes of a block form a connected subtree within the block whose root coincides with the root of the block. Further, if the left path of the block contains more than 4d nodes then all global nodes lie on the left path of the block. Otherwise all nodes on the left path of the block are global. The global nodes in the tree form a global tree as in the previous upper bound constructions. The size of the global tree is at most n=7:25. We analyze the e ect of a original tree rotation on the global tree. An interblock right single rotation translates into a corresponding rotation on the global tree if both nodes of the rotation are global. Otherwise the global tree is not a ected. The analysis of an intrablock right single rotation involves the following cases:

Proof. The proof uses induction ! n. on Case 1. n 174d: S d (n) n 87dn: 2 Case 2. n > 174d: Divide the tree into a sequence of n=K blocks such that each
( )

Local-local: The global tree is una ected. Local-global: Again, the global tree is not a ected, but the global role is transferred
from the global node to the local node.

70

CHAPTER 3. THE DEQUE CONJECTURE
the left subtree of x within the block contains only global nodes, then the rotation simply propagates to the global tree. Otherwise, p's global role is transferred to the node, say x0, in p's block that had preorder number 4d + 1 initially. Let p0 denote the lowest ancestor of x0 in the original tree which is global. The e ect of the transfer of global role on the structure of the global tree is to contract edge x; p] and add a new edge x0; p0]. We show that the same transformation is realizable through a series of right single rotations in the global tree. These rotations are performed by traversing the path from p to p0 in the global tree as follows (See Figure 3.8): Start at edge p; x] and repeat the following operation until the last edge on the path is reached: If the next edge on the path is a left edge, move to the next edge; otherwise, rotate the current edge and move to the next edge after the rotation. Finally, if x0 belongs to the right subtree of p0 in the original tree, rotate the last global tree edge traversed. Remark. The operation performs all the rotations within the subtree of the global tree rooted at x. This is seen as follows. If x = p0, then no rotations are performed on the global tree. Otherwise, p0 lies in the left subtree of x. Hence the successor of edge p; x] on the global tree path from p to p0 is a left edge. This implies that the operation does not rotate edge p; x]. Therefore all the rotations performed by the operation occur in the subtree of the global tree rooted at x. At any during this traversal, contracting the current edge results in a tree that is identical to the tree obtained by contracting the edge x; p] in the initial tree, so it follows that the above series of rotations on the global tree correctly simulates the rotation of edge x; p].

Global-global: Let x; p] denote the rotated edge such that p is the parent of x. If

In summary, a right single rotation of an edge x; p], such that p is the parent of x, either does not a ect the global tree, or translates into a rotation of the edge x; p] in the global tree, or translates into a sequence of right single rotations on the subtree of the global tree rooted at x. The rotation is called global if it results in a rotation of the corresponding edge in the global tree and local otherwise.

3.4. NEW PROOFS OF THE SCANNING THEOREM

71

* * * *

The original tree

x
*

p

g
* * *

*

g p
*

x
*

x0 p g

p0
The global tree

*

x0 x

p0 g

x

p0

Figure 3.8: The transfer of global role in an intrablock global-global rotation. Circles denote the nodes of the block. The starred nodes of the original tree are the global nodes.

x0

p0

72

CHAPTER 3. THE DEQUE CONJECTURE

Consider the e ect of a right twist in the original tree on the global tree. The sequence of single rotations on the global tree caused by the right twist comprises l-rotations, caused by local rotations in the twist, and g -rotations, caused by global rotations in the twist. The nodes involved in any l-rotation are distinct from the nodes involved in any previous g -rotation, hence we may transform the sequence of global tree rotations by moving each l-rotation before all the g -rotations without altering the net e ect of the sequence on the global tree. The su x of the sequence consisting of all the g -rotations de nes a global twist on the global tree. In summary, the e ect of a right twist in the original tree on the global tree is a right rotation followed by a global twist corresponding to the subsequence of global rotations in the twist. We estimate the number of single rotations performed by d-shallow twists in a right twist sequence executed on the tree. Consider any d-shallow twist in the sequence. De ne the left path of the twist to be the left path resulting from the contraction of the right edges on the access path of the lowest node involved in the twist. We classify the right single rotations performed by the twist as follows: Type 1. Local, interblock rotation in which the top node is global: There is at most one Type-1 rotation per twist because the left subtree of the bottom node of the rotation consists of only local nodes. Type 2. Local, interblock rotation in which the top node is local: The top node lies on the left path of its block and, since the node is local, it has 4d global ancestors within the block that lie on the left path of the twist. Notice that the top nodes of di erent Type-2 rotations belong to di erent blocks. Thus, if k2 denotes the number of Type-2 rotations performed by the twist, then the left path of the twist contains at least (4d + 1)k2 edges. Since the number of edges on the left path of the twist is bounded by dk, we obtain that k2 k=4 . Type 3. Local, intrablock rotation: For each Type-3 rotation, charge (8/3) debits to the block in which the rotation is performed. If the number of Type-3 rotations is at least (3k ? 4)=8, the total charges to the blocks plus a charge of (4/3) debits to the twist itself pays for all the rotations performed by the twist. Type 4. Global rotation: Only the situation where the number of Type-3 rotations

3.4. NEW PROOFS OF THE SCANNING THEOREM
is less than (3k ? 4)=8 needs to be considered. In this case at least

73

k ? 1 ? k=4 ? ( (3k ? 4)=8 ? 1) = k ? k=4 ? (3k + 3)=8

3k=8

global rotations are performed. Therefore the global twist performs at least 3k=8 rotations on the global tree, and it is (8d=3)-shallow. If we charge each such global twist (4/3) times the actual cost, then all the rotations can be paid for. This is seen as follows. Let k3 and k4 denote, respectively, the number of Type-3 and Type-4 rotations. Then, k3 + k4 3k=4 ? 1. The total charge is 8k3=3 + 4=3 + 4k4=3 which is minimized when k3 = 0. When k3 = 0, the total charge is at least 4=3 + (4=3)(3k=4 ? 1) k. Since each d-shallow twist is charged at most 4=3 debits, the total charge to all the d-shallow twists is at!most 16dn=3 by Lemma 3.11. The total charge to a block of size s is at most 8 s =3. It follows that the total charge to all the blocks is at most 2 4nK=3 116dn=3. By the inductive hypothesis, the total charge to all the (8d=3)shallow global twists is at most (4=3)(87)(8d=3)(n=7:25) = 128dn=3. Therefore the sum total of all the charges is bounded by 16dn=3 + 116dn=3 + 128dn=3 87dn, completing the induction step.

74

CHAPTER 3. THE DEQUE CONJECTURE

Chapter 4

Testing Set Equality
The problem of maintaining a dynamic collection of sets under various operations arises in numerous applications. A natural application is the implementation of high-level programming languages like SETL that support sets and permit operations such as equality, membership, union, intersection, etc. on them. The general problem of e ciently maintaining sets under all of these operations appears quite di cult. This chapter describes a fast data structure for maintaining sets under equality-tests and under creations of new sets through insertions and deletions of elements1 .

4.1 Introduction
The Set Equality-testing Problem is to maintain a collection of sets over a nite, ordered universe under the following operations:

Equal(S; T ): Test if S = T . Insert(S; x; T ): Create a new set T = S fxg. Delete(S; x; T ): Create a new set T = S nfxg.
The collection initially contains just the empty set. We would like to devise a data structure for this problem that tests equality of sets in constant time and executes the remaining operations as fast as possible, under this constraint.
1

The work of this chapter was reported in a joint-paper with Robert E. Tarjan 31].

75

76

CHAPTER 4. TESTING SET EQUALITY

If sets are represented by unique storage structures, then equality-testing of a pair of sets can be implemented in constant time by just checking whether they are represented by a single storage structure; uniqueness simply means that all the instances of a set are represented by a single storage structure. Following this natural approach, several people have devised unique storage representations for sets that allow constant time equality-tests and can be updated e ciently. Wegman and Carter 35] gave a randomized signature representation for sets that can be updated in constant time and constant space but errs with a small probability during equality-tests. Pugh 26] and Pugh and Tietelbaum 27] gave an error-free randomized binary trie representation for sets that can be updated in O(log n) expected time and O(log n) expected space, where n denotes the size of the updated set. Their data structures also support union and intersection of sets, although less e ciently. Yellin 40] gave a deterministic binary trie representation of sets that can be updated in O(log2 m) time and O(log m) space, where m denotes the total number of updates. We devise a deterministic data structure for the Set Equality-testing Problem requiring O(log m) amortized time and O(log m) space per update operation. The data structure is based on a solution to a more fundamental problem involving S-expressions. S-expressions 5] constitute the staple data type of programming language LISP. An S-expression is either an atom (signifying a number or a character string) or a pair of S-expressions. An atom S-expression is represented in storage by a node; a pair Sexpression is represented by a node with left and right pointers that point to nodes representing the component S-expressions. We store S-expressions uniquely, i.e. all instances of an S-expression are represented by a single node. Cons(s1,s2 ) returns the S-expression (s1:s2 ). A cascade of Cons operations is a sequence of Cons operations in which the result of each Cons operation is an input to the next Cons operation. For instance, s1 := Cons(s0; t0 ) s2 := Cons(s1; t1 ) . . . sf := Cons(sf ?1; tf ?1 ) is a cascade of f Cons operations. The S-expression problem in question is to devise a data structure for e ciently implementing cascades of Cons operations on uniquely stored S-expressions.

4.1. INTRODUCTION

77

Unique storage of S-expressions makes Cons operations expensive. Given a pair of S-expressions, a Cons operation has to check whether there is a third S-expression in the collection with these S-expressions as its component S-expressions. Viewing the collection of S-expressions as a dictionary, this is equivalent to performing a search operation, possibly followed by an insertion, on the dictionary. Single Cons operations p can be implemented in O( log F ) time and O(1) amortized space or, alternately, in O(1) time and O(F ) space, where F denotes the total number of Cons operations performed and is any positive constant. This implementation is based on Willard's data structure 37] for maintaining a dictionary in a small universe. Universal hashing 8] and dynamic perfect hashing 13] o er alternate implementations that require O(1) randomized amortized time and O(1) amortized space per Cons operation. We develop a data structure that performs a cascade of f Cons operations in O(f + log mc ) amortized time, where mc denotes the total number of cascades performed. The total space used is proportional to the number of distinct S-expressions present. This means that Cons operations can be implemented in constant amortized time and constant space in situations where these operations occur in long cascades. Our set-equality-testing data structure is an immediate corollary of this result. When sets are represented by binary tries, an update operation translates into a cascade of at most log m Cons operations and requires O(log m) amortized time using this data structure. Many list-oriented functions in functional languages (LISP, for instance) involve cascades of Cons operations and can be implemented e ciently using this method; function Append is a typical example:

Append( v ; v ; . . . ; vk ]; w ; w ; . . . ; wl]) s := Cons(vk ; w ; w ; . . . ; wl]) s := Cons(vk? ; s )
1 2 1 2 1 1 2 2

Result

. . . := Cons(v1; sk?1 )

1

1

The chapter is organized as follows. In Sections 4.2 and 4.3, we describe the data structure for equality-testing of sets and analyze its performance. In Section 4.4, we discuss directions for further work.

78

CHAPTER 4. TESTING SET EQUALITY

4.2 The Data Structure
We reduce the Set Equality-testing Problem to the problem of implementing cascades of Cons operations on uniquely stored S-expressions. The elements seen so far are numbered in serial order and de ne the current universe U = 1; jU j]. Each set is represented by a binary trie 21] in this universe. The binary trie representing a set S is an S-expression that stores the elements of S as atoms and is de ned recursively. Let 2p < jU j 2p+1. A singleton set is represented by an atom and the empty set, by the atom NIL. If jS j 2, then S is represented by a pair (s1 :s2 ), where s1 and s2 are, respectively, the S-expressions representing subsets S \ 1; 2p] and S \ 2p + 1; jU j] in their respective subuniverses. We store S-expressions uniquely so that two sets are equal if and only if their S-expressions are represented by a single node. A set update operation translates into a cascade of at most log jU j log m Cons operations, which can be implemented in O(log m) amortized time and O(log m) space using a method described below; m denotes the total number of update operations. We describe an e cient data structure for performing cascades of Cons operations on uniquely stored S-expressions. The data structure requires O(f + log mc ) amortized time to perform a cascade of f Cons operations, where mc denotes the total number of cascades performed. Consider the collection of nodes representing S-expressions. Number these nodes serially in their order of creation. A parent of a node v is de ned to be a node that points to v . Each node v maintains a set parents(v ) of all its parents. Each parent p 2 parents(v ) is assigned a key equal to (serial#(w); b), where w is the other node (besides v ) pointed to by p, and b equals 0 or 1 depending on whether the left pointer of p points to v or not. To perform a Cons operation on two nodes, v and w, we search the set parents(v) using the key (serial#(w); 0) and return the matching parent. If there is no matching parent, we create a new node p with pointers to v and w, set parents(p) to empty, insert p into parents(v) and parents(w), and return p. In a cascade of Cons operations, we implement each Cons operation by searching in the set of parents of the node returned by the previous Cons operation. We represent each set parents(v ) by a binary search tree and perform searches and insertions on the tree using the Splay Algorithm2 . A search operation is followed by a
2

The Splay Algorithm is described in Chapter 3, Section 3.1.1.

4.3. THE ANALYSIS

79

splay on the last-visited node during the search. A new element is inserted into the tree as follows. If the inserted element is larger than the current maximum element, insert it as the right child of the maximum element; this requires maintaining a pointer to the rightmost node in the tree. Otherwise insert the element into the tree in the standard top-down manner and then splay at the element. These two types of insertions are called passive and active, respectively. We implement passive insertions more e ciently since they are more numerous than active insertions.

4.3 The Analysis
The following theorem summarizes the performance of the data structure for Cons operations.

Theorem 4.1 The amortized cost of a cascade of f Cons operations equals O(f +
log mc ), where mc denotes the total number of cascades performed on S-expressions. The key idea behind the proof of this theorem is to bound the cost of operations on a parent set using a strong form of Sleator and Tarjan's Static Optimality Theorem 28]. We focus on the graph induced by the S-expression nodes, write the static optimality expressions for all these nodes, and bound the sum of the static optimality expressions over all the nodes, using the fact that S-expression nodes have at most two children (even though they might have unboundedly many parents). We state the lemmas used in proving the theorem. The following lemma uses the notion of blocks in a binary tree introduced in Chapter 3, Section 3.2.1, and occurs implicitly in the work of Cole et al. 11].

Lemma 4.1 Consider a binary search tree whose elements have been assigned arbitrary

nonnegative weights. Suppose that the tree is partitioned into blocks so that each block has a positive weight (the weight of a block equals the total weight of all the elements in it). Let n denote the number of elements in the tree and let nb denote the number of blocks. The cost of a sequence of m splays performed on the roots of the blocks equals b O(m + n + Pm log(W=wj ) + Pn=1 log(W=wi)), where W = the total weight of all the j =1 i elements, wj = the weight of the block of the j th accessed element, and wi = the weight of the ith block of the tree.

80

CHAPTER 4. TESTING SET EQUALITY

in Section 2, \Global insertions", and analyze the splays using their analysis of global insertions3 . Their analysis yields the following conclusions: the amortized cost of a splay on the root of a block with weight w equals O(1 + log(W=w)); the drop in potential over P b the entire sequence equals O( n=1 log(W=wi) + n). The result follows. i The following lemma bounds the cost of the sequence of operations performed on a single parent set and it is the key idea underlying the analysis.
empty) binary search tree using splays. Let fi = the number of searches of element i, F = the total number of searches, na = the number of active insertions, and n = the total number of insertions. P The cost of this sequence equals O(n + na log na + F + fi 1 fi log(F=fi )).

Proof. Assign potentials to the nodes of the tree as described by Cole et al. 11]

Lemma 4.2 Consider a sequence of insertions and searches performed on an (initially

according to their order of arrival (without splaying). On this tree, we perform the searches and simulate the insertions. Active insertions are simulated by splaying at the corresponding elements and passive insertions are simply ignored. We obtain a sequence of splays corresponding to active insertions and searches (active splays and hot splays, respectively). It su ces to bound the cost of this sequence. We bound the cost of this sequence by partitioning the tree into blocks and applying Lemma 4.1. Partition the tree into blocks as follows. The elements accessed by active and hot splays are, respectively, called active and hot. Every active or hot element forms a singleton block. Each nonempty interval of nodes between consecutive singleton blocks forms a passive block. Choose an element from each passive block and call it the block representative. Note that na = the number of active elements. The weight of element i is de ned by:
8 > fi > > < F=(n > > > :
3

Proof. We modify the sequence by preinserting all the elements into the initial tree

0

a + 1)

if the element is hot if the element is active but not hot if the element is in a passive block but not the representative

An account of this analysis can also be found in Cole 9], Section 4.

4.3. THE ANALYSIS

81

The representatives of na +1 of the passive blocks are each assigned a weight of F=(na +1); the representatives of the remaining passive blocks are placed in one-to-one correspondence with the set of hot elements and assigned the weights of their mates. The total weight of the tree is at most 4F . Applying Lemma 4.1, the cost of the sequence of splays equals

O(na + F + n +
2(
X

X

fi

log(4F=fi )) + (2na + 1) log(4(na + 1))) =

fi

fi log(4F=fi) + na log(4(na + 1)) +
X

1

1

O(n + na log na + F +

fi

fi log(F=fi)):

1

Theorem 28]. The term static optimality comes from the expression i fi log(F=fi) which gives the weighted path length of the optimal static binary tree whose leaves have weights f1 ; f2 ; . . . ; fn . Their theorem applies only to sequences of searches in which all the elements of the tree are accessed at least once. The use of Cole et al.'s sharper analysis 11] yielded our stronger lemma. The following graph inequality will help us to bound the sum of the static optimality expressions over the nodes of the S-expression graph, using the fact that the nodes of this graph have constant-bounded indegrees.
Let

Remark. The lemma is a strong form of Sleator and Tarjan's Static Optimality
P

Lemma 4.3 Consider a digraph G = (V; E ) and consider a collection of walks in G.
Fe Fv Wv idv
= the number of traversals of edge e in the walks, P = (v;w )2E F(v;w ) , for any vertex v , = the number of walks originating at vertex v , and = indegree(v ) + 1.
X
(

Then,

v;w)2E
(

F(v;w) log(Fv =F(v;w) )
) ( )

X

v2V

Fv log idv +
X

X

Fv

Wv log Fv :

1

X
(

Proof. Let F v;w = F v;w ? #walks with (v; w) as the last edge.
F(v;w) log(Fv =F(v;w) ) =
X

v;w)2E

Fv

1

Fv log Fv +

(

v;w)2E

F(v;w) log(1=F(v;w))

82
X

CHAPTER 4. TESTING SET EQUALITY
(x log(1=x) is decreasing in 1=e; 1]) X X X = Wv log Fv + F(v;w) log(Fw =F(v;w))
Fv
X
1

Fv

1

Wv log Fv +

X
(

x;v)2E

F(x;v) log Fv +

X
(

v;w)2E

F(v;w) log(1=F(v;w))

Fv

Wv log Fv +

Fw

X

1(

1

w2V

Fw log idw (entropy inequality).

v;w)2E

We are ready to prove the theorem. Proof of Theorem 4.1. Consider a sequence of mc cascades of Cons operations, comprising F Cons operations totally. The cost of a cascade of f Cons operations equals O(f ) plus the cost of operations performed on parent sets. During any cascade of Cons operations, there are at most two active insertions into parent sets. These insertions are performed when the rst node is created by the cascade; all subsequent insertions are passive. Hence, out of at most 2F insertions into parent sets totally performed during the sequence of cascades, at most 2mc insertions are active insertions. Applying Lemma 4.2 to the sequence of insertions and searches performed on each parent set and summing the costs over all parent sets, we see that the total cost of parent set operations equals

O(F + mc log mc +

X
nodes

X
v i 2 parents(v) ^ fi 1

fi log(F (v)=fi ));

where F (v ) denotes the total number of searches performed on parents(v ) and fi denotes the number of searches of element i among these. The double summation bounds the total cost of all searches performed on the parent sets. This summation can be bounded using Lemma 4.3. The collection of nodes at the end of the sequence of cascades induces a directed graph whose vertices are the S-expression nodes and whose edges go from nodes to their parents. The indegree of each vertex in this graph is at most 2. For each edge (v; w), de ne F(v;w) = the number of searches of node w performed on parents(v ). Delete all edges e such that Fe = 0. Applying Lemma 4.3 to the resulting graph, we see that the summation is bounded by F log 3 + mc log mc . It follows that the cost of the sequence of cascades equals O(F + mc log mc ). The theorem follows.

4.4. DIRECTIONS FOR FURTHER WORK

83

4.4 Directions for Further Work
The following open problems arise naturally in connection with this work: 1. Is there a data structure for implementing Cons operations in constant amortized time and constant amortized space, in general? 2. Prove (or disprove) that the problem of maintaining sets under the complete repertoire of set operations has no e cient solution. An e cient solution is one that implements all set operations in time polylogarithmic in the number of update operations. 3. The Sequence Equality-testing Problem 31] is to maintain a collection of sequences from a nite, ordered universe under equality-tests and under creations of new sequences through insertions and deletions of elements. There exists a data structure that performs equality-tests of sequences in constant time and updates sequences p in about n time/space, where n denotes the length of the updated sequence. The problem can be solved in O(log m) time/space per update operation if either sequences are repetition-free or randomization and a small error are permitted; m denotes the number of update operations. The existence of a deterministic (or even an error-free randomized) data structure that updates sequences in polylogarithmic time/space, in general, remains open.

84

CHAPTER 4. TESTING SET EQUALITY

Bibliography
1] A.V.Aho, J.E.Hopcroft, and J.D.Ullman. The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading, Mass., 1974. 2] A.V.Aho and D.Lee. Storing a dynamic sparse table. In Proc. 27th IEEE FOCS, 1986, 55-60. 3] M.Ajtai. A lower bound for nding predecessors in Yao's cell probe model. Combinatorica 8, 3, 1988, 235-247. 4] M.Ajtai, M.Fredman, and J.Komlos. Hash functions for priority queues. Information and Control 63, 1984, 217-225. 5] J.Allen. Anatomy of LISP. McGraw Hill Publishing Co., 1978. 6] J.Bentley and J.Saxe. Decomposable searching problems 1: Static-to-dynamic transformations. J. Algorithms 1, 1980, 301-358. 7] N.Blum. On the single operation worst-case time complexity of the disjoint set union problem. SIAM J. Computing 15, 1986, 1021-1024. 8] J.L.Carter and M.N.Wegman. Universal classes of hash functions. J. Comp. Sys. Sci., 18, 1979, 143-154. 9] R.Cole. On the dynamic nger conjecture for splay trees. In Proc. 22nd ACM STOC, 1990, 8-17. 10] R.Cole. On the dynamic nger conjecture for splay trees 2: Finger searching. Courant Institute Technical Report No. 472, 1989. 85

86

BIBLIOGRAPHY

11] R.Cole, B.Mishra, J.Schmidt, and A.Siegel. On the dynamic nger conjecture for splay trees 1: Splay-sorting (log n)-block sequences. Courant Institute Technical Report No. 471, 1989. 12] K.Culik II and D.Wood. A note on some tree similarity measures. Info. Process. Lett. 15, 1982, 39-42. 13] M.Dietzfelbinger, A.Karlin, K.Mehlhorn, F.Meyer auf der Heide, H.Rohnert, and R.E.Tarjan. Dynamic perfect hashing: Upper and lower bounds. In Proc. 29th IEEE FOCS, 1988, 524-531. 14] M.L.Fredman, J.Komlos, and E.Szemeredi. Storing a sparse table with O(1) worst case access time. J. ACM 31, 3, 1984, 538-544. 15] M.L.Fredman and M.E.Saks. The cell probe complexity of dynamic data structures. In Proc. 21st ACM STOC, 1989, 345-354. 16] M.L.Fredman, R.Sedgewick, D.D.Sleator, and R.E.Tarjan. The pairing heap: a new form of self-adjusting heap. Algorithmica 1, 1986, 111-129. 17] M.L.Fredman and D.E.Willard. Blasting through the information theoretic barrier with fusion trees. In Proc. 22nd STOC, 1990, 1-7. 18] I.Galperin and R.L.Rivest. Scapegoat trees. Manuscript, December 1990. 19] S.Hart and M.Sharir. Nonlinearity of Davenport-Schinzel sequences and of generalized path compression schemes. Combinatorica 6, 2, 1986, 151-177. 20] W.Hoe ding. Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association 58, 1963, 13-30. 21] D.E.Knuth. The Art of Computer Programming 3: Sorting and Searching. Addison-Wesley, Reading, Mass., 1973. 22] J.M.Lucas. Arbitrary splitting in splay trees. Rutgers University Tech. Rept. No. 234, June 1988. 23] K.Mehlhorn. Data Structures and Algorithms 1: Sorting and Searching. Springer-Verlag, 1984.

BIBLIOGRAPHY

87

24] K.Mehlhorn, S.Naher, and M.Rauch. On the complexity of a game related to the dictionary problem. In Proc. 30th IEEE FOCS, 1989, 546-548. 25] W.Paul and J.Simon. Decision trees and random access machines. Symposium uber logik and algorithmik, Zurich 1980; also in Mehlhorn 23, 85-97]. 26] W.Pugh. Incremental computation and the incremental evaluation of functional programming. Ph.D. Thesis, Cornell University, 1988. 27] W.Pugh and T.Teitelbaum. Incremental computation via function caching. In Proc. 16th ACM POPL, 1989, 315-328. 28] D.D.Sleator and R.E.Tarjan. Self-adjusting binary search trees. J. ACM, 32, 1985, 652-686. 29] D.D.Sleator, R.E.Tarjan, and W.P.Thurston. Rotation distance, triangulations, and hyperbolic geometry. J. Amer. Math. Soc. 1, 3, 1988, 647-681. 30] R.Sundar. Twists, turns, cascades, deque conjecture, and scanning theorem. In Proc. 30th IEEE FOCS, 1989, 555-559; On the deque conjecture for the splay algorithm. Combinatorica, to appear. 31] R.Sundar and R.E.Tarjan. Unique binary search tree representations and equalitytesting of sets and sequences. In Proc. 22nd ACM STOC, 1990, 18-25. 32] R.E.Tarjan. Data Structures and Network Algorithms. Society for Industrial and Applied Mathematics, Philadelphia, Pa., 1983. 33] R.E.Tarjan. Sequential access in splay trees takes linear time. Combinatorica 5, 1985, 367-378. 34] R.E.Tarjan. Amortized computational complexity. SIAM J. Appl. Discrete Meth. 6, 1985, 306-318. 35] M.N.Wegman and J.L.Carter. New hash functions and their use in authentication and set equality. J. Comp. Sys. Sci. 22, 1981, 265-279. 36] R.Wilber. Lower bounds for accessing binary search trees with rotations. SIAM J. Computing 18, 1989, 56-67.

88

BIBLIOGRAPHY

37] D.E.Willard. New trie data structures which support very fast search operations. J. Comp. Sys. Sci., 28, 1984, 379-394. 38] A.C.Yao. Should tables be sorted? J. ACM 28, 1981, 615-628. 39] A.C.Yao. On the complexity of maintaining partial sums. SIAM J. Comput. 14, 2, 1985, 277-288. 40] D.Yellin. Representing sets with constant time equality testing. IBM Tech. Rept., April 1990; In Proc. First Annual ACM-SIAM Symposium on Discrete Algorithms, 1990, 64-73.

...and Amortized Efficiency Of List Data Structures Editor_....pdf
Programming Techniques and Amortized Efficiency Of List Data Structures Editor_...We analyze the amortized complexity of LRU, showing that its efficiency ...
lec01.AmortizedAnalysis(C)_图文.pdf
lec01.AmortizedAnalysis(C)_电子/电路_工程科技_专业资料。Amortized Complexity ü?Aggregate method. ?? Accounting method. ?? Potential function method. Poten...

Efficiency: worst case, best case, and average, amortized analysis Asymptotic...Focus on efficiency, complexity, and correctness ?? Data structures ?? ...
Algorithmic_Time_Complexity_Basics-_图文.ppt
? The amortized runtime complexity of the algorithm is the function defined... data transfer/dependency arrow MS(n) Merge(n) Merge(n): Worst-case ...
Lecture7-ICImplementation_图文.pdf
Custom block can be reused many times, thus cost can be amortized over a...more complex structures ? Macrocells: cells that contain a complexity that ...
Dynamic Graph Shortest Path Algorithm.pdf
the amortized running time of their algorithm is..., we introduce some auxiliary data structures. ...The entire complexity of this algorithm is O(m ...

Advanced Data Structures and Algorithm Analysis ... Merge_Skew is in amortized O(log N) time, ...If so, the time complexity will be O(N1+N2)...
SELF-ADJUSTING HEAPS.pdf
Key words. Self-organizing data structure, amortized complexity, heap, priority queue 1. Introduction. Many kinds of data structures have been designed with...
A Tight Lower Bound for Top-Down Skew Heaps.pdf
Our methods resemble the methods used to obtain lower bounds on the amortized complexity of union- nd data structures (see, e.g., 1, 11, 12]), ...
(δγ,)-occurrencewithα.pdf
structures of these sequences, which are typically...-queue has an amortized constant time complexity....We have shown that the min-queue data structure...
Reflected min-max heaps.pdf
complexity 1 Introduction Priority queues are fundamental data structures that ...Fibonacci heaps are optimal in the amortized setting. In the worst-case ...
6.897 Advanced Data Structures Spring.pdf
6.897 Advanced Data Structures Spring_专业资料。...(n, w)) amortized per operation monotone ... algorithm with Inverse-Ackermann type complexity. ...
Characterizing History independent Data Structures.pdf
is a complexity separation between weak and strong history independence ....This technique combined with an amortized analysis yields data structures with...
ALG-Syllabus-English.doc
Amortized analysis Solving recurrences Problems ...DATA STRUCTURES Arrays, stack and queues Records ...COMPLEXITY Introduction: A simple example Information...
Data structures for halfplane proximity queries and ....pdf
Data structures for halfplane proximity queries and...(log n) amortized pointer changes, subject to ...cult because the complexity of the changes to ...
Raster Set Representations with Efficient JOIN Operator Josef....pdf
There are data structures with amortized complexity of O(N ) for sequences of N tests (that means constant average time for an individual test). We ...
Data Structures_图文.ppt
Mehta. Fundamentals of Data Structures in C++ (Second Edition). Silicon ... then we can amortize costs such that the amortized time complexity of ...
Proximate point searching.pdf
Data structures with the working set property can... have the same amortized asymptotic runtime as ...and the combinatorial complexity of the point set...
To be Decided.pdf
c structures and functionality based on patthat ...framework can be amortized over many projects, 3...complexity of the framework and the likelihood ...
6.897 Advanced Data Structures Spring.pdf
6.897 Advanced Data Structures Spring_专业资料。In the last lecture we ...Thus, the amortized time complexity of the search operation is O(2l ). ...