Andrew received his master's degree in computer science from RPI in Troy, New York. He can be reached through his Bitnet address, which is aliao%eagle @wesleyan.bitnet. You can also reach him through the DDJ office.
Application programs are often developed using standard data structure techniques such as stacks, queues, and balanced trees with the goal of limiting worst case performance. Such programs, however, normally carry out many operations on a given data structure. This means that you may be able to trade off the individual worst case cost of each operation for that of the worst case cost over a sequence of operations. In other words, any one particular operation may be slow, but the average time over a sufficiently large number of operations is fast. This is an intuitive definition of amortized time, a way of measuring the complexity of an algorithm. In this case, the algorithms to be concerned with are those that carry out operations on data structures.
The heuristic I'll discuss in this article is called the "structural self-adjusting heuristic." To illustrate what I mean by self-adjusting, consider the following example: Suppose you're running an information warehouse and your task is to distribute information to people who request it. The information in this warehouse could be stored in a fixed order, such as the order of information in a library. You quickly notice, however, that certain pieces of information are requested more often than others. You could make the job easier by moving the most often requested information close to the service counter. This means that instead of having to search through the depths of the warehouse at any given time, you have a good portion of the most requested information nearby.
As this example suggests, self-adjusting heuristic algorithms are ideally suited to lists, binary search trees, and priority queues (heaps). In lists, the heuristic attempts to keep the most frequently accessed items as close to the front as possible. In binary search trees, the heuristic attempts to keep the most frequently accessed items as close to the root as possible, while preserving the symmetric ordering. Finally, in heaps, the heuristic attempts to minimize the cost of modifying the structure, and partially orders the heap in a simple, uniform way. To illustrate how these algorithms can be implemented, I've provided sample Pascal source code.
A singly linked list is a group of records where each record contains one field that holds an individual piece of user data, and another field that holds a pointer to the next record in the list. An initial pointer that indicates which record starts the list is (or should be) kept. This pointer enables you to search, insert, and delete operations.
To understand how the move-to-front (MTF) approach works, consider a situation in which a particular application uses an open hash table with a linked list that is associated with each array location. Suppose that the hashing routine for this application is as good as it can possibly be. If you wish to improve the search performance without unduly complicating the supporting code, however, you might examine the performance of the search performed on the lists. Chances are that certain elements are accessed more often than others. The use of either a transpose or a frequency count heuristic (two other common access approaches) does not appear to be a good idea because of the search overhead involved with each approach. Both methods require either a local exchange operation or extra searching in order to reinsert an accessed item into the correct part of the list. Also, the count method requires a change in the list: The addition of an integer field that maintains the access count. All three heuristics are effective in that they search less than half the list.
One reason why the MTF heuristic performs better than the transpose method is that the transpose heuristic causes the list to converge more slowly to its optimal ordering. In the case of MTF, an element is brought to the front of the list. Furthermore, such an element quickly "sinks" to the end of the list over the course of a sequence of accesses if that element is not a sufficiently wanted item. Essentially, MTF may be viewed as an optimistic method in the sense that the method "believes" that an accessed item will be accessed again. Analogously, the transpose heuristic may be viewed as pessimistic in that it "doubts" that an accessed item will be accessed again. The count method is a compromise between the two.
As Figure 1 and Listing One (page 105) illustrate, searching is the key operation for the MTF heuristic. This search operation is very much like a normal search on a singly linked list, except that an extra pointer is kept to the current predecessor of the list node that is currently being examined. Once a given item is found, the pointer to its predecessor node is used to alter the predecessor node's link field so that the link field points to the successor node of the accessed item. The link field in the desired node is then altered to point to the first element in the list, and the head-of-list pointer is set to point to the new front-of-the-list item. For all intents and purposes, the insert operation is a push operation -- the new item is immediately put at the front of the list. Finally, an MTF search is used to perform a delete. If the item to be deleted is located at the front of the list, that item is removed from the front of the list.
A "heap" is a tree-based data structure in which each record node keeps a key, along with pointers to the record node's successors. The heap maintains an ordering of items such that every node has a key less than, or equal to, the keys of the node's successors. This last description is the concept of "heap-ordering."
There are a number of classical priority queue structures (such as 2 - 3 trees, leftist heaps, and binomial heaps) that are amenable to fast merging operations. Of These, the simplest scheme for maintaining a heap with fast merge operations is the "leftist heap," which was developed to maintain partially ordered lists with a logarithmic time-merge operation. A leftist heap is based upon a binary tree node that contains rank, weight, and two pointer fields (to indicate left and right children). The rank field is defined to be 0 if a node is a leaf. Otherwise, the rank field is defined as one more than the minimum value of both the rank of the leftchild and the rank of the rightchild.
A binary tree is a leftist heap if it is heap-ordered and if the rank of a given leftchild is greater than, or equal to, the rank of its rightchild sibling. The problem with maintaining leftist heaps is that the configuration of the data structure is based upon the rank definition. All operations are heavily dependent upon the value kept in the rank field of a given node. To illustrate the point, I'll describe the leftist heap merge operation.
The leftist heap merge operation is made possible by a modified version of an "enqueue" process (which takes a heap and a queue pointer's record as parameters). This particular enqueue operation saves the root of the heap and moves the front queue pointer down to the rightchild of the root just saved. You then break the link between the saved root and its rightchild. If the queue pointers are both empty, point the front and rear pointers to the root node that was just saved, and set the rightchild pointer field of the root to empty. Otherwise, point the rightchild pointer to the node currently pointed to by the rear queue pointer, and point the rear queue pointer to this newly obtained node.
Implement the merge with the following steps: While neither of the two heaps being merged is empty, call enqueue with the currently minimum key and with the queue pointer's record. Next, while the "first" heap is not empty, call enqueue with that heap and with the queue pointer's record. Perform the same steps for the other heap. These three processes merge the right path. Complete the process with a bottom-up traversal of the right path in order to fix up the rank fields and to perform any necessary swaps to maintain the structural invariant.
Now point to the current two bottommost nodes on the merge path. If there is no left sibling of the bottommost node, make the rightchild a leftchild and set its parent's rank field to 0. Next, set the rightchild's rightchild pointer field to empty. If the bottommost node has a left sibling, compare the two children and swap them when the rank of the left sibling is less than that of the right sibling. In any event (given this case), set the parent's rank field to 1+ rank of the rightchild. Also note which nodes are the next two bottommost nodes on the merge path at this point, and make sure that the parent node before this step points to the rightchild. This process continues until the root is reached when the root of the new heap is returned. Once the merge operation for leftist heaps has been described, the other heap operations are easy to implement.
This description of the merge operation suggests that two passes are required over the merge path. The question remains: How do you improve performance without unduly complicating the algorithms that maintain the heap? This can be done with a restructuring method that essentially exchanges every node on the result heap's right path with the node's left sibling. The version of the technique presented here also has a feature in which one top-down pass completes the merge. The resulting structure, called a "top-down-skew heap," is a self-adjusting analog of the leftist heap.
A skew heap is based upon a simple binary tree node that contains a weight plus pointer fields to left and right children. The process of merging is made possible by another modified version of the enqueue algorithm. In this case it's not necessary to maintain the rank/balance field in order to obtain logarithmic, amortized performance.
This particular enqueue operation saves the root of the heap and moves the front queue pointer down to the rightchild of the root just saved. You then break the link between the saved root and its rightchild by changing the current leftchild into a rightchild. If the queue pointers are both empty, point the front and rear pointers to the root node just saved, and set the root's leftchild pointer to empty. Otherwise, the newly obtained node becomes the leftchild of the node that is currently indicated by the rear queue pointer, after which the rear queue pointer is changed to indicate the newly obtained node. (See Figure 2.)
The following steps implement the merge: While neither of the two heaps being merged is empty, call enqueue with the heap that contains the current minimum key and the queue pointer's record. Next, while the "first" heap is not empty, call enqueue with that heap and with the queue pointer's record. Follow the same process for the other heap. (This approach is analogous to Tarjan and Sleator's conceptual noting that the left and right children of every node on the merge path are swapped. The implementation used here, however, is a variation.) Once either of the two heaps being merged becomes empty, merely attach the remaining heap to the bottom of the result heap's left path. Again, the rest of the heap operations are easy to define.
Much like the leftist heap, the binomial heap has an analogous self-adjusting counterpart. This new structure, called the "pairing heap," is a recent development in heaps that supports the decreaseKey operation. The essential definition of the pairing heap, like that of the skew heap, is based upon a simple binary tree record node that contains at least weight plus three pointer fields (to indicate the parent and the left and right siblings). Like most heaps, the pairing heap depends upon a merge operation, but has a less complicated scheme than its classical counterpart.
In the case of the binomial heap, you need to maintain a forest of trees where each tree contains a number of nodes equal to a non-negative integer power of two. Thus, a binomial heap of n items can be represented by a forest in which each tree corresponds one-to-one with the one bit that represents the value of n in binary. (This eventually leads to the fact that all of the binomial heap operations are, in the worst case, logarithmic time.) Needless to say, the code needed to implement a binomial heap merge operation is complicated and difficult to maintain.
The merge operation for pairing heaps begins by determining which of the two heaps has the minimal weight at the root. The heap with the non-minimum key at the root then becomes the child at the root of the other heap. The heap that is being made into a subtree points its root node right sibling pointer to the child of the root of the other heap. Furthermore, the first heap's parent pointer is set to the new heap root, and the new heap root points its leftchild pointer to the root of the heap that is being made into a subtree. The merge operation returns the root of the new heap. (See Figure 3.)
Given the above definition of the merge operation, the DeleteMin operation (see Figure 4 and Listing Three, page 106) is easy to describe. I will describe the front-back one-pass variation here. To begin, save the root node and keep a pointer to the leftchild. Next, empty the pointer to the root. While subtrees are linked to the leftchild of the root, remove trees in pairs (beginning with the leftchild) and merge the trees, then merge the result to the heap pointed to by the root pointer. Repeat this step until there are no more trees. (The pairing heap derives its name from the restructuring operation that takes place during a DeleteMin.)
Describing the DecreaseKey operation for pairing heaps (see Figure 5) is just as easy. This operation assumes that you have direct access to the node whose weight field is being decreased, to a root to the heap that contains the node, and to the value by which you wish to decrease the weight. Go to the parent of the node that is being operated on, and then go to the leftchild of that parent. Scan along the right sibling list to find the predecessor of the node that will be operated upon. When the predecessor is located, clip out the tree rooted at the node upon which you wish to carry out the actual Decrease-Key operation. To clip out the tree, link around the node in question. If the node is a leftchild, make its right sibling the new leftchild. Now decrease the weight and merge the tree that is rooted at the node with the root of the pairing heap.
The simple local restructuring heuristics presented here provide an elegant approach to the development of heap structures. In fact, these heaps are simpler to understand and to implement than either the leftist or binomial heaps. Furthermore, indications are that self-adjusting heaps are just as competitive in practice as their classical counterparts. In any event, I've presented two very different (though effective) local restructuring heuristics. The first heuristic reorganizes lists in order to make frequently requested list items more accessible. The second heuristic applies a simple local restructuring method (in place of maintaining balance/accounting data and resolving special structural cases) in order to quickly maintain both the structure and the partial ordering of a heap.
Now let's consider an efficient self-adjusting heuristic for binary search trees. This algorithm makes frequently requested items in the tree more easily accessible, and quickly maintains both the structure and the sorted ordering of the tree.
In a "binary search tree," each node keeps a key along with two pointers to the node's successors. The ordering is such that if a node has key K, every node in that node's left subtree must have keys less than K, and every node in its right subtree must have keys greater than K. This is known as "symmetric ordering." The performance costs of generic binary search tree operations are, in the worst case, logarithmic time (if the input data is sufficiently random). Such a tree may also degenerate as a result of insertions and deletions, and yield steadily poorer performance.
The process of tree degeneration has led to the development of various height/weight balanced trees and B-tree schemes. Although these various schemes guarantee logarithmic worst case times per operation, some of the schemes are not as efficient as possible under nonuniform access patterns. Furthermore, many of these schemes require extra space for balance/accounting information, and the need to keep this information current tends to complicate maintenance of the data structure. Certain cases must be checked on each update, thus incurring a large overhead.
Rotation is the key technique that makes some of the balanced and previous self-adjusting tree schemes possible. In fact, rotation plays a part in the implementation of the splay tree. Before this discussion continues, it is necessary to understand how a right rotation and a left rotation at any node of a binary tree are performed.
As Listing Two (page 105) shows, you implement a right rotation with the following steps: If the pointer to a starting root of some tree is not empty and that node has a left subtree, save pointer to the root and then save pointer to the right subtree of the initial left subtree. Then make the pointer to the initial left subtree the new starting root pointer, and let the original root be the rightchild of the new root. Finally, designate the pointer to the saved rightchild of the original leftchild as a leftchild of the new root's rightchild (which is the original root).
Implement a left rotation in a similar manner. If the pointer to a starting root of some tree isn't empty, and that no has a right subtree, save the pointer the root and then save the pointer the left subtree of the initial right subtree. Then, designate the pointer to the initial right subtree as the new starting root pointer, and let the original root be the leftchild of the new root. Finally designate the pointer to the save leftchild of the original rightchild as rightchild of the new root's leftchild (which is the original root).
The drawbacks of many of the efficient search tree techniques motivate the development of the splay tree. Because binary search trees maintain sorted sets, the question arose as to whether the speed of the search process could be improved if certain item had a higher request frequency than others. In an attempt to improve performance, Allen, Munro, and Bitner proposed two self-adjusting techniques on search trees during the late 1970s. The gist of the first scheme is a single rotation of the item accessed towards the root. The second scheme involves multiple rotations of the accessed item all the way to the root. The techniques are analogous to the variations of the transpose methods for singly linked lists. Neither heuristic is efficient in the amortized sense, since long access sequences exist where the time per access is linear. It is thus clear that the search paths to frequently accessed items need to be as short as possible. Tarjan and Sleator's proposed self-adjusting heuristic halves the depth of each node on the path to an accessed item when the item is finally moved to the root. A splay tree is a binary search tree that employs this heuristic.
The proposed self-adjusting heuristic has two versions. The "bottom-up splay" is appropriate if you already have direct access to the node that is to be moved to the root. Heuristic restructuring occurs during the second pass back up the search path (assuming that the first pass down the tree is performed in order to find the item). The second version of the proposed self-adjusting heuristic, called a "top-down splay," is an efficient variation of the process used to carry out Tarjan and Sleator's self-adjusting heuristic. This variant requires a pointer to the tree (call it T), that points to the current node to be examined during the search. This heuristic also requires two double pointer records, called L and R (for left and right subtrees), that point to all items less than or greater than the node at T. Figure 6 describes this step.
Case 1 (Top-Down Zig):
If x is the root of T and y is the
accessed item (with x=parent(y)
then if y is a leftchild, then break
the link from x to y and add x
to the bottom left of R (else if y
is a rightchild, add x to the
bottom right of L) and now T points
to y, the new root.
Case 2 (Top-Down Zig-Zig):
If x is the root of T and y
(child(x)=y=parent(z))and z are
both leftchildren (or both
right-children) then do a rotation to
the right (or symmetrically, a
rotation to the left), break the
link from y to z and attach y to
the bottom left of R (else
bottom right of R) and now T points
to z, the new root.
Case 3 (Top-Down Zig-Zag):
If x is the root of T and y is a
leftchild of x and z s a rightchild
of y (or y is a rightchild of x and
z s a leftchild of y), break the
link from x to y and attach x to
the bottom left of R (else the
bottom right of L), break the
link from y to z and attach y to
the bottom right of L (else the
bottom left of R) and now T
points to z, the new root.
As illustrated in Figure 7, the splaying process repeatedly applies one of the appropriate cases until there are no more cases to apply. At this point, the leftchild of the remaining root is attached to the bottom right of L, and the rightchild is attached to the bottom left of R. The final step points the leftchild of the final remaining root to the subtrees kept by L, and points the rightchild to the subtrees kept by R. (Unlike the bottom-up variation, the top-down heuristic includes the splay step.) When the search/access for a requested node fails, change the last node on the search path into the root of the tree. This step makes the definition of all of the other operations very easy.
To search for a node, simply apply the searching process as described earlier. The process of insertion involves searching for the key V to be inserted. If V is less than the key at the root, make the node that contains V point its leftchild pointer to the leftchild of the root (which breaks the link from the root to that leftchild), and point the rightchild pointer to the root. Otherwise, the leftchild pointer of the node that contains V points to the root, and the rightchild pointer points to the rightchild of the root (and the link from the root to the rightchild is broken). The insertion step is completed by designating the node that contains V as the root.
The split operation is essentially the process of breaking the tree at the root in the manner described in the description of the insertion process. The process of deletion is just as easy. Perform the splay search from the key to be deleted. If the root does not contain the node with the key to be deleted, nothing happens. If the root does contain the node with the key to be deleted, keep pointers to the two subtrees at the root, perform a splay search for the maximum key in the left subtree (and designate the root of the left subtree as the new root), and point the rightchild pointer of the root to the right subtree. The join operation of two binary search trees (assuming that all items in Tree 1 are less than those in Tree 2) is simply the non-no operation of the delete algorithm just described.
The self-adjusting heuristic provides an alternative to the standard balancing/accounting worst-case asymptotic solutions used to develop efficient programs -- and may, in fact, be the method of choice. Furthermore, the algorithms to maintain these self-adjusting data structures are both conceptually easy to understand and simple to implement in practice.
In which applications could these data structures be used to improve performance? Some possibilities are symbol table management applications (MTF lists, splay trees, and possibly in conjunction with hashing schemes), graph algorithms (skew and pairing heaps, particularly with respect to finding minimum spanning trees and the shortest paths in graphs), and other network optimization algorithms (such as splay trees, particularly in maximum/minimum network flow algorithms). Recent work by Jones, Bern, and de Carvalho, as well as my own work, indicates that some of the self-adjusting data structures do seem to perform better in practice than do conventional data structures.
Aho, A.; Hopcroft, J.; and Ullman, J. The Design and Analysis of Computer Algorithms. Reading, Mass.: Addison-Wesley, 1974.
Allen, B. and Munro, I. "Self-Organizing Search Trees." Journal of the ACM 25 (1978).
Bentley, J.L. and McGeoch, C.C. "Amortized Analyses of Self-Organizing Sequential Search Heuristics." Communications of the ACM 28 (1985).
Bern, M. and de Carvalho, M. "A Greedy Heuristic for the Rectilinear Steiner Tree Problem." Report No. UCB/CSD 87/306, Computer Science Division. Berkeley: UC Berkeley (1987).
Bitner, J.R. "Heuristics That Dynamically Organize Data Structures." SIAM Journal of Computing 8 (1979).
Brown, M.R. "Implementation And Analysis Of Binomial Queue Algorithms." SIAM Journal of Computing 7 (1978).
Dietz, P. and Sleator, D. "Two Algorithms for Maintaining Order in a List." Proceedings of the 19th ACM Symposium on Theory of Computing (1987).
Fredman, M.L. and Tarjan, R.E. "Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms." Proceedings of the 25th Annual IEEE Foundation of Computer Science (1984).
Fredman, M.L. et al. "The Pairing Heap: A New Form of Self-Adjusting Heap." Algorithmica 1 (1986).
Jones, D.W. "An Empirical Comparison of Priority Queue and Event Set Implementations." Communications of the ACM 29 (1986).
Knuth, D.E. The Art Of Computer Programming, Vol. 3: Searching And Sorting, 2nd ed. Reading, Mass.: Addison-Wesley, 1973.
Liao, A.M. "Three Priority Queue Applications Revisited." Submitted to Algorithmica (1988).
Sedgewick, R. Algorithms. Reading, Mass.: Addison-Wesley, 1983.
Sleator, D.D. and Tarjan, R.E. "Self-Adjusting Binary Trees." Proceedings of the 15th ACM Symposium on Theory of Computing (1983).
Sleator, D.D. and Tarjan, R.E. "Self-Adjusting Binary Search Trees." Journal of the ACM 32 (1985).
Sleator, D.D., and Tarjan, R.E. "Self-Adjusting Heaps." SIAM Journal of Computing 15 (1986).
Tarjan, R.E. "Data Structures And Network Algorithms." CBMS Regional Conference Series In Applied Mathematics 44. Philadelphia: SIAM (1983).
Tarjan, R.E. "Amortized Computational Complexity." SIAM Journal of Algebraic Discreet Methods 6 (1985).
Vuillemin, J. "A Data Structure For Manipulating Priority Queues." Communications of the ACM 21 (1978).
Wirth, N. Algorithms + Data Structures = Programs. Englewood Cliffs, New Jersey: Prentice Hall, 1976.
_SELF-ADJUSTING DATA STRUCTURES_
by Andrew M. Liao
[LISTING ONE]
{*** Singly linked move-to-the front list ***}
{*** Contents: "LInsert", "Mtffind" ***}
{ Data Structure:
ptr=^node;
node=RECORD rec:item; next:ptr; END; }
PROCEDURE LInsert(arg:item; VAR root:ptr);
VAR p:ptr; { To generate storage }
BEGIN
NEW(p); { Allocate }
p^.rec:=arg; { Add data }
p^.next:=root; { Place at front of list }
root:=p; { Point to new front of list }
END;
FUNCTION Mtffind(arg:item; VAR root:ptr;):boolean;
VAR temp1,temp2:ptr; { Search pointers }
found:boolean; { TRUE iff found }
BEGIN
temp1:=root; { Get a copy of starting location }
temp2:=root; { Secondary copy }
found:=false; { Nothing found yet }
WHILE (temp1<>NIL) AND (NOT found) DO
BEGIN
IF temp1^.rec<>arg THEN { Found it? }
BEGIN { Nope... }
temp2:=temp1; { Move trailing pointer }
temp1:=temp1^.next; { Move search pointer }
END
ELSE found:=true; { Yup... }
END;
IF found THEN { Move item to front of list }
BEGIN
temp2^.next:=temp1^.next;
IF temp1<>root THEN temp1^.next:=root;
root:=temp1;
END;
Mtffind:=found;
END;
[LISTING TWO]
{*** Move To The Front Splay Tree ***}
{*** Contents: SplaySearch, BSInsert, BSDelete ***}
{ Data Structure:
ptr=^node;
node=RECORD data:key; left,right:ptr; END; }
FUNCTION SplaySearch(x:key; VAR p:ptr):boolean;
TYPE noderec=RECORD { Temporary Tree Pointer Def. }
left,right:ptr;
END;
VAR l,r:noderec; { Temporary Trees }
done:boolean; { TRUE if NIL encountered in search }
PROCEDURE RRot(VAR p:ptr);
VAR temp,temp1:ptr; { Temporary pointers }
BEGIN
IF p<>NIL THEN { Don't rotate if nothing's there }
IF p^.left<>NIL THEN { No left edge - don't rotate }
BEGIN
temp:=p; temp1:=p^.left^.right; { Copy root & 2ndary child }
p:=temp^.left; p^.right:=temp; { Rotate root }
temp^.left:=temp1; { Reattach 2ndary child }
END;
END;
PROCEDURE LRot(VAR p:ptr);
VAR temp,temp1:ptr; { Temporary pointers }
BEGIN
IF p<>NIL THEN { Don't rotate if nothing's there }
IF p^.right<>NIL THEN { No right edge - don't rotate }
BEGIN
temp:=p; temp1:=p^.right^.left; { Copy root & 2ndary child }
p:=temp^.right; p^.left:=temp; { Rotate root }
temp^.right:=temp1; { Reattach 2ndary child }
END;
END;
PROCEDURE LnkRight(VAR p:ptr; VAR r:noderec);
VAR temp:ptr; { Temporary pointer }
BEGIN
IF p^.left<>NIL THEN { No left child - don't cut & link }
BEGIN
temp:=p^.left; p^.left:=NIL; { Remember left child & break link }
IF r.left=NIL THEN { Attach to temporary tree }
BEGIN r.left:=p; r.right:=p;END { Empty tree? }
ELSE { Just add to bottom leftmost }
BEGIN r.right^.left:=p; r.right:=r.right^.left; END;
p:=temp; { New root is left child }
END;
END;
PROCEDURE LnkLeft(VAR p:ptr; VAR l:noderec);
VAR temp:ptr; { Temporary pointer }
BEGIN
IF p^.right<>NIL THEN { No right child - don't cut & link }
BEGIN
temp:=p^.right; p^.right:=NIL;{ Remember right child & break link }
IF l.left=NIL THEN { Attach to temporary tree }
BEGIN l.left:=p; l.right:=p;END { Empty tree? }
ELSE { Just add to bottom rightmost }
BEGIN l.right^.right:=p; l.right:=l.right^.right; END;
p:=temp; { New root is right child }
END;
END;
PROCEDURE Assemble(VAR p:ptr; VAR l,r:noderec);
VAR temp,temp1:ptr;
BEGIN
temp:=p^.left; temp1:=p^.right; { Hold onto subtrees }
IF l.left<>NIL THEN
BEGIN
p^.left:=l.left; { Attach temporary left subtree }
l.right^.right:=temp; { Reattach orginal left subtree }
END;
IF r.left<>NIL THEN
BEGIN
p^.right:=r.left; { Attach temporary right subtree }
r.right^.left:=temp1; { Reattach original right subtree }
END;
END;
BEGIN
l.left:=NIL; l.right:=NIL; { Initialize temp trees }
r.left:=NIL; r.right:=NIL;
done:=false; { Init to "item maybe there" }
IF p<>NIL THEN { No search if tree's empty }
BEGIN
REPEAT
IF (x<p^.data) THEN { Item on left subtree? }
IF (p^.left<>NIL) THEN
BEGIN
IF x=p^.left^.data THEN LNKRIGHT(p,r)
ELSE
IF x<p^.left^.data THEN BEGIN RRot(p); LNKRIGHT(p,r); END
ELSE
IF x>p^.left^.data THEN BEGIN LNKRIGHT(p,r);LNKLEFT(p,l);END;
END ELSE done:=TRUE
ELSE
IF (x>p^.data) THEN { Item on right subtree? }
IF (p^.right<>NIL) THEN
BEGIN
IF x=p^.right^.data THEN LNKLEFT(p,l)
ELSE
IF x>p^.right^.data THEN BEGIN LRot(p); LNKLEFT(p,l); END
ELSE
IF x<p^.right^.data THEN BEGIN LNKLEFT(p,l);LNKRIGHT(p,r);END;
END ELSE done:=TRUE;
UNTIL (x=p^.data) OR DONE;
ASSEMBLE(p,l,r); SplaySearch:=(x=p^.data);
END ELSE SplaySearch:=FALSE;
END;
PROCEDURE BSInsert(x:key; VAR root:ptr);
VAR p:ptr;
BEGIN
NEW(p);
p^.data:=x;
p^.left:=NIL; p^.right:=NIL;
IF root=NIL THEN root:=p { No tree, just insert }
ELSE
BEGIN
IF NOT SplaySearch(x,root) THEN { Is it already there? }
IF x<root^.data THEN { Less than? }
BEGIN
p^.right:=root; { Root item greater than }
p^.left:=root^.left; { Link up left child }
root^.left:=NIL; root:=p; { Break link; root=new item }
END
ELSE
IF x>root^.data THEN { Greater than? }
BEGIN
p^.left:=root; { Root item less than }
p^.right:=root^.right; { Link up right child }
root^.right:=NIL; root:=p; { Break link; root=new item }
END;
END;
END;
PROCEDURE BSDelete(x:key; VAR root:ptr);
VAR temp1,temp2,temp4:ptr;
temp3:key;
flg:boolean;
BEGIN
IF SplaySearch(x,root) THEN
BEGIN
temp1:=root^.left; temp2:=root^.right; { Save subtrees }
IF temp1<>NIL THEN { Is there a left subtree? }
BEGIN
temp4:=temp1;
WHILE temp4^.right<>NIL DO { MTF max left tree element }
temp4:=temp4^.right;
temp3:=temp4^.right^.data;
flg:=SplaySearch(temp3,temp1);
temp1^.right:=temp2; { Attach right subtree }
END ELSE temp1:=temp2; { Just attach right tree }
dispose(root);
root:=temp1; { Return new tree }
END;
END;
[LISTING THREE]
{*** Self-adjusting heap ***}
{*** Contents: Merge, Min, Insert, DeleteMin routines ***}
{ Data Structure:
ptr=^node;
node=RECORD data:item; left,right:ptr; END; }
FUNCTION Merge(q1,q2:ptr):ptr;
TYPE Qrec=RECORD
front,rear:ptr;
END;
VAR Q:Qrec;
PROCEDURE Enqueue(VAR q1:ptr; VAR Q:Qrec);
VAR temp:ptr;
BEGIN
temp:=q1; { Save top of heap }
q1:=q1^.right; { Point to next top of heap }
temp^.right:=temp^.left; { Swap right child to left }
temp^.left:=NIL; { Make sure left link's broken }
IF q.front=NIL THEN { Empty merge queue }
BEGIN
q.front:=temp; q.rear:=temp;
END
ELSE { Oops, just add to last leftchild }
BEGIN
q.rear^.left:=temp; q.rear:=temp;
END;
END;
BEGIN
q.front:=NIL; q.rear:=NIL; { Init merge queue }
WHILE (q1<>NIL) AND (q2<>NIL) DO { Pairwise compare and merge }
IF q1^.data<=q2^.data THEN Enqueue(q1,q)
ELSE Enqueue(q2,q);
IF (q1<>NIL) AND (q2=NIL) THEN
BEGIN
IF q.rear<>NIL THEN q.rear^.left:=q1
ELSE q.front:=q1;
END
IF (q1=NIL) AND (q2<>NIL) THEN
BEGIN
IF q.rear<>NIL THEN q.rear^.left:=q2
ELSE q.front:=q2;
END;
Merge:=q.front;
END;
FUNCTION Min(q1:ptr; VAR x:ptr):boolean;
BEGIN
x:=q1;
Min:=(q1<>NIL);
END;
PROCEDURE Insert(x:item; VAR q:ptr);
VAR p:ptr;
BEGIN
NEW(p); { Allocate }
p^.data:=x; { Fill it! }
p^.left:=NIL; p^.right:=NIL; { No children }
q:=Merge(q,p); { Add it to heap }
END;
FUNCTION DeleteMin(q:ptr; VAR x:ptr):ptr;
BEGIN
IF Min(q,x) THEN { Is there a min to delete? }
DeleteMin:=Merge(q^.left,q^.right)
ELSE DeleteMin:=NIL; { Nothing at all }
END;
{ Pairing Heaps as described by Tarjan, et al from Algorithmica:
Data Structure:
TYPE hptr=^node;
node=RECORD
wt:integer;
parent,left,right:hptr;
END; }
FUNCTION Merge(arg1,arg2:hptr):hptr;
BEGIN
IF (arg1<>NIL) AND (arg2<>NIL) THEN { 2 Queues to merge? }
BEGIN
IF arg1^.wt<arg2^.wt THEN { Which is minimal? }
BEGIN
arg2^.parent:=arg1; { Who's the parent? }
arg2^.right:=arg1^.left; { Point to arg1's child }
arg1^.left:=arg2; { It's officially a child }
Merge:=arg1;
END
ELSE
BEGIN
arg1^.parent:=arg2; { Who's the parent? }
arg1^.right:=arg2^.left; { Point to arg2's child }
arg2^.left:=arg1; { It's officially a child }
Merge:=arg2;
END;
END
ELSE
IF (arg1<>NIL) THEN Merge:=arg1 { Just arg1's queue }
ELSE Merge:=arg2 { Anything else }
END;
PROCEDURE Insert(a1,a2,x:integer; VAR root:hptr);
VAR p:hptr;
BEGIN
New(p); { Allocate }
p^.v1:=a1; p^.v2:=a2;
p^.wt:=x; p^.parent:=NIL; { Set key }
p^.left:=NIL; p^.right:=NIL; { Set pointers }
root:=Merge(p,root); { Add it... }
END;
FUNCTION Min(root:hptr; VAR minitem:hptr):boolean;
BEGIN
minitem:=root; { What's at the root? }
Min:=(minitem<>NIL); { Anything there? }
END;
FUNCTION DeleteMin(root:hptr; VAR minitem:hptr):hptr;
VAR arg1,arg2,p1:hptr;
BEGIN
IF Min(root,minitem) THEN
BEGIN
root:=NIL; { ReInit root }
p1:=minitem^.left; { Save kids }
WHILE p1<>NIL DO { For all subtrees }
BEGIN
arg1:=p1; { First Subtree }
p1:=p1^.right; { Move along }
arg2:=p1; { Next potential subtree }
IF p1<>NIL THEN p1:=p1^.right; { If not NIL, move on }
root:=Merge(Merge(arg1,arg2),root); { Merge result with current }
END;
IF root<>NIL THEN root^.right:=NIL;
DeleteMin:=root;
END ELSE DeleteMin:=NIL;
END;
FUNCTION LinkSearch(p:hptr):hptr;
VAR temp:hptr;
BEGIN
temp:=p^.parent^.left;
WHILE (temp<>p) AND (temp^.right<>p) AND (temp^.right<>NIL) DO
temp:=temp^.right;
LinkSearch:=temp;
END;
FUNCTION DecreaseKey(change:integer; p,root:hptr):hptr;
VAR temp:hptr;
BEGIN
IF (p<>NIL) AND (root<>NIL) THEN
BEGIN
p^.wt:=p^.wt-ABS(change);
IF p=root THEN DecreaseKey:=root
ELSE
BEGIN
temp:=LinkSearch(p);
IF temp=p THEN p^.parent^.left:=p^.parent^.left^.right
ELSE temp^.right:=p^.right;
DecreaseKey:=Merge(p,root);
END;
END;
END;
FUNCTION Delete(p,root:hptr):hptr;
VAR temp:hptr;
BEGIN
IF (p<>NIL) AND (root<>NIL) THEN
BEGIN
IF p=root THEN Delete:=DeleteMin(root,temp)
ELSE
BEGIN
temp:=LinkSearch(p);
IF temp=p THEN p^.parent^.left:=p^.parent^.left^.right
ELSE temp^.right:=p^.right;
Delete:=Merge(DeleteMin(p,temp),root);
END;
END ELSE Delete:=root;
END;