A splay tree is an example of a *self-organizing structure* that adapts itself to changing conditions. The principle behind self organization is simple: When a node is accessed, it is moved to the top of the tree. Then, if the node is accessed again, it is available with only minimal searching. As the tree is used, the most frequently accessed nodes tend to float to the top. When the access patterns change, other keys float to the top.

The splaying algorithm is similar to the previous strategy given in that it moves the desired node all the way to the root, but the movement is performed in a rigorously defined way. Assume that you have a pointer to the node you would like to move to the top. Three rules are involved, which are applied repeatedly from the bottom up until the node is at the root. (These rules assume you have some way to find the parent of a node.)

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).

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 log*n*, the same as for balanced trees. Unfortunately, splay trees have the same worst case that linked lists have.

So far, we've described splaying in terms of bottom-up operations. If splaying is used in conjunction with searching, this implies two passes: a top-down pass to find the node, and then the bottom-up splaying pass. The bottom-up pass requires that you either have saved the parent pointers on a stack on the way down or that each node stores a parent pointer.

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.

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

// 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.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;

}

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.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.

We'll now implement splay trees using a simple two-class hierarchy. The following *SplayTreeb *class defines a data-independent base class. This class is unusual in that it has all static member functions, which are declared protected. This is done to hide the names of these otherwise ordinary functions, and to make them accessible* *only to the *SplayTree* class that you are about to see. The functions included in *SplayTreeb* are the *LinkRight( ), LinkLeft( ), RotateRight( )*, and *RotateLeft( )* functions shown earlier. Also included are some functions for manipulating the minimum and maximum nodes in the tree, which we'll discuss later.

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;

};

Complete code for splay trees is given on disk in the files *splay.h, splay.cpp, *and *splay.mth.* A test program is given in *tstsplay.cpp.* In addition, many supporting files from Chapter 10 are used.

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.

The following *SearchAndSplay( )* routine shows how to search for a node in a splay tree. The basic idea is to do a standard binary search and perform top-down splaying at the same time. The appropriate splaying operations to perform are determined by comparing the current node *t* with the desired key, as well as testing the children of *t*.

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

root = LinkRight(root, &r);

}

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

root = LinkRight(root, &r);

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

root = LinkLeft(root, &l);

}

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

root = LinkLeft(root, &l);

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

}

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

}

}

Assemble(root, &l, &r);

}

If the matching node is in the tree, it will become the root of the tree after the search. However, if the node isn't in the tree, either the predecessor or successor of the node will become the root. Thus, the root must be tested to see if it is indeed the matching node, as the following *Member( )* function illustrates:

template<class TYPE>

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

{

SearchAndSplay(x);

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

}

Unlike a normal binary search tree, nodes are added to a splay tree at the root. To make this work, the *SplayAndSearch( )* routine is first called. If the node already exists, the insertion is skipped. If the node doesn't exist, a new node is allocated to become the new root. The splaying that takes place during the unsuccessful search restructures the tree so that splicing in the new root is easy. The old root will be the predecessor or successor of the new root. We make the old root the left or right child of the new root. In turn, one of the children of the old root will become the other child of the new root. Figure 12.9 shows an example. The following *Add( )* function gives the details.

template<class TYPE>

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

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

// set existed to 1 and return. If not found, add a new

// 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;

}

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 log*n*.

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.

At this point, the node targeted for deletion is detached from the tree. The following *Detach( )* function gives the details. The node can then be de-allocated if desired. A *Delete( )* routine (not shown) handles this chore. Note that, if the node to be detached isn't found in the tree, the tree may be restructured anyway by *SearchAndSplay( )*--in anticipation of the possible detachment.

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;

// returns 0 if not found.

{

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;

}

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 log*n* 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].

The following *SplayMin( )* function shows how the minimum node can be splayed to the top. This function is an adaptation of the *SearchAndSplay( )* function. But here, we don't need to do any searching, since the minimum node is always to our left. Note that the splaying will be in the form of zig-zagging operations, except for perhaps the final operation, which may be a single zig. A *SplayMax( )* function can be symmetrically defined. Here, the maximum is always on the right.

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;

}

After the minimum is splayed to the top, the node can be detached in exactly the same way we detached nodes with the *Detach( )* function. The only difference is that the left child of the splayed node is always null. So, if the right subtree is empty, we know the tree is empty. Here is the corresponding *DetachMin( )* function. A *DetachMax( )* function could be symmetrically defined:

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.

While splay trees make good non-contiguous priority queues, other data structures, called *heaps* (not to be confused with the heaps used for dynamic memory allocation), work well for contiguous priority queues. Heaps are advantageous because they can be implemented without storing left and right pointers in the nodes. Only the data needs to be stored. For details on heaps, see the companion volume [Flamig 93].

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 log*n *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.