Sections Summary Operations Splay Rotations References Visualize Tree Operations Algorithm Visualization Homepage

Splay Trees Summary Splay Trees were invented by Sleator and Tarjan. This data structure is essentially a binary tree with special update and access rules. It has the wonderful property to adapt optimally to a sequence of tree operations. More precisely, a sequence of m operations on a tree with initially n nodes takes time O (n ln (n) + m ln (n)). Operations Splay trees support the following operations. We write S for sets, x for elements and k for key values. splay(S,k) returns an access to an element x with key k in the set S. In case no such element exists, we return an access to the next smaller or larger element. split(S,k) returns (S_1,S_2), where for each x in S_1 holds: key[x] <= k , and for each y in S_2 holds: k < key[y] . join(S_1,S_2) returns the union S = S_1 + S_2. Condition: for each x in S_1 and each y in S_2: x <= y. insert(S,x) augments S by x. delete(S,x) removes x from S. Each split, join, delete and insert operation can be reduced to splay operations and modifications of the tree at the root which take only constant time. Thus, the run time for each operation is essentially the same as for a splay operation. Splay Operation The most important tree operation is splay(x), which moves an element x to the root of the tree. In case x is not present in the tree, the last element on the search path for x is moved instead. The run time for a splay(x) operation is proportional to the length of the search path for x: While searching for x we traverse the search path top-down. Let y be the last node on that path. In a second step, we move y along that path by applying rotations as described later. The time complexity of maintaining a splay trees is analyzed using an Amortized Analysis. Consider a sequence of operations op_1, op_2, ..., op_m. Assume that our data structure has a potential. One can think of the potential as a bank account. Each tree operation op_i has actual costs proportional to its running time. We're paying for the costs c_i of op_i with its amortized costs a_i. The difference between concrete and amortized costs is charged against the potential of the data structure. This means that we're investing in the potential if the amortized costs are higher that the actual costs, otherwise we're decreasing the potential. Thus, we're paying for the sequence op_1, op_2, ..., op_m no more than the initial potential plus the sum of the amortized costs a_1 + a_2 + ... + a_m. The trick of the analysis is to define a potential function and to show that each splay operation has amortized costs O (ln (n)). It follows that the sequence has costs O (m ln (n) + n ln (n)) . Example The examples illustrate a splay operation on a leaf node in a complete binary tree and a splay operation on tree in form of a linear list. Observe how each tree is changing while the splayed element is rotated to the root. Rotations The splay operation moves the accessed element x to the root of the tree T. This is done using rotations on x and parent y and grandparent z. There are two kinds of double rotations and one single rotation. Due to symmetry, we need mirror-image versions of each rotation. Type 1:    x < y < z ,   or    z < y < x   respectively. Type 2:    y < x < z ,   or    z < x < y   respectively. Type 3: The last case deals with the situation that the splay node x is a child of the root. Thus, we need a single rotation.    x < y ,   or    y < x   respectively. References [1] Data Structures and Their Algorithms, Lewis and Denenberg, Harper Collins, 1991, pp 243-251. [2] "Self-adjusting Binary Search Trees", Sleator and Tarjan, JACM Volume 32, No 3, July 1985, pp 652-686. [3] Data Structure and Algorithm Analysis, Mark Weiss, Benjamin Cummins, 1992, pp 119-130. [4] Data Structures, Algorithms, and Performance, Derick Wood, Addison-Wesley, 1993, pp 367-375