# CHAPTER 12: SPLAY TREES

The balanced trees presented in Chapter 11 are optimal when the keys in the trees are accessed in a uniform way. However, if a few keys are accessed more frequently than others, a balanced tree isn't necessarily the best choice. It's better to have the most frequently used keys close to the top of the tree, so that the searching costs, amortized over the life of the tree, are optimal. We'll now take a look at data structures called splay trees that have this goal in mind. Splay trees were invented by D. Sleator and R. Tarjan. See [Sleatar 85] for the definitive paper on splay trees. These intriguing structures have many uses, but we'll examine them in the context of binary search trees and priority queues.

## SELF-ORGANIZING TREES

Rotation is the best way to move a node to the top, since this approach preserves the binary search tree property. Various strategies are possible for choosing the rotations to perform. In one strategy, a single rotation is used to move the desired node one level closer to the root. Another strategy involves moving the node all the way to the top using a series of single rotations. Unfortunately, neither of these strategies performs well in practice. However, a third approach does a yield good results: splaying.

## Bottom-Up Splaying

1. Zig.When the desired node is one level below the root, a single rotation is performed (called a zig in splaying parlance) to move the node to the root. Figure 12.1(a) shows an example. (There is also a symmetrical orientation, which is not shown.)

2. Zig-zig. When the desired node is more than one level deep, and the parent and grandparent are aligned the same way, two single rotations in the same direction (called a zig-zig) are performed to move the node closer to the root. Figure 12.1(b) shows an example. (Again, there is a symmetrical orientation not shown.)

3. Zig-zag. When the desired node is more than one level deep, and its parent and grandparent are aligned in opposite directions, then a double rotation (called a zig-zag) is performed. Figure 12.1(c) shows an example (with the symmetrical case omitted once again).

#### (c) Zig-zag (double rotation)

Figure 12.2 shows a complete example of splaying, with all three rules being applied. In this example, node c is the desired node to be moved to the root. Note that the tree undergoes a large amount of restructuring. This is typical of splaying. Don't be misled by the fact that the final tree is more balanced than the original. Splaying can greatly unbalance the tree. For example, Figure 12.3 shows how accessing the nodes of a tree in sorted order can lead to a degenerate tree.

The purpose of splaying isn't to balance the tree, but rather to move the most frequently used nodes to the top. Splay trees have been found to have the following behavior: For a tree of n nodes, as many as n steps may be required to find any given node. This happens when searching for a node at the bottom of a degenerate tree. However, if a sufficiently long series of searches is performed, the searching averages out to just log n steps, due to the way splaying restructures the tree. In other words, splay trees have an amortized efficiency of logn, the same as for balanced trees. Unfortunately, splay trees have the same worst case that linked lists have.

## Top-Down Splaying

It's possible to combine splaying and searching into a single top-down pass, eliminating the problem of finding the parents. In top-down splaying, the strategy is to split the tree into middle, left, and right subtrees. The middle subtree contains that portion of the splayed tree not yet visited. The left subtree contains those nodes known to be smaller than any node in the middle subtree, and the right subtree contains those nodes known to be greater than any node in the middle subtree. As we pass down the tree searching for the desired node, we perform the required splaying rotations and then split off chunks of the tree, attaching them to either the left or right subtrees. When the splaying is finished, the trees are combined again to produce the splayed tree.

In the figures to follow, the left subtree is labelled L and the right subtree is labelled R. The root nodes are actually dummy header nodes holding no data. In the left subtree, nodes are always attached on the right side. In fact, the attachment point, drawn as a black square, is always the right child of the maximum node. The left child link of L, which would otherwise be null, is used to point directly to the maximum node. When L is empty, we make the left child link point back to L. The right subtree has a symmetrical orientation, with the attachment point always the left child of the minimum node, and with the right child of R pointing to the minimum node.

As is true with bottom-up splaying, top-down splaying involves three configurations. The zig operation, which corresponds to a single rotation, is accomplished by cutting off part of the tree and attaching it to the appropriate subtree, depending on the direction of the rotation. Figure 12.4 illustrates the process. Note that the splayed node becomes the root of the middle subtree. The following LinkRight( ) and LinkLeft( ) routines show how the attachments can be coded. Here, p is the root of the middle subtree, and l and r point to the roots of the left and right subtrees, respectively. The routines use generic Bnodeb pointers, and thus are independent of the data stored in the nodes.

// p->left becomes the new parent of the tree that p

// used to belong to, so we return p->left

{

Bnodeb *newp = p->left;

p->left = 0;

r->right->left = p; // Set left child of minimum node

r->right = p;       // Point directly to minimum node

return newp;

}

