Next Chapter Return to Table of Contents Previous Chapter

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

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.

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

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.1 The three splaying cases.

(a) Zig (single rotation)

(b) Zig-zig (two single rotations)

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

Figure 12.2 Bottom-up splaying.

(a) Zig-zag

(b) Zig-zag

(c) Zig

Figure 12.3 Degenerate splaying.

Top-Down Splaying

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.

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.

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.4 Top-down zigging.

(a) Link right

(b) Link left

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.5 Top-down zig-zigging.

(a) Rotate right, link right

(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.6. Top-down zig-zagging.

(a) Link right, link left

(b) Link left, link right

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

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.

Searching in a Splay Tree

Inserting into a Splay Tree

Deleting from a Splay Tree

Searching in a Splay Tree

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;

}

Inserting into a Splay Tree

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;

}

Figure 12.9 Insertion into a splay tree.

(a) Original tree

(b) Unsuccessful search for g

(c) Adding g as the root

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.

Figure 12.10. Detaching a node from a splay tree.

(a) Original tree

(b) Splay b to top

(c) Splay c to top of subtree

(d) Make c 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;

}

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

Figure 12.11 Priority queue splaying.

(a) Original tree

(b) Extract a

(c) Add h without splaying

(d) Extract b

(e) Add e without splaying

(f) Extract c

(g) Extract d

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

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.

Go to Chapter 13 Return to Table of Contents