27 Splay Trees

T.V. Geetha

Welcome to the e-PG Pathshala Lecture Series on Data Structures. In this module we will discuss another self balbalanced tree – Splay Trees.

Learning Objectives

The learning objectives of the module are as follows:

•  To understand the idea behind Splay Trees

•  To discuss the cases of SplayTrees

•  To describe the operations of Splay Trees

•  To outline the advantages of Splay Trees

27.1 Basic Idea

The basic idea of the splay tree is thatevery time a node is accessed, assuming that access to this node will be needed immediately, it is pushed up to the root by a series of tree rotations knowing assplaying so that the search time for that node is the minimum. The idea is that if the node being splayedis deep, manynodes on the path to that node are alsodeep and by restructuring the tree, wemake access to all of those nodes cheaperin the future, again assuming that nodes nearer a node already accessed will be needed sooner than other nodes.

We carry out a“Blind” rebalancing height information is kept. In spite of this the worst-case time per operation is O(n) but the worst-case amortized time is O(log n). We had already discussed amortized analysis as the worst case analysis of the average cost per operation of a sequence of operations. During Insert/find operations we always rotate the inserted node or the node that is searched to the root. We maintain the property of good locality where we move the commonly accessed keys high up the tree so that they become easier and easier to find.

Figure 27.1 Splay Tree

We move the node n (the node just inserted or just searched for) to the root by a series of zig-zag and zig-zig rotations. When we are forced to make a deep access, we ensure that we also fix up a lot of deep nodes towards the root (Figure 27.1).

27.2 Splay Trees

Splay trees are binary search trees (BSTs) that are not perfectly balanced all the time but allow search and insertion operations to try to balance the tree so that future operations can run faster. The splay trees are based on the heuristic that if a node X is accessed once, it is likely to be accessed again.A fter node X is accessed, we perform “splaying” operations to bring X up to the root of the tree. We perform splaying in such a manner that it leaves the tree more or less balanced as a whole.

27.2.1 Motivating Example

Let us understand the concept of splay trees using a motivating example. In the example shown in Figure 27.2, after we search for 12, splaying with 12 makes the tree balancedand 12 moves to the root. Subsequent accesses for 12 will take O(1) time, We perform splay with active (recently accessed) nodes, they will move towards the root and inactive nodes will slowly move further from the root

27.3 Six Cases of Splaying

Let X be a non-root node, i.e., has at least 1 ancestor. Let P be its parent node and Let G be its grandparent node (if it exists). Now let us consider a path from G to X. Every time we traverse a left subtree, we have “zig”type of splay and correspondingly every time we traverse a right subtree, we have “zag” type of splay. Now with this basis let us discuss the six cases of splaying (Figure 27.3). The first case is a “zig”, when X is the left child of P. The second case is a “zag”, when X is the right child of P. Next is “zig-zig” when X is the left child of P and in turn P is left child of G. The fourth case is “zig-zag”, when P is left child of G, but X is the right child of P. The fifth case is “zag-zig”, when P is right child of G, and X is the left child of P. The fifth case is “zag-zig”, when P is right child of G, and X is the left child of P, the final sixth case is “zag-zag”, when X is the right child of P and in turn P is right child of G.

27.4 Splay Operation

Now let us discuss the splay operation in detail. We traverse the tree from node x we want to splay to root, rotating along the way until xis the root.

Rotation

Now at each rotation, if x is the root, do nothing.

If x has no grandparent, rotate x about its parent.

If x has a grandparent,

• if x and its parent are both left children or both right children
• rotate the parent about the grandparent, then
• rotate x about its parent
• if x and its parent are opposite type children (one left and the other right)
• rotate x about its parent, then
• Rotate x about its new parent (former grandparent)

27.5 Operations of Splay Trees

27.5.1 Insertion Operation

As usual for every balanced tree we first insert as we do into a normal binary search tree. Our next step is to splay the inserted node. if there is a duplicate, the node that holds the duplicate element is splayed.

27.5.2 Find Operation

We first search for the node, if we find the node we splay to the root. Otherwise we splay the last node that was found of the path we traversed while searching.

27.5.3 Splay Operation

When node X is accessed either as a result of inserting X or during the find operation, we need to apply one of six rotation operations. In the splay terminology right rotates are called “zig” while left rotates are called “Zag”.

27.5.3.1 Single Rotations

There are two cases of single rotations, zig and zag. This happens when X has a parent P but no grandparent G.

27.5.3.1.1 Zig Operation