Bnodeb *LinkLeft(Bnodeb *p, Bnodeb *l )

// p->right becomes the new parent of the tree that p

// used to belong to, so we return p->right

{

Bnodeb *newp = p->right;

p->right = 0;

r->left->right = p; // Set right child of maximum node

r->left = p;        // Point directly to maximum node

return newp;

}

#### Figure 12.4 Top-down zigging.

Figure 12.5 illustrates the zig-zig operation, in both the left and right orientations. Again, the splayed node becomes the root of the middle subtree. Recall that a zig-zig corresponds to two single rotations in the same direction. In top-down splaying, the last rotation is accomplished by either LinkRight( ) or LinkLeft( ). The first rotation is handled by one of the following rotation routines: RotateRight( ) or RotateLeft( ).

Bnodeb *RotateRight(Bnodeb *p)

// Rotates right about p. Returns a pointer

// to the node that takes the place of p.

{

Bnodeb *t = p->left;

p->left = t->right;

t->right = p;

return t;

}

Bnodeb *RotateLeft(Bnodeb *p)

// Rotates left about p. Returns a pointer

// to the node that takes the place of p.

{

Bnodeb *t = p->right;

p->right = t->left;

t->left = p;

return t;

}

#### (b) Rotate left, link left

Figure 12.6 illustrates the zig-zag configuration, in which a double rotation is performed. Using LinkRight( ) and LinkLeft( ) in a series has the same effect as doing the two opposite rotations that make up a double rotation. As always, the splayed node becomes the root of the middle subtree.

The operations for zig, zig-zig, and zig-zag are applied repeatedly until the desired node (the one having the matching key) becomes the root of the middle subtree. At this point, the three subtrees are assembled back into a single tree, as illustrated in Figure 12.7. The splayed node becomes the root of the reassembled tree. The following Assemble( ) routine gives the necessary pointer manipulations.

void Assemble(Bnodeb *p, Bnodeb *l, Bnodeb *r)

// Assembles p, l, and r into one tree, with p as the root,

// l & r as the left and right subtrees of p, and the old

// left and right subtrees of p as right and left subtrees

// of l & r, respectively

{

if (1->right) {

1->left->right = p->left;

p->left = l->right;

}

if (r->left) {

r->right->left = p->right;

p->right = r->left;

}

}

#### Figure 12.7 Reassembling a splayed tree.

Figure 12.8 shows a complete example of top-down splaying. First a zig-zig is performed, followed by a zig-zag, and finally a zig. We've used the same tree as the one shown earlier in Figure 12.2 (illustrating bottom-up splaying). Note that the resulting splayed trees are different, although the splayed node c is at the root in both. The difference in the two cases exists because the rotations are performed in different orders.

#### Figure 12.8 Top-down splaying.

We are now in a position to show how a search routine for a splay tree might be coded. But first, we'll define some classes to be used for splay trees.

## SPLAY TREE CLASSES

class SplayTreeb {

protected:

static Bnodeb *LinkRight(Bnodeb *p, Bnodeb *r);

static Bnodeb *LinkLeft(Bnodeb *p, Bnodeb *l);

static void Assemble(Bnodeb *p, Bnodeb *l, Bnodeb *r);

static Bnodeb *SplayMin(Bnodeb *t);

static Bnodeb *SplayMax(Bnodeb *t);

static Bnodeb *DetachMin(Bnodeb *&root);

static Bnodeb *DetachMax(Bnodeb *&root);

};

The following SplayTree class is derived from the SplayTreeb class:

template<class TYPE>

class SplayTree : public SplayTreeb {

protected:

Bnodeb *root;

void SearchAndSplay(const TYPE &x);

Bnode<TYPE> *SearchP(const TYPE &x, Bnode<TYPE> *&p, int &side);

// Allocation functions. . .

public:

// Constructors, destructors, copy functions,

// and other supporting functions. . .

Bnode<TYPE> *Member(const TYPE &x);

int Add(const TYPE &x, int &existed);

Bnode<TYPE> *AddFixed(const TYPE &x, int &existed);

Bnode<TYPE> *Detach(const TYPE &x);

Bnode<TYPE> *DetachMin();

Bnode<TYPE> *DetachMax();

int Delete(const TYPE &x);

void DeleteMin();

void DeleteMax();

Bnode<TYPE> *Min();

Bnode<TYPE> *Max();

int IsEmpty();

Bnode<TYPE> *Root() const;

};

