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,
30
splay_insert/4
,
31
splay_del/3
,
32
splay_init/1
,
33
splay_join/3
,
34
splay_split/5
]).
35
36
/** @defgroup Splay_Trees Splay Trees
37
@ingroup YAPLibrary
38
@{
39
40
Splay trees are explained in the paper "Self-adjusting Binary Search
41
Trees", by D.D. Sleator and R.E. Tarjan, JACM, vol. 32, No.3, July 1985,
42
p. 668. They are designed to support fast insertions, deletions and
43
removals in binary search trees without the complexity of traditional
44
balanced trees. The key idea is to allow the tree to become
45
unbalanced. To make up for this, whenever we \ find a node, we move it up
46
to the top. We use code by Vijay Saraswat originally posted to the Prolog
47
mailing-list.
48
49
Date: Sun 22 Mar 87 03:40:22-EST
50
>From: vijay <Vijay.Saraswat@C.CS.CMU.EDU>
51
Subject: Splay trees in LP languages.
52
53
There have hardly been any interesting programs in this Digest for a
54
long while now. Here is something which may stir the slothful among
55
you! I present Prolog programs for implementing self-adjusting binary
56
search trees, using splaying. These programs should be among the most
57
efficient Prolog programs for maintaining binary search trees, with
58
dynamic insertion and deletion.
59
60
The algorithm is taken from: "Self-adjusting Binary Search Trees",
61
D.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
63
informal introduction).
64
-----------------------------------------
65
66
The operations provided by the program are:
67
68
1. 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
76
2. 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
81
3. 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
86
4. 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
92
5. 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
97
The basic workhorse is the routine bst(Op, Item, Tree, NewTree), which
98
returns in NewTree a binary search tree obtained by searching for Item
99
in< Tree and splaying. OP controls what must happen if Item is not
100
found in the Tree. If Op = access(V), then V is unified with null if
101
the item is not found in the tree, and with true if it is; in the
102
latter 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
131
v
132
If item _Key_ is in tree _Tree_, return its _Val_ and
133
unify _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
143
Delete item _Key_ from tree _Tree_, assuming that it is present
144
already. The variable _Val_ unifies with a value for key _Key_,
145
and the variable _NewTree_ unifies with the new tree. The predicate
146
will fail if _Key_ is not present.
147
148
149
*/
150
splay_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
156
Insert item _Key_ in tree _Tree_, assuming that it is not
157
there already. The variable _Val_ unifies with a value for key
158
_Key_, and the variable _NewTree_ unifies with the new
159
tree. In our implementation, _Key_ is not inserted if it is
160
already there: rather it is unified with the item already in the tree.
161
162
163
*/
164
splay_insert
(
Item
,
Val
,
Tree
,
NewTree
)
:-
165
bst(insert,
Item
,
Val
,
Tree
,
NewTree
).
166
167
splay_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
174
Combine trees _LeftTree_ and _RighTree_ into a single
175
tree _NewTree_ containing all items from both trees. This operation
176
assumes that all items in _LeftTree_ are less than all those in
177
_RighTree_ and destroys both _LeftTree_ and _RighTree_.
178
179
180
*/
181
splay_join
(
Left
,
Right
,
New
)
:-
182
join(
L
-
L
,
Left
,
Right
,
New
).
183
184
/** @pred splay_split(+ _Key_,? _Val_,+ _Tree_,- _LeftTree_,- _RightTree_)
185
186
Construct and return two trees _LeftTree_ and _RightTree_,
187
where _LeftTree_ contains all items in _Tree_ less than
188
_Key_, and _RightTree_ contains all items in _Tree_
189
greater than _Key_. This operations destroys _Tree_.
190
*/
191
splay_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
207
bst(
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
219
bst(access(
Null
),
_Item
,
_
,
_L
, null,
_R
,
_Tree
)
:-
bst,
Null
=
bst.
220
bst(access(true),
Item
,
Val
,
Left
-
A
, n(
Item0
,
Val0
,
A
,
B
),
Right
-
B
, n(
Item
,
Val
,
Left
,
Right
))
:-
Item
==
Item0
,
bst,
Val
=
Val0
.
221
bst(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:
228
bst(access(
Null
),
Item
,
_
,
Left
-
L
, n(
X
,
VX
, null,
B
),
Right
-
B
, n(
X
,
VX
,
Left
,
Right
))
:-
229
Item
@<
X
,
bst,
Null
=
bst.
230
bst(
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:
235
bst(
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:
239
bst(
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
246
bst(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.
248
bst(
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
252
bst(
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
256
bst(
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
263
join(
Left
-
A
, n(
X
,
VX
,
A
, var),
Right
, n(
X
,
VX
,
Left
,
Right
))
:-
join.
264
join(
Left
-
n(
X
,
VX
,
A
,
B
), n(
X
,
VX
,
A
, n(
Y
,
VY
,
B
, var)),
Right
, n(
Y
,
VY
,
Left
,
Right
))
:-
join.
265
join(
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
272
Initialize a new splay tree.
273
274
275
*/
276
splay_init
(
_
).
277
278
/** @} */
279
280
splay_del/3
splay_del(+ Item,+ Tree,- NewTree)
splay_init/1
splay_init(- NewTree)
splay_insert/4
splay_insert(+ Key,? Val,+ Tree,- NewTree)
splay_join/3
splay_join(+ LeftTree,+ RighTree,- NewTree)
splay_split/5
splay_split(+ Key,? Val,+ Tree,- LeftTree,- RightTree)
var/1
var( T)
library
splay.yap
Generated by
1.9.3