“Zig” operation is just a single rotation, as in a tree. Suppose 6 was the node that was accessed (e.g. using Search). Here X (6) is a left child of the parent P (15) but no grandparent. Figure 27.4 shows the example of Zig-Right,a single right rotation of 6 about the pivot 15 whichmoves 6 to the root. This splay operation allows 6 to be accessed faster next time in the O(1).

“Zag” is just a single rotation, again as in the AVL tree rotation. Suppose 15 was the node that was accessed (e.g., using Search). Here X (15) is a right child of the parent P (6) but no grandparent. Figure 27.5 shows the example of Zag-Left, a single left rotation of 15 about the pivot 6 which moves 15 to the root. This splay operation allows 15 to be accessed faster next time in the O(1).

27.5.3.2 Double Rotations

Thereare four cases of double rotations, zig-zig, zig-zag, zag-zig, and zag-zag. This happens when X has a parent P and P has parent G.

27.5.3.2.1 Zig-Zig Operation

“Zig-Zig” consists of two single rotations of the same type. Suppose 3 was the node that was accessed (e.g., using Search). Here X (3) is the left child of parent P (6) and has a grandparent GP (15). P (6) is the left child of grandparent GP (15). Due to “zig-zig” splaying, 3 has to be bubbled to the top (Figure 27.6). First we Zig-Right, a single right rotate of P (6) about GP (15). Now P (6) becomes the root whose left child is X (3). Now we again carry out a Zig-Right, a single right rotate of X (3) about P (6). Now X (3) becomes the root and will be accessed faster next time in the O(1). In this case, first P is right rotated about GP and then X is right rotated about P. Note that parent-grandparent is rotated first.

Figure 27.7 “Zag-Zig” Operation

“Zag-Zig” consists of two consists of two rotations of the opposite type. Suppose 12 was the node that was accessed (e.g., using Search). Here X (12) is the right child of parent P (6) and has a grandparent GP (15). P (6) is the left child of grandparent GP (15). Due to “zag-zig” splaying, 3 bubbles to the top (Figure 27.7). First we Zag-Left, a single left rotate of X (12) about P (6). Now P (6) becomes the left child of X (12). Now we again carry out a Zig-Right, a single right rotate of X (12) about GP (15). Now X (12) becomes the root and will be accessed faster next time in the O(1). In this case first X is left rotated about P and then X is again right rotated about GP. Notice that this is simply an LR imbalance correction in tree terminology (first a left rotation, then a right rotation).

27.5.3.2.3 Zig-Zag Operation

“Zig-Zag” consists of two consists of two rotations of the opposite type. Suppose 17 was the node that was accessed (e.g., using Search). Here X (17) is the left child of parent P (20) and has a grandparent GP (15). P (20) is the right child of grandparent GP (15). Due to “zig-zag” splaying, 17 bubbles to the top (Figure 27.8). First we Zig-Right, a single right rotate of X (17) about P (20). Now P (20) becomes the right child of X (17). Now we again carry out a Zag-left, a single left rotate of X (17) about GP (15). Now X (17) becomes the root and will be accessed faster next time in the O(1). In this case first X is right rotated about P and then X is again left rotated about GP. Notice that this is simply an RL imbalance correction in AVL tree terminology (first a right rotation, then a left rotation).

 “Zag-Zag” consists of two single rotations of the same type. Suppose 30 was the node that was accessed (e.g., using Search). Here X (30) is the right child of parent P (20) and has a grandparent GP (15). P (20) is the right child of grandparent GP (15). Due to “zag-zag” splaying, 30 has to be bubbled to the top (Figure 27.9). First we Zag-left, a single left rotate of P (20) about GP (15). Now P (20) becomes the root whose rightchild is X (30). Now we again carry out a Zag-Left, a single left rotate of X (30) about P (20). Now X (30) becomes the root and will be accessed faster next time in the O(1). In this case, first P is left rotated about GP and then X is left rotated about P. Note that parent-grandparent is rotated first.

27.6 Splay Trees: Examples

The first example we will see is a series of operations of the same type. In the example shown in Figure 27.10, 40 is accessed. 40 is down at the fifth level of the tree. Now we want to keep rotating till 40 bubbles to the top and becomes the root. Now X (40) is the left child of parent P (50) who is itself the left child of grandparent GP (60). We first carry out a Zig, right rotation of 40 about 50. Again we carry out a Zig, right rotation of 40 about 60. Now again we carry out a Zig, right rotation of 40 about 70, and again a Zig, right rotation of 40 about the root of the tree 80. Thus after a series of 4 Zig operations, the node last accessed 40, bubbles up to become the root so that next time it can be accessed fast.

