ABSTRACT
There are various data structures like AVL-trees, red-black trees, 2-3-trees (Chapter 10) which support operations like insert, delete (including deleting the minimum item), search (or membership) in O(log n) time (for each operation). Splay trees, introduced by Sleator and Tarjan [13, 15] support all these operations in O(log n) amortized time, which roughly means that starting from an empty tree, a sequence of m of these operations will take O(m log n) time (deterministic), an individual operation may take either more time or less time (see Theorem 12.1). We discuss some applications in the rest of this section.