As usual, the SplayTree class is implemented as a concrete data type, with various constructors, destructors, overloaded assignment operators, allocation functions, and so on. These functions are similar to those used in the Bstree and RBtree classes of earlier chapters, and won't be discussed further. Instead, we'll focus on routines for searching, inserting, and deleting nodes.

## Searching in a Splay Tree

template<class TYPE>

void SplayTree<TYPE>::SearchAndSplay(const TYPE &x)

// Search for node containing the key x, moving that

// node to the root using top-down splaying

{

Bnodeb l, r; // Temp subtrees holding no data

if (root == 0) return;

l.left = &l; l.right = 0;

r.left = 0;  r.right = &r;

while (x != Root()->info) { // While root doesn't match

if (x < Root()->info) {   // Search left down the tree

if (root->left) {

if (x == Root()->Left()->info) {

// zig

}

else if (x < Root()->Left ()->info) {

// zig-zig

root = RotateRight(root);

if (root->left) root = LinkRight(root, &r);

}

else if (x > Root()->Left()->info) {

// zig-zag

if (root->right) root = LinkLeft(root, &l);

}

} else break;    // Node isn't in the tree

}

else {               // x > root->info, so search right down the tree

if (root-> right) {

if (x == Root()->Right()->info) {

// zig

}

else if (x > Root()->Right()->info) {

// zig-zig

root = RotateLeft(root);

if (root->right) root = LinkLeft(root, &l);

}

else if (x < Root()->Right()->info) {

// zig-zag

if (root->left) root = LinkRight(root, &r);

}

} else break; // Node isn't in the tree

}

}

Assemble(root, &l, &r);

}

template<class TYPE>

Bnode<TYPE> *SplayTree<TYPE>::Member(const TYPE &x)

{

SearchAndSplay(x);

return (Root() && Root()->info == x) ? Root() : 0;

}

## Inserting into a Splay Tree

template<class TYPE>

int SplayTree<TYPE>::Add(const TYPE &x, int &existed)

// Search for a node containing key x in the tree. If found,

// node to the tree containing x. This node will become

// the new root.

// Returns 1 if successful; returns 0 if allocation failed

{

Bnode<TYPE> *p;

SearchAndSplay(x); // Moves closest match to the root

existed = (Root() && Root()->info == x) ? 1 : 0;

if (!existed) {

p = AllocNode(x);

if (p == 0) return 0;

// p is about to become the new root

if (Root()) {

//  Determine which side of p the old root should go on

if (x < Root()->info) {

p->right = root;

p->left = root->left;

root->left = 0;

}

else { // x > root->info at this point

p->left = root;

p->right = root->right;

root->right = 0;

}

}

root = p;

}

return 1;

}

## Deleting from a Splay Tree

In Chapter 10, we detached a node from a binary search tree by swapping the node's key with that of its successor, and then detaching the successor. We can use a similar process with a splay tree, except that we want to perform splaying at the same time, so that the amortized searching cost will remain at logn.

The deletion can be performed by first calling SearchAndSplay( ) to move the node to delete to the root. Then, we splay the successor node to the top of the right subtree by calling a special SplayMin( ) function. (The successor of the root is always the minimum node of the right subtree.) We'll describe the SplayMin( ) function in the next section. Note that the successor node is guaranteed to have a null left child (Can you figure out why?). Thus, we can easily make the successor the new root and make, as its left child, the left child of the old root. Figure 12.10 illustrates this process. If the root doesn't have a successor, the left child of the root can take its place. If there is no left child, the tree is now empty.

We could also use an alternate, symmetrical operation for the detachment: The predecessor node could be used as the replacement by splaying the maximum node of the left subtree to the top, making it the new root, and using the right child of the old root as the right child of the new root.

#### (d) Make c the new root

template<class TYPE>

Bnode<TYPE> *SplayTree<TYPE>::Detach(const TYPE &x)

// Searches for a node matching x and detaches it from

// the tree. Returns a pointer to the node detached;

{

if (root == 0) return 0;

SearchAndSplay(x);

if (Root()->info == x) { // Matching node found

Bnode<TYPE> *oldroot = Root();

if (root->right) {

root = SplayMin(root->right);

root->left = oldroot->left;

}

else root = root->left;

return oldroot;

}

return 0;

}

## SPLAY TREES AS PRIORITY QUEUES

In Chapter 9, we briefly mentioned priority queues, in which items are inserted in any order, but extracted in sorted order, based on a priority determined by a key within each item. Because splay trees are highly adaptable, they can be used quite effectively as priority queues. The technique involves inserting items into the splay tree in binary search tree order, and then extracting either the minimum (or maximum) node. The following discussion assumes that we wish to extract the minimum node, but the techniques described can easily be modified to extract the maximum node.

