YAP 7.1.0
splay.yap
Go to the documentation of this file.
1/*************************************************************************
2* *
3* YAP Prolog *
4* *
5* Yap Prolog was developed at NCCUP - Universidade do Porto *
6* *
7* Copyright L.Damas, V.S.Costa and Universidade do Porto 1985-1997 *
8* *
9**************************************************************************
10* *
11* File: splay.yap *
12* Last rev: 5/12/99 *
13* mods: *
14* comments: Vijay Saraswat's implementation of Splay trees *
15* *
16*************************************************************************/
17
18/**
19 * @file splay.yap
20 * @author Vijay Saraswat
21 * @date Wed Nov 18 01:12:49 2015
22 *
23 * @brief "Self-adjusting Binary Search Trees
24 *
25 *
26*/
27
28:- module(splay,[
29 splay_access/5,
35
36/** @defgroup Splay_Trees Splay Trees
37@ingroup YAPLibrary
38@{
39
40Splay trees are explained in the paper "Self-adjusting Binary Search
41Trees", by D.D. Sleator and R.E. Tarjan, JACM, vol. 32, No.3, July 1985,
42p. 668. They are designed to support fast insertions, deletions and
43removals in binary search trees without the complexity of traditional
44balanced trees. The key idea is to allow the tree to become
45unbalanced. To make up for this, whenever we \ find a node, we move it up
46to the top. We use code by Vijay Saraswat originally posted to the Prolog
47mailing-list.
48
49Date: Sun 22 Mar 87 03:40:22-EST
50>From: vijay <Vijay.Saraswat@C.CS.CMU.EDU>
51Subject: Splay trees in LP languages.
52
53There have hardly been any interesting programs in this Digest for a
54long while now. Here is something which may stir the slothful among
55you! I present Prolog programs for implementing self-adjusting binary
56search trees, using splaying. These programs should be among the most
57efficient Prolog programs for maintaining binary search trees, with
58dynamic insertion and deletion.
59
60The algorithm is taken from: "Self-adjusting Binary Search Trees",
61D.D. Sleator and R.E. Tarjan, JACM, vol. 32, No.3, July 1985, p. 668.
62(See Tarjan's Turing Award lecture in this month's CACM for a more
63informal introduction).
64-----------------------------------------
65
66The operations provided by the program are:
67
681. access(i,t): (implemented by the call access(V, I, T, New))
69 "If item i is in tree t, return a pointer to its location;
70 otherwise return a pointer to the null node."
71 In our implementation, in the call access(V, I, T, New),
72 V is unifies with `null' if the item is not there, else
73 with `true' if it is there, in which case I is also
74 unified with that item.
75
762. insert(i,t): (implemented by the call insert(I, T, New))
77 "Insert item i in tree t, assuming that it is not there already."
78 (In our implementation, i is not inserted if it is already
79 there: rather it is unified with the item already in the tree.)
80
813. delete(i,t): (implemented by the call del(I, T, New))
82 "Delete item i from tree t, assuming that it is present."
83 (In our implementation, the call fails if the item is not in
84 the tree.)
85
864. join(t1,t2): (Implemented by the call join(T1, T2, New))
87 "Combine trees t1 and t2 into a single tree containing
88 all items from both trees, and return the resulting
89 tree. This operation assumes that all items in t1 are
90 less than all those in t2 and destroys both t1 and t2."
91
925. split(i,t): (implemented by the call split(I, T, Left, Right))
93 "Construct and return two trees t1 and t2, where t1
94 contains all items in t less than i, and t2 contains all
95 items in t greater than i. This operations destroys t."
96
97The basic workhorse is the routine bst(Op, Item, Tree, NewTree), which
98returns in NewTree a binary search tree obtained by searching for Item
99in< Tree and splaying. OP controls what must happen if Item is not
100found in the Tree. If Op = access(V), then V is unified with null if
101the item is not found in the tree, and with true if it is; in the
102latter case Item is also unified with the item found in the tree. In
103% the first case, splaying is done at the node at which the discovery
104% was made that Item was not in the tree, and in the second case
105% splaying is done at the node at which Item is found. If Op=insert,
106% then Item is inserted in the tree if it is not found, and splaying is
107% done at the new node; if the item is found, then splaying is done at
108% the node at which it is found.
109
110% A node is simply an n/3 structure: n(NodeValue, LeftSon, RightSon).
111% NodeValue could be as simple as an integer, or it could be a (Key,
112% Value) pair.
113
114
115% A node is simply an n/3 structure: n(NodeValue, LeftSon, RightSon).
116% NodeValue could be as simple as an integer, or it could be a (Key,
117% Value) pair.
118
119% Here are the top-level axioms. The algorithm for del/3 is the first
120% algorithm mentioned in the JACM paper: namely, first access the
121% element to be deleted, thus bringing it to the root, and then join its
122% sons. (join/4 is discussed later.)
123
124
125
126*/
127
128/*
129 @pred splay_access(- _Return_,+ _Key_,? _Val_,+ _Tree_,- _NewTree_)
130
131v
132If item _Key_ is in tree _Tree_, return its _Val_ and
133unify _Return_ with `true`. Otherwise unify _Return_ with
134`null`. The variable _NewTree_ unifies with the new tree.
135
136
137*/
138
139
140/** @pred splay_del(+ _Item_,+ _Tree_,- _NewTree_)
141
142
143Delete item _Key_ from tree _Tree_, assuming that it is present
144already. The variable _Val_ unifies with a value for key _Key_,
145and the variable _NewTree_ unifies with the new tree. The predicate
146will fail if _Key_ is not present.
147
148
149*/
150splay_access(V, Item, Val, Tree, NewTree):-
151 bst(access(V), Item, Val, Tree, NewTree).
152
153/** @pred splay_insert(+ _Key_,? _Val_,+ _Tree_,- _NewTree_)
154
155
156Insert item _Key_ in tree _Tree_, assuming that it is not
157there already. The variable _Val_ unifies with a value for key
158 _Key_, and the variable _NewTree_ unifies with the new
159tree. In our implementation, _Key_ is not inserted if it is
160already there: rather it is unified with the item already in the tree.
161
162
163*/
164splay_insert(Item, Val,Tree, NewTree):-
165 bst(insert, Item, Val, Tree, NewTree).
166
167splay_del(Item, Tree, NewTree):-
168 bst(access(true), Item, Val, Tree, n(Item, Val, Left, Right)),
169 splay_join(Left, Right, NewTree).
170
171/** @pred splay_join(+ _LeftTree_,+ _RighTree_,- _NewTree_)
172
173
174Combine trees _LeftTree_ and _RighTree_ into a single
175tree _NewTree_ containing all items from both trees. This operation
176assumes that all items in _LeftTree_ are less than all those in
177 _RighTree_ and destroys both _LeftTree_ and _RighTree_.
178
179
180*/
181splay_join(Left, Right, New):-
182 join(L-L, Left, Right, New).
183
184/** @pred splay_split(+ _Key_,? _Val_,+ _Tree_,- _LeftTree_,- _RightTree_)
185
186Construct and return two trees _LeftTree_ and _RightTree_,
187where _LeftTree_ contains all items in _Tree_ less than
188 _Key_, and _RightTree_ contains all items in _Tree_
189greater than _Key_. This operations destroys _Tree_.
190*/
191splay_split(Item, Val, Tree, Left, Right):-
192 bst(access(true), Item, Val, Tree, n(Item, Val, Left, Right)).
193
194% We now consider the definition of bst. We use the notion of
195% `difference-bsts'. There are two types of difference-bsts, a left one
196% and a right one. The left one is of the form T-L where T is a bst and
197% L is the *right* son of the node with the largest value in T. The
198% right one is of the form T-R where T is a binary search tree and R is
199% the *left* son of the node with the smallest value in T. An empty bst
200% is denoted by a variable. Hence L-L denotes the empty left (as well as
201% right) difference bst.
202
203% As discussed in the JACM paper, we start with a notion of a left
204% fragment and a right fragment of the new bst to be constructed.
205% Intially, the two fragments are empty.
206
207bst(Op, Item, Val, Tree, NewTree):-
208 bst(Op, Item, Val, L-L, Tree, R-R, NewTree).
209
210% We now consider the base cases. The empty tree is a variable: hence it
211% will unify with the atom null. (A non-empty tree is a n/3 structure,
212% which will not unify with null). If Item was being *access*ed, then it
213% was not found in the tree, and hence Null=null. On the other hand, if
214% the Item is found at the root, then the call terminates, with the New
215% Tree being set up appropriately.
216
217% The base clauses are:
218
219bst(access(Null), _Item, _, _L, null, _R, _Tree):- bst, Null = bst.
220bst(access(true), Item, Val, Left-A, n(Item0, Val0, A, B), Right-B, n(Item, Val, Left, Right)) :- Item == Item0, bst, Val = Val0.
221bst(insert, Item, Val, Left-A, T, Right-B, n(Item0, Val, Left, Right)) :-
222 (var(T) ; T = n(Item0, _Val0, A, B), Item == Item0), !, Item = Item0.
223% We now consider the zig case, namely that we have reached a node such
224% that the required Item is either to the left of the current node and
225% the current node is a leaf, or the required item is the left son of
226% the current node. Depending upon the Op, the appropriate action is
227% taken:
228bst(access(Null), Item, _, Left-L, n(X, VX, null, B), Right-B, n(X, VX, Left, Right)) :-
229 Item @< X, bst, Null = bst.
230bst(Op, Item, Val, Left, n(X, VX, n(Item, Val, A1, A2), B), R-n(X, VX, NR,B), New):-
231 Item @< X, bst,
232 bst(Op, Item, Val, Left, n(Item, Val, A1, A2), R-NR, New).
233% The recursive cases are straightforward:
234% Zig-Zig:
235bst(Op, Item, Val, Left, n(X, VX, n(Y, VY, Z, B), C), R-n(Y, VY, NR, n(X, VX, B, C)), New):-
236 Item @< X, Item @< Y, bst,
237 bst(Op, Item, Val, Left, Z, R-NR, New).
238% Zig-Zag:
239bst(Op, Item, Val, L-n(Y, VY, A, NL), n(X, _VX, n(Y, VY, A, Z), C), R-n(X, _NX, NR, C), New):-
240 Item @< X, Y @< Item,bst,
241 bst(Op, Item, Val, L-NL, Z, R-NR, New).
242% The symmetric cases for the right sons of the current node
243% are straightforward too:
244
245% Zag
246bst(access(Null), Item, _, Left-B, n(X, VX, B, null), Right-_R, n(X, VX, Left, Right)):-
247 X @< Item, bst, Null = bst. % end of the road.
248bst(Op, Item, Val, L-n(X, VX, B, NL), n(X, VX, B, n(Item, Val, A1, A2)), Right, New):-
249 X @< Item, bst,
250 bst(Op, Item, Val, L-NL, n(Item, Val, A1, A2), Right, New).
251% Zag-Zag
252bst(Op, Item, Val, L-n(Y, VY, n(X, VX, C, B), NL), n(X, VX, C, n(Y, VY, B, Z)), Right, New):-
253 X @< Item, Y @<Item,bst,
254 bst(Op, Item, Val, L-NL, Z, Right, New).
255% Zag-Zig
256bst(Op, Item, Val, L-n(X, VX, A, NL), n(X, VX, A, n(Y, VY, Z, C)), R-n(Y, VY, NR, C), New):-
257 X @< Item, Item @< Y,bst,
258 bst(Op, Item, Val, L-NL, Z, R-NR, New).
259
260% We now consider the definition of join. To join Left to Right, it is
261% sufficient to splay at the rightmost vertex in Left, and make Right
262% its Right son. To build NewTree, we initially start with an empty left
263join(Left-A, n(X, VX, A, var), Right, n(X, VX, Left, Right)):-join.
264join(Left-n(X, VX, A, B), n(X, VX, A, n(Y, VY, B, var)), Right, n(Y, VY, Left, Right)):- join.
265join(Left-n(Y, VY, n(X, VX, C, B), NL), n(X, VX, C, n(Y, VY, B, n(Z, VZ, A1, A2))), Right, New):-
266 join(Left-NL, n(Z, VZ,A1, A2), Right, New).
267
268
269/** @pred splay_init(- _NewTree_)
270
271
272Initialize a new splay tree.
273
274
275*/
276splay_init(_).
277
278/** @} */
279
280
splay_del(+ Item,+ Tree,- NewTree)
splay_init(- NewTree)
splay_insert(+ Key,? Val,+ Tree,- NewTree)
splay_join(+ LeftTree,+ RighTree,- NewTree)
splay_split(+ Key,? Val,+ Tree,- LeftTree,- RightTree)
var( T)