Splay Trees

Splay trees are explained in the paper "Self-adjusting Binary Search Trees", by D.D. More...

Detailed Description

Splay trees are explained in the paper "Self-adjusting Binary Search Trees", by D.D.

Sleator and R.E Tarjan, JACM, vol 32, No.3, July 1985, p 668 They are designed to support fast insertions, deletions and removals in binary search trees without the complexity of traditional balanced trees The key idea is to allow the tree to become unbalanced To make up for this, whenever we \ find a node, we move it up to the top We use code by Vijay Saraswat originally posted to the Prolog mailing-list

Date: Sun 22 Mar 87 03:40:22-EST >From: vijay Vijay.nosp@m..Sar.nosp@m.aswat.nosp@m.@C.C.nosp@m.S.CMU.nosp@m..EDU Subject: Splay trees in LP languages

There have hardly been any interesting programs in this Digest for a long while now Here is something which may stir the slothful among you! I present Prolog programs for implementing self-adjusting binary search trees, using splaying These programs should be among the most efficient Prolog programs for maintaining binary search trees, with dynamic insertion and deletion

The algorithm is taken from: "Self-adjusting Binary Search Trees", D.D Sleator and R.E Tarjan, JACM, vol 32, No.3, July 1985, p 668 (See Tarjan's Turing Award lecture in this month's CACM for a more

informal introduction).

The operations provided by the program are:

1. access(i,t): (implemented by the call access(V, I, T, New)) "If item i is in tree t, return a pointer to its location; otherwise return a pointer to the null node" In our implementation, in the call access(V, I, T, New), V is unifies with ‘null’ if the item is not there, else with ‘true’ if it is there, in which case I is also unified with that item
2. insert(i,t): (implemented by the call insert(I, T, New)) "Insert item i in tree t, assuming that it is not there already." (In our implementation, i is not inserted if it is already there: rather it is unified with the item already in the tree.)
3. delete(i,t): (implemented by the call del(I, T, New)) "Delete item i from tree t, assuming that it is present." (In our implementation, the call fails if the item is not in the tree.)
4. join(t1,t2): (Implemented by the call join(T1, T2, New)) "Combine trees t1 and t2 into a single tree containing all items from both trees, and return the resulting tree This operation assumes that all items in t1 are less than all those in t2 and destroys both t1 and t2"
5. split(i,t): (implemented by the call split(I, T, Left, Right)) "Construct and return two trees t1 and t2, where t1 contains all items in t less than i, and t2 contains all items in t greater than i This operations destroys t"

The basic workhorse is the routine bst(Op, Item, Tree, NewTree), which returns in NewTree a binary search tree obtained by searching for Item in< Tree and splaying OP controls what must happen if Item is not found in the Tree If Op = access(V), then V is unified with null if the item is not found in the tree, and with true if it is; in the latter case Item is also unified with the item found in the tree In the first case, splaying is done at the node at which the discovery was made that Item was not in the tree, and in the second case splaying is done at the node at which Item is found If Op=insert, then Item is inserted in the tree if it is not found, and splaying is done at the new node; if the item is found, then splaying is done at the node at which it is found

A node is simply an n/3 structure: n(NodeValue, LeftSon, RightSon) NodeValue could be as simple as an integer, or it could be a (Key, Value) pair

A node is simply an n/3 structure: n(NodeValue, LeftSon, RightSon) NodeValue could be as simple as an integer, or it could be a (Key, Value) pair

Here are the top-level axioms The algorithm for del/3 is the first algorithm mentioned in the JACM paper: namely, first access the element to be deleted, thus bringing it to the root, and then join its sons (join/4 is discussed later.)

---

Class Documentation

splay_del/3

class splay_del/3

splay_del(+ Item,+ Tree,- NewTree)

Delete item Key from tree Tree, assuming that it is present already The variable Val unifies with a value for key Key, and the variable NewTree unifies with the new tree The predicate will fail if Key is not present

splay_insert/4

class splay_insert/4

splay_insert(+ Key,? Val,+ Tree,- NewTree)

Insert item Key in tree Tree, assuming that it is not there already The variable Val unifies with a value for key Key, and the variable NewTree unifies with the new tree In our implementation, Key is not inserted if it is already there: rather it is unified with the item already in the tree

splay_join/3

class splay_join/3

splay_join(+ LeftTree,+ RighTree,- NewTree)

Combine trees LeftTree and RighTree into a single tree NewTree containing all items from both trees This operation assumes that all items in LeftTree are less than all those in RighTree and destroys both LeftTree and RighTree

splay_split/5

class splay_split/5

splay_split(+ Key,? Val,+ Tree,- LeftTree,- RightTree)

Construct and return two trees LeftTree and RightTree, where LeftTree contains all items in Tree less than Key, and RightTree contains all items in Tree greater than Key This operations destroys Tree

splay_init/1

class splay_init/1

splay_init(- NewTree)

Initialize a new splay tree