A regular binary search tree can be used as a priority queue, but a splay tree is more effective. Recall that the minimum node of a tree can be found by continuously walking left until a null left child is found. The minimum node may be near the bottom of the tree, so the first extraction may not be very efficient. However, in a splay tree, extracting the minimum node tends to cause nodes close the minimum to migrate to the top. Thus, subsequent extractions can be quite efficient.

However, if intervening insertions take place, the minimum node may fall toward the bottom again. This can be circumvented by modifying the behavior for insertions: Don't do splaying when a node is inserted. Instead, use an ordinary binary search tree insertion. Recall that such insertions don't restructure the tree. Instead, the new node is added somewhere close to the bottom. The minimum node will thus remain close to the top for a subsequent extraction. If the new node is the minimum, it will be added below the old minimum (in fact, on the left), and thus will be quite close to the top.

Note The technique just described is believed to have been invented by the author.

Figure 12.11 illustrates a splay tree used as a priority queue. Note that, once the splaying begins, the minimum node stays close to the top. If the extraction process begins on a degenerate tree with n nodes, with the minimum node at the bottom, the worst-case cost is n steps. However, the amortized cost will probably be closer to logn steps, and may be much better than this. Because the insertions don't do splaying, it helps if the insertions are intermixed with extractions (which is likely to be the case). If there is a long series of insertions without extractions, an expensive extraction might be forthcoming, but subsequent extractions are likely to be cheap due to the splaying that finally takes place. It is difficult to precisely analyze the costs of the insertions and extractions for the strategy given here. The costs when using normal splaying operations for priority queue insertion have been empirically analyzed [Jones 86].

#### (g) Extract d

Bnodeb *SplayTreeb::SplayMin(Bnodeb *t)

// Move the minimum of t up the tree, replacing t

// as the root. The new root is returned.

{

Bnodeb l, r;

if (t == 0) return 0;

l.left = &l; l.right = 0;

r.left = 0;  r.right = &r;

while(t->left) {

// Go left as far as possible, splaying along the way

// We have either a zig-zig, or a zig orientation

if (t->left->left) t = RotateRight(t);

t = LinkRight(t, &r); // t->left guaranteed not null

}

Assemble(t, &l, &r);

return t;

}

Bnodeb *SplayTreeb::DetachMin(Bnodeb *&root)

// Detach the minimum node of the tree, returning

// a pointer to it, or 0 if tree is empty

{

if (root == 0) return 0;

root = SplayMin(root);

// Replace the minimum node, now at the root,

// with its successor, found by splaying the

// minimum node of the right subtree to the top.

// If there is no right subtree, then we know the

// tree is empty, since the left child is null.

Bnodeb *oldroot = root;

if (root->right) {

root = SplayMin(root->right);

root->left = oldroot->left;

}

else root = 0;

return oldroot;

}

To insert a node into a splay tree-based priority queue without splaying, we can use functions identical to the SearchP( ) and Add( ) functions of the Bstree class described in Chapter 10. (We won't repeat those functions here.) For the code given on disk, we've renamed Add( ) to AddFixed( ) to differentiate it from the Add( ) function that uses splaying.

## SUMMARY

Splay trees are intriguing structures because they are so adaptable. For example, we can use a splay tree for normal binary searching operations, and then decide to switch gears and use it like a priority queue. In fact, we can switch between extracting the minimum nodes and extracting the maximum nodes, and the splay tree will automatically adjust itself. (However, alternating between minimum and maximum extractions will lead to bad performance. There are better structures for this type of activity, called min-max priority queues. See [Atk 86].)

Unfortunately, splay trees do not necessarily make good general-purpose search trees. There are two fundamental problems:

1. Splay trees have the same worst-case searching performance as linked list. For a large number of nodes, this may be unacceptable. If you want to guarantee logn performance for any single operation, a balanced binary search tree is better.

2. For the most efficient operation, a splay tree must always restructure the tree, even during what would otherwise be read-only searching, and even when the searching is unsuccessful. Thus, you couldn't use a splay tree to search a database on CD-ROM, for instance. You could implement the searching to forego the splaying, but then the amortized efficiency would suffer. Alternatively, you could "train" the splay tree by using a long series of typical accesses, using splaying, and then "freeze" the structure. From then on, you could search without the splaying. However, this would only be effective if no new nodes were added, and if the access patterns didn't change.

Splay trees are advantageous when the access patterns favor a few nodes over the rest. A priority queue provides a good example because the nodes being favored are the ones with the smallest keys. These nodes tend to percolate to the top during the minimum node extraction process.