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

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.

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.

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.

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.

Allen, B. and Munro, I. "Self-Organizing Search Trees." Journal of the ACM 25 (1978).

Fredman, M.L. et al. "The Pairing Heap: A New Form of Self-Adjusting Heap." Algorithmica 1 (1986).

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 Search Trees." Journal of the ACM 32 (1985).

Sleator, D.D., and Tarjan, R.E. "Self-Adjusting Heaps." SIAM Journal of Computing 15 (1986).

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

{*** 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;

{*** 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;