MIT OpenCourseWarehttp://ocw.mit.edu 6.854J / 18.415J Advanced Algorithms Fall 2008��For information about citing these materials or our Terms of Use, visit: http://ocw.mit.edu/terms.18.415/6.854 Advanced Algorithms September 24, 2008 Lecture 6 - Splay Trees Lecturer: Michel X. Goemans 1 Introduction In this lecture, we investigate splay trees, a type of binary search tree (BST) first formulated by Sleator and Tarjan in 1985. Splay trees are self-adjusting BSTs that have the additional helpful property that more commonly accessed nodes are more quickly retrieved. They have good behavior when compared to many other types of self-balancing BSTs, e ven when the operations are unknown and non-uniform. While in the worst case, operations can take O(n) time, splay tree s maintain O(log n) amortized cost for basic BST operations, and are within a constant factor to the cost of any static BST. We first give an overview of the operations used in splay trees, then give an amortized analysis of its behavior. We conclude by noting its behavior relative to other Binary Search Trees. 2 Splay Tree Structure A splay tree is a dynamic binary search tree, meaning that it p e rforms additional operations to optimize behavior. Because they are BSTs, given a node x in a splay tree and a node y in the left subtree of x, we have key(y) < key(x). Similarly, for a node z in the right subtree of x, we have key(x) < key(z). This is the binary search tree property. A well-balanced splay tree will have height Θ(log(n), where n is the number of nodes. Splay trees achieve their efficiency through use of the following operations: 2.1 Rotation The basic operation used in splay trees (or any other dynamic BST) is the rotation. A rotation involves rearranging the nodes of a subtree rooted at y so that one of the children x of y be com es the new root of the subtree, while maintaining the binary search tree property. This is illustrated in Figure 1. When the left child becomes the new root, the rotation is a right rotation. When the right child becomes the new ro ot, the rotation is a le ft rotation. We call a right rotation a zig and a left rotation a zag. The key idea of the splay tree is to bring node x to the root of the tree when accessing x via rotations. This brings the most recently accessed nodes closer to the top of the tree. However, there are many ways of bringing a node to the root via rotations, and we must therefore specify in which order we perform them. Consider a linear tree (effec tively a linked list) of the values 1, . . . , n, rooted at n. Suppose we acc ess the value 1. If we use the naive (and most natural) method of repeatedly performing a zig to bring 1 at the top, we proceed as illustrated in Figure 2. The resulting tree has the same height as the original tree, and is c learly not better balanced. We must try a more clever approach than successive, single rotations. 6 - Splay Trees-1Figure 1: Rotation via zigs and zags. Figure 2: When we access node 1 and try to bring it up via pure rotations, the result is a tree that is just as unbalanced as before. 2.2 Splay-Step We now define an operation called splay-step. In one splay-step on a node x, x is brought up 2 levels with rotations (or just 1 level if x’s parent is the root). When some node x is accessed in the splay tree, we bring x up with a series of splay-steps until it is the root. We separate the actions performed for the splay-step into the following categories. Call the node that we are trying to access x, its parent y, and y’s parent z. • Case 0: x is the root. Do nothing in this case. • Case 1: y is the root. If x is the left child of the root, perform a zig on x and y. If not, perform a zag. • Case 2: x and y are both left children (or both right children). Let us look at the case when both x and y are left children. We first do a zig on the y-z connection. Then, we do a zig on the x-y connection. If x and y are right children, we do the same thing, but with zags instead. (See Figure 3.) • Case 3: x is a left child and y is a right child, or vice versa. Consider the case where x is a right child, and y is a left child. We first do a zag on the x-y edge, and then a zig on the x-z edge. In the case where x is a left child and y a right child, we do the same thing, but with a zig on the first move, followed by a zag. (See Figure 4.) 6 - Splay Trees-2�Figure 3: Cas e 2 of the splay-step is when x and y are the same type of children. In this figure, we first do a zig on y − z, and then a zig on x − z. Figure 4: In Case 3, x and y are not the same type of children. In this c ase , we do a zag on the x − y edge, and then a zig on the x − z edge. Note that in the case of the earlier example with the chain of nodes, using splay-step instead of direct rotations results in a much more balanced tree, see Figure 5. 2.3 Splay With the splay-step operation, we can bring the node x to the root of the splay tree with the procedure: splay(x): WHILE x=root: DO splay-step(x) The described pro c edure performs the splay operation in a bottom-up order. It is possible to perform the splay operation in a top down fashion, which would result in the same running time. 6 - Splay Trees-3� Figure 5: When splaying node 1, the resulting tree has half its original height. 3 Running-Time Analysis 3.1 Potential Function We define a class of potential functions for the amortized analysis of operations on a splay tree. The potential function depends on weights that we can choose. For each node x in the tree, make the following definitions: • T (x) is the subtree rooted at x (and it includes teh node x itself), • weight function: w(x) > 0 is the weight of node x (we can choose what this is; we’ll often take w(x) = 1 for all nodes x) • weight-sum function: s(x) = w(y), y ∈T (x) • rank function: r(x) = log2 s(x). 6 - Splay Trees-4� � � Then we define the potential function as: φ = r(x). x∈T (root) 3.2 Amortized Cost of Splay(x) Using the potential function described above, we can show that the amortized cost of the splay operation is O(log n). For the purposes of cost analysis, we assume a rotation takes 1 unit of time. Lemma 1 For a splay-step operation on x that transforms the rank function r into r�,