Figure 27.11 Example where 60 is Accessed

The second example we will see is a series of operations of the different types.In the example shown in Figure 27.11, 60 is accessed. 60 is down at the fourth level of the tree. Now we want to keep rotating till 60 bubbles to the top and becomes the root. Now X (60) is the right child of parent P (50) who is itself the left child of grandparent GP (70). We first carry out a Zag, left rotation of 60 about 50. Now we carry out a Zig, right rotation of 60 about 70. Now we carry out a Zag, left rotation of 60 about the root of the tree 40. Thus after a series of 3 operations, Zag, Zig and Zag operations, the node last accessed 60, bubbles up to become the root so that next time it can be accessed fast.

27.7 Why Splaying Helps

Now we note that the node to be splayed n and its children are always helped that is go up the tree. Except for last step, nodes that are hurt by a zig-zag or zig-zig are later helped by a rotation higher up the tree. The result is that the shallow nodes may increase depth by one or two but other nodes decrease depth by a large amount. If a node n on the access path is at depth d before the splay, it’s at about depth d/2 after the splay. Exceptions are the root, the child of the root, and the node that is splayed.

27.8 Splaying during other operations

Splaying can be done not just after search, but also after other operations such as Insert/Delete. After an insert operation of node X, which is normally inserting X at a leaf node which is what will happen in a regular BST, we need to splay X up to the root. For deleting a node X, we carry out asearch on X and get X up to the root. We delete X at the root and move the largest item in its left sub-tree, i.e, its predecessor, to the root using splaying.

27.9Splaying Operations with Splitting Trees

In general, for an insert operation, we could do an ordinary BST insert, but that would not fix up the tree. We could do a BST insert followed by a find for splaying. However a better idea is to carry out the splay before the insert operation. For this purpose we need to split the tree T, Split(T, x) which creates two BST’s L and R, such that all elements of T are in either L or R, all elements in L are £ x and all elements in R are > x. Here x is the node to be inserted. Note that L and R share no elements. Now we insert at the root whose children will be L and R.

27.9.1 Splitting a Tree

Now the question is how do we split? We can find x or the parent of where x would be if we were to insert it as an ordinary BST. After this we can splay x or the parent to the root and then break one of the links from the root to a child (Figure 27.12).

27.9.2 Insert Example with Splitting

The insert example with splitting is shown in Figure 27.13. First we have the original tree. Now suppose we want to insert 5 then we need to split with 5. In other words we split the tree into two components L and R such that all nodes in L are £5 and all nodes in R are >5. In order to do this we need to move a node that is largest in the tree but which is less than 5 up the tree, in our example node 4. For this we carry out the appropriate splay operations. Now we join the tree by inserting 5 as the root with L and R as it’s left and right sub trees respectively.

27.9.2 Delete Example with Splitting

The delete example with splitting is shown in Figure 27.13. First we have the original tree. Now we first find 4, the node to be deleted, and splay 4. Now we have 4 at the root of the tree. We delete 4 and split the tree into two components L and R such that all nodes in L are <4 and all nodes in R are >4. Now we splay on the maximum element in L such that this maximum element is now the root of L. Now we join R as the right sub tree of this root of L. Now we have the tree with the node 4 deleted.

27.10Analysis of Splay Trees

The examples we have seen suggest that splaying causes the tree to get balanced. By analyzing the splay operation we can prove that any sequence of M operations on a splay tree of size N takes O(M log N) time. So, the amortized running time for one operation is O(log N).This guarantees that even if the depths of some nodes get very large, you cannot get a long sequence of O(N) searches because each search operation causes a rebalance. On the other hand without splaying, total time could be O(MN).

27.11 Advantages of Splay Trees

Splay trees are arguably the most practical kind of self-balancing trees. They do not need any extra information to be stored in the node, such as color, level, etc. These trees are balanced in an amortized sense that is running time on the average isO(mlogn) for m operations. The splay tree can be adapted to the ways in which items are being accessed in a dictionary to achieve faster running times for the frequently accessed items with (O(1)) while trees such as AVL is about O(log n). If number of finds is much larger than n, then locality is crucial, example in applications such as word-counting. Splay trees also support efficient split and join operations. They areand useful for other tasks such as for range queries.

Summary

• Explained the idea behind Splay Trees
• Discussed the 6 cases of SplayTrees
• Described the operations of Splay Trees
• Outlined some of the advantages of Splay Trees