1 ;;;-------------------------------------------------------------------------
2 ;;; Search and splaying.
6 #0x00000000 (n = 1) (*) 2
7 #0x00000001 (n = 3) (*) 4
8 #0x00000002 (n = 1) (*) 6
9 #0x00000003 (n = 7) (*) 8
10 #0x00000004 (n = 1) (*) 10
11 #0x00000005 (n = 3) (*) 12
12 #0x00000006 (n = 1) (*) 14
13 #0x00000007 (n = 12) (*) 16
14 #0x00000008 (n = 1) (*) 18
15 #0x00000009 (n = 3) (*) 20
16 #0x0000000a (n = 1) (*) 22
17 #0x0000000b (n = 4) (*) 24
22 #0x0000000c (n = 1) (*) 2
23 #0x0000000e (n = 3) (*) 4
24 #0x0000000d (n = 1) (*) 6
25 #0x00000012 (n = 7) (*) 8
26 #0x0000000f (n = 1) (*) 10
27 #0x00000011 (n = 3) (*) 12
28 #0x00000010 (n = 1) (*) 14
29 #0x00000017 (n = 12) (*) 16
30 #0x00000013 (n = 1) (*) 18
31 #0x00000015 (n = 3) (*) 20
32 #0x00000014 (n = 1) (*) 22
33 #0x00000016 (n = 4) (*) 24
34 #<node #0x00000017 16>
38 XYLA-SPLAY SPLAY zig left child
40 #0x00000018 (n = 1) (*) 2
41 #0x0000001a (n = 3) (*) 4
42 #0x00000019 (n = 1) (*) 6
43 #0x0000001e (n = 12) (*) 8
44 #0x0000001b (n = 1) (*) 10
45 #0x0000001d (n = 3) (*) 12
46 #0x0000001c (n = 1) (*) 14
47 #0x00000023 (n = 8) (*) 16
48 #0x0000001f (n = 1) (*) 18
49 #0x00000021 (n = 3) (*) 20
50 #0x00000020 (n = 1) (*) 22
51 #0x00000022 (n = 4) (*) 24
54 XYLA-SPLAY SPLAY zig right child
56 #0x00000024 (n = 1) (*) 2
57 #0x00000026 (n = 3) (*) 4
58 #0x00000025 (n = 1) (*) 6
59 #0x0000002a (n = 7) (*) 8
60 #0x00000027 (n = 1) (*) 10
61 #0x00000029 (n = 3) (*) 12
62 #0x00000028 (n = 1) (*) 14
63 #0x0000002f (n = 11) (*) 16
64 #0x0000002b (n = 1) (*) 18
65 #0x0000002d (n = 3) (*) 20
66 #0x0000002c (n = 1) (*) 22
67 #0x0000002e (n = 12) (*) 24
68 #<node #0x0000002e 24>
72 XYLA-SPLAY SPLAY zig-zig left/left child
74 #0x00000030 (n = 1) (*) 2
75 #0x00000032 (n = 12) (*) 4
76 #0x00000031 (n = 1) (*) 6
77 #0x00000036 (n = 10) (*) 8
78 #0x00000033 (n = 1) (*) 10
79 #0x00000035 (n = 3) (*) 12
80 #0x00000034 (n = 1) (*) 14
81 #0x0000003b (n = 8) (*) 16
82 #0x00000037 (n = 1) (*) 18
83 #0x00000039 (n = 3) (*) 20
84 #0x00000038 (n = 1) (*) 22
85 #0x0000003a (n = 4) (*) 24
88 XYLA-SPLAY SPLAY zig-zig left/left child
89 XYLA-SPLAY SPLAY zig left child
91 #0x0000003c (n = 12) (*) 2
92 #0x0000003e (n = 6) (*) 4
93 #0x0000003d (n = 1) (*) 6
94 #0x00000042 (n = 5) (*) 8
95 #0x0000003f (n = 1) (*) 10
96 #0x00000041 (n = 3) (*) 12
97 #0x00000040 (n = 1) (*) 14
98 #0x00000047 (n = 11) (*) 16
99 #0x00000043 (n = 1) (*) 18
100 #0x00000045 (n = 3) (*) 20
101 #0x00000044 (n = 1) (*) 22
102 #0x00000046 (n = 4) (*) 24
103 #<node #0x0000003c 2>
105 XYLA-SPLAY SPLAY zig-zig right/right child
106 XYLA-SPLAY SPLAY zig left child
108 #0x00000048 (n = 1) (*) 2
109 #0x0000004a (n = 3) (*) 4
110 #0x00000049 (n = 1) (*) 6
111 #0x0000004e (n = 5) (*) 8
112 #0x0000004b (n = 1) (*) 10
113 #0x0000004d (n = 6) (*) 12
114 #0x0000004c (n = 12) (*) 14
115 #0x00000053 (n = 5) (*) 16
116 #0x0000004f (n = 1) (*) 18
117 #0x00000051 (n = 3) (*) 20
118 #0x00000050 (n = 1) (*) 22
119 #0x00000052 (n = 4) (*) 24
120 #<node #0x0000004c 14>
124 XYLA-SPLAY SPLAY zig-zag left/right child
126 #0x00000054 (n = 1) (*) 2
127 #0x00000056 (n = 3) (*) 4
128 #0x00000055 (n = 1) (*) 6
129 #0x0000005a (n = 5) (*) 8
130 #0x00000057 (n = 1) (*) 10
131 #0x00000059 (n = 12) (*) 12
132 #0x00000058 (n = 1) (*) 14
133 #0x0000005f (n = 6) (*) 16
134 #0x0000005b (n = 1) (*) 18
135 #0x0000005d (n = 3) (*) 20
136 #0x0000005c (n = 1) (*) 22
137 #0x0000005e (n = 4) (*) 24
138 #<node #0x00000059 12>
140 XYLA-SPLAY SPLAY zig-zag right/left child
142 #0x00000060 (n = 1) (*) 2
143 #0x00000062 (n = 3) (*) 4
144 #0x00000061 (n = 1) (*) 6
145 #0x00000066 (n = 7) (*) 8
146 #0x00000063 (n = 1) (*) 10
147 #0x00000065 (n = 3) (*) 12
148 #0x00000064 (n = 1) (*) 14
149 #0x0000006b (n = 9) (*) 16
150 #0x00000067 (n = 1) (*) 18
151 #0x00000069 (n = 12) (*) 20
152 #0x00000068 (n = 1) (*) 22
153 #0x0000006a (n = 2) (*) 24
154 #<node #0x00000069 20>
158 XYLA-SPLAY SPLAY zig-zig left/left child
159 XYLA-SPLAY SPLAY zig left child
161 #0x0000006c (n = 12) (*) 2
162 #0x0000006e (n = 6) (*) 4
163 #0x0000006d (n = 1) (*) 6
164 #0x00000072 (n = 5) (*) 8
165 #0x0000006f (n = 1) (*) 10
166 #0x00000071 (n = 3) (*) 12
167 #0x00000070 (n = 1) (*) 14
168 #0x00000077 (n = 11) (*) 16
169 #0x00000073 (n = 1) (*) 18
170 #0x00000075 (n = 3) (*) 20
171 #0x00000074 (n = 1) (*) 22
172 #0x00000076 (n = 4) (*) 24
175 XYLA-SPLAY SPLAY zig-zag right/left child
176 XYLA-SPLAY SPLAY zig left child
178 #0x00000078 (n = 1) (*) 2
179 #0x0000007a (n = 3) (*) 4
180 #0x00000079 (n = 1) (*) 6
181 #0x0000007e (n = 4) (*) 8
182 #0x0000007b (n = 12) (*) 10
183 #0x0000007d (n = 2) (*) 12
184 #0x0000007c (n = 1) (*) 14
185 #0x00000083 (n = 7) (*) 16
186 #0x0000007f (n = 1) (*) 18
187 #0x00000081 (n = 3) (*) 20
188 #0x00000080 (n = 1) (*) 22
189 #0x00000082 (n = 4) (*) 24
192 XYLA-SPLAY SPLAY zig-zig right/right child
193 XYLA-SPLAY SPLAY zig left child
195 #0x00000084 (n = 1) (*) 2
196 #0x00000086 (n = 3) (*) 4
197 #0x00000085 (n = 1) (*) 6
198 #0x0000008a (n = 5) (*) 8
199 #0x00000087 (n = 1) (*) 10
200 #0x00000089 (n = 6) (*) 12
201 #0x00000088 (n = 12) (*) 14
202 #0x0000008f (n = 5) (*) 16
203 #0x0000008b (n = 1) (*) 18
204 #0x0000008d (n = 3) (*) 20
205 #0x0000008c (n = 1) (*) 22
206 #0x0000008e (n = 4) (*) 24
209 XYLA-SPLAY SPLAY zig-zig left/left child
210 XYLA-SPLAY SPLAY zig right child
212 #0x00000090 (n = 1) (*) 2
213 #0x00000092 (n = 3) (*) 4
214 #0x00000091 (n = 1) (*) 6
215 #0x00000096 (n = 7) (*) 8
216 #0x00000093 (n = 1) (*) 10
217 #0x00000095 (n = 3) (*) 12
218 #0x00000094 (n = 1) (*) 14
219 #0x0000009b (n = 8) (*) 16
220 #0x00000097 (n = 12) (*) 18
221 #0x00000099 (n = 3) (*) 20
222 #0x00000098 (n = 1) (*) 22
223 #0x0000009a (n = 2) (*) 24
226 XYLA-SPLAY SPLAY zig-zag left/right child
227 XYLA-SPLAY SPLAY zig right child
229 #0x0000009c (n = 1) (*) 2
230 #0x0000009e (n = 3) (*) 4
231 #0x0000009d (n = 1) (*) 6
232 #0x000000a2 (n = 7) (*) 8
233 #0x0000009f (n = 1) (*) 10
234 #0x000000a1 (n = 3) (*) 12
235 #0x000000a0 (n = 1) (*) 14
236 #0x000000a7 (n = 10) (*) 16
237 #0x000000a3 (n = 1) (*) 18
238 #0x000000a5 (n = 2) (*) 20
239 #0x000000a4 (n = 12) (*) 22
240 #0x000000a6 (n = 1) (*) 24
243 ;; Splaying example from the paper.
245 #0x000000a8 (n = 1) (*) 5
246 #0x000000b4 (n = 13) (*) 10
247 #0x000000a9 (n = 1) (*) 15
248 #0x000000b1 (n = 9) (*) 20
249 #0x000000aa (n = 1) (*) 25
250 #0x000000b0 (n = 7) (*) 30
251 #0x000000ab (n = 1) (*) 35
252 #0x000000af (n = 5) (*) 40
253 #0x000000ac (n = 1) (*) 45
254 #0x000000ae (n = 3) (*) 50
255 #0x000000ad (n = 1) (*) 55
256 #0x000000b3 (n = 11) (*) 60
257 #0x000000b2 (n = 1) (*) 65
258 #0x000000b6 (n = 15) (*) 70
259 #0x000000b5 (n = 1) (*) 75
260 #0x000000b8 (n = 17) (*) 80
261 #0x000000b7 (n = 1) (*) 85
262 #0x000000ba (n = 19) (*) 90
263 #0x000000b9 (n = 1) (*) 95
266 #0x000000a8 (n = 1) (*) 5
267 #0x000000b4 (n = 9) (*) 10
268 #0x000000a9 (n = 1) (*) 15
269 #0x000000b1 (n = 7) (*) 20
270 #0x000000aa (n = 1) (*) 25
271 #0x000000b0 (n = 3) (*) 30
272 #0x000000ab (n = 1) (*) 35
273 #0x000000af (n = 5) (*) 40
274 #0x000000ac (n = 1) (*) 45
275 #0x000000ae (n = 19) (*) 50
276 #0x000000ad (n = 1) (*) 55
277 #0x000000b3 (n = 3) (*) 60
278 #0x000000b2 (n = 1) (*) 65
279 #0x000000b6 (n = 5) (*) 70
280 #0x000000b5 (n = 1) (*) 75
281 #0x000000b8 (n = 9) (*) 80
282 #0x000000b7 (n = 1) (*) 85
283 #0x000000ba (n = 3) (*) 90
284 #0x000000b9 (n = 1) (*) 95
285 #<node #0x000000ae 50>
287 ;; All zig-zig example from the paper.
289 #0x000000bb (n = 1) (*) 5
290 #0x000000bd (n = 3) (*) 10
291 #0x000000bc (n = 1) (*) 15
292 #0x000000bf (n = 5) (*) 20
293 #0x000000be (n = 1) (*) 25
294 #0x000000c1 (n = 7) (*) 30
295 #0x000000c0 (n = 1) (*) 35
296 #0x000000c3 (n = 9) (*) 40
297 #0x000000c2 (n = 1) (*) 45
298 #0x000000c5 (n = 11) (*) 50
299 #0x000000c4 (n = 1) (*) 55
300 #0x000000c7 (n = 13) (*) 60
301 #0x000000c6 (n = 1) (*) 65
302 #0x000000c9 (n = 15) (*) 70
303 #0x000000c8 (n = 1) (*) 75
306 #0x000000bb (n = 1) (*) 5
307 #0x000000bd (n = 15) (*) 10
308 #0x000000bc (n = 1) (*) 15
309 #0x000000bf (n = 5) (*) 20
310 #0x000000be (n = 1) (*) 25
311 #0x000000c1 (n = 3) (*) 30
312 #0x000000c0 (n = 1) (*) 35
313 #0x000000c3 (n = 9) (*) 40
314 #0x000000c2 (n = 1) (*) 45
315 #0x000000c5 (n = 3) (*) 50
316 #0x000000c4 (n = 1) (*) 55
317 #0x000000c7 (n = 13) (*) 60
318 #0x000000c6 (n = 1) (*) 65
319 #0x000000c9 (n = 3) (*) 70
320 #0x000000c8 (n = 1) (*) 75
321 #<node #0x000000bd 10>
323 ;; All zig-zag example from the paper.
325 #0x000000ca (n = 1) (*) 5
326 #0x000000d6 (n = 13) (*) 10
327 #0x000000cb (n = 1) (*) 15
328 #0x000000d3 (n = 9) (*) 20
329 #0x000000cc (n = 1) (*) 25
330 #0x000000d0 (n = 5) (*) 30
331 #0x000000cd (n = 1) (*) 35
332 #0x000000cf (n = 3) (*) 40
333 #0x000000ce (n = 1) (*) 45
334 #0x000000d2 (n = 7) (*) 50
335 #0x000000d1 (n = 1) (*) 55
336 #0x000000d5 (n = 11) (*) 60
337 #0x000000d4 (n = 1) (*) 65
338 #0x000000d8 (n = 15) (*) 70
339 #0x000000d7 (n = 1) (*) 75
342 #0x000000ca (n = 1) (*) 5
343 #0x000000d6 (n = 7) (*) 10
344 #0x000000cb (n = 1) (*) 15
345 #0x000000d3 (n = 5) (*) 20
346 #0x000000cc (n = 1) (*) 25
347 #0x000000d0 (n = 3) (*) 30
348 #0x000000cd (n = 1) (*) 35
349 #0x000000cf (n = 15) (*) 40
350 #0x000000ce (n = 1) (*) 45
351 #0x000000d2 (n = 3) (*) 50
352 #0x000000d1 (n = 1) (*) 55
353 #0x000000d5 (n = 5) (*) 60
354 #0x000000d4 (n = 1) (*) 65
355 #0x000000d8 (n = 7) (*) 70
356 #0x000000d7 (n = 1) (*) 75
357 #<node #0x000000cf 40>
359 ;; Unsuccessful search example from the paper. The same setup is used for
360 ;; some later examples, and I've modified it because I consistently use the
361 ;; leftmost node of the right tree as the joining node, rather than the
362 ;; rightmost node of the left tree.
364 #0x000000e3 (n = 1) (*) 10
365 #0x000000e7 (n = 5) (*) 20
366 #0x000000e6 (n = 3) (*) 30
367 #0x000000e4 (n = 1) (*) 35
368 #0x000000e5 (n = 2) (*) 40
369 #0x000000ec (n = 10) (*) 50
370 #0x000000eb (n = 4) (*) 60
371 #0x000000e8 (n = 1) (*) 70
372 #0x000000ea (n = 3) (*) 90
373 #0x000000e9 (n = 1) (*) 100
376 #0x000000e3 (n = 1) (*) 10
377 #0x000000e7 (n = 5) (*) 20
378 #0x000000e6 (n = 3) (*) 30
379 #0x000000e4 (n = 1) (*) 35
380 #0x000000e5 (n = 2) (*) 40
381 #0x000000ec (n = 7) (*) 50
382 #0x000000eb (n = 1) (*) 60
383 #0x000000e8 (n = 10) (*) 70
384 #0x000000ea (n = 2) (*) 90
385 #0x000000e9 (n = 1) (*) 100
388 ;;;-------------------------------------------------------------------------
393 #0x000000ed (n = 1) (*) 2
394 #0x000000ee (n = 3) (*) 4
395 #0x000000ef (n = 1) (*) 6
396 #0x000000f0 (n = 7) (*) 8
397 #0x000000f1 (n = 1) (*) 10
398 #0x000000f2 (n = 3) (*) 12
399 #0x000000f3 (n = 1) (*) 14
400 #0x000000f4 (n = 12) (*) 16
401 #0x000000f5 (n = 1) (*) 18
402 #0x000000f6 (n = 3) (*) 20
403 #0x000000f7 (n = 1) (*) 22
404 #0x000000f8 (n = 4) (*) 24
408 XYLA-SPLAY SPLAY zig-zig right/right child
410 #0x000000f9 (n = 1) (*) 2
411 #0x000000fb (n = 3) (*) 4
412 #0x000000fa (n = 1) (*) 6
413 #0x000000ff (n = 7) (*) 8
414 #0x000000fc (n = 1) (*) 10
415 #0x000000fe (n = 3) (*) 12
416 #0x000000fd (n = 1) (*) 14
417 #0x00000104 (n = 11) (*) 16
418 #0x00000100 (n = 1) (*) 18
419 #0x00000102 (n = 3) (*) 20
420 #0x00000101 (n = 1) (*) 22
421 #0x00000103 (n = 12) (*) 24
422 #0x00000105 (n = 13) (*) 25
426 XYLA-SPLAY SPLAY zig-zig right/right child
427 XYLA-SPLAY SPLAY zig-zag right/left child
429 #0x00000106 (n = 1) (*) 2
430 #0x00000108 (n = 3) (*) 4
431 #0x00000107 (n = 1) (*) 6
432 #0x0000010c (n = 7) (*) 8
433 #0x00000109 (n = 1) (*) 10
434 #0x0000010b (n = 3) (*) 12
435 #0x0000010a (n = 1) (*) 14
436 #0x00000111 (n = 11) (*) 16
437 #0x0000010d (n = 1) (*) 18
438 #0x0000010f (n = 2) (*) 20
439 #0x0000010e (n = 3) (*) 22
440 #0x00000112 (n = 13) (*) 23
441 #0x00000110 (n = 1) (*) 24
443 ;; Insertion example from the paper.
445 #0x000000d9 (n = 1) (*) 10
446 #0x000000dd (n = 5) (*) 20
447 #0x000000dc (n = 3) (*) 30
448 #0x000000da (n = 1) (*) 35
449 #0x000000db (n = 2) (*) 40
450 #0x000000e2 (n = 10) (*) 50
451 #0x000000e1 (n = 4) (*) 60
452 #0x000000de (n = 1) (*) 70
453 #0x000000e0 (n = 3) (*) 90
454 #0x000000df (n = 1) (*) 100
457 #0x000000d9 (n = 1) (*) 10
458 #0x000000dd (n = 5) (*) 20
459 #0x000000dc (n = 3) (*) 30
460 #0x000000da (n = 1) (*) 35
461 #0x000000db (n = 2) (*) 40
462 #0x000000e2 (n = 6) (*) 50
463 #0x000000e1 (n = 8) (*) 60
464 #0x000000de (n = 1) (*) 70
465 #0x00000113 (n = 11) (*) 80
466 #0x000000e0 (n = 2) (*) 90
467 #0x000000df (n = 1) (*) 100
469 ;;;-------------------------------------------------------------------------
474 #0x00000114 (n = 1) (*) 2
475 #0x00000115 (n = 3) (*) 4
476 #0x00000116 (n = 1) (*) 6
477 #0x00000117 (n = 7) (*) 8
478 #0x00000118 (n = 1) (*) 10
479 #0x00000119 (n = 3) (*) 12
480 #0x0000011a (n = 1) (*) 14
481 #0x0000011b (n = 12) (*) 16
482 #0x0000011c (n = 1) (*) 18
483 #0x0000011d (n = 3) (*) 20
484 #0x0000011e (n = 1) (*) 22
485 #0x0000011f (n = 4) (*) 24
489 XYLA-SPLAY SPLAY zig-zig left/left child
491 #0x00000120 (n = 1) (*) 2
492 #0x00000122 (n = 3) (*) 4
493 #0x00000121 (n = 1) (*) 6
494 #0x00000126 (n = 7) (*) 8
495 #0x00000123 (n = 1) (*) 10
496 #0x00000125 (n = 3) (*) 12
497 #0x00000124 (n = 1) (*) 14
498 #0x00000127 (n = 11) (*) 18
499 #0x00000129 (n = 3) (*) 20
500 #0x00000128 (n = 1) (*) 22
501 #0x0000012a (n = 2) (*) 24
505 XYLA-SPLAY SPLAY zig left child
507 #0x0000012c (n = 1) (*) 2
508 #0x0000012e (n = 3) (*) 4
509 #0x0000012d (n = 1) (*) 6
510 #0x0000012f (n = 6) (*) 10
511 #0x00000131 (n = 2) (*) 12
512 #0x00000130 (n = 1) (*) 14
513 #0x00000137 (n = 11) (*) 16
514 #0x00000133 (n = 1) (*) 18
515 #0x00000135 (n = 3) (*) 20
516 #0x00000134 (n = 1) (*) 22
517 #0x00000136 (n = 4) (*) 24
521 XYLA-SPLAY SPLAY zig-zag left/right child
523 #0x00000138 (n = 1) (*) 2
524 #0x0000013a (n = 3) (*) 4
525 #0x00000139 (n = 1) (*) 6
526 #0x0000013e (n = 5) (*) 8
527 #0x0000013b (n = 1) (*) 10
528 #0x0000013d (n = 11) (*) 12
529 #0x00000143 (n = 5) (*) 16
530 #0x0000013f (n = 1) (*) 18
531 #0x00000141 (n = 3) (*) 20
532 #0x00000140 (n = 1) (*) 22
533 #0x00000142 (n = 4) (*) 24
535 XYLA-SPLAY SPLAY zig-zag right/left child
537 #0x00000144 (n = 1) (*) 2
538 #0x00000146 (n = 3) (*) 4
539 #0x00000145 (n = 1) (*) 6
540 #0x0000014a (n = 7) (*) 8
541 #0x00000147 (n = 1) (*) 10
542 #0x00000149 (n = 3) (*) 12
543 #0x00000148 (n = 1) (*) 14
544 #0x0000014f (n = 8) (*) 16
545 #0x0000014d (n = 11) (*) 20
546 #0x0000014c (n = 1) (*) 22
547 #0x0000014e (n = 2) (*) 24
549 ;; Removal example from the paper, modified for difference in join policy.
551 #0x000000d9 (n = 1) (*) 10
552 #0x000000dd (n = 5) (*) 20
553 #0x000000dc (n = 3) (*) 30
554 #0x000000da (n = 1) (*) 35
555 #0x000000db (n = 2) (*) 40
556 #0x000000e2 (n = 6) (*) 50
557 #0x000000e1 (n = 8) (*) 60
558 #0x000000de (n = 1) (*) 70
559 #0x00000113 (n = 11) (*) 80
560 #0x000000e0 (n = 2) (*) 90
561 #0x000000df (n = 1) (*) 100
564 #0x000000d9 (n = 1) (*) 10
565 #0x000000dc (n = 4) (*) 30
566 #0x000000da (n = 1) (*) 35
567 #0x000000db (n = 2) (*) 40
568 #0x000000e2 (n = 10) (*) 50
569 #0x000000e1 (n = 5) (*) 60
570 #0x000000de (n = 1) (*) 70
571 #0x00000113 (n = 4) (*) 80
572 #0x000000e0 (n = 2) (*) 90
573 #0x000000df (n = 1) (*) 100
575 ;;;-------------------------------------------------------------------------
578 ;; With joining node. (Trivial!)
580 #0x00000150 (n = 1) (*) 1
581 #0x00000151 (n = 3) (*) 2
582 #0x00000152 (n = 1) (*) 3
583 #0x00000153 (n = 7) (*) 4
584 #0x00000154 (n = 1) (*) 5
585 #0x00000155 (n = 3) (*) 6
586 #0x00000156 (n = 1) (*) 7
587 #0x00000157 (n = 12) (*) 8
588 #0x00000158 (n = 1) (*) 9
589 #0x00000159 (n = 3) (*) 10
590 #0x0000015a (n = 1) (*) 11
591 #0x0000015b (n = 4) (*) 12
593 #0x0000015c (n = 1) (*) 14
594 #0x0000015d (n = 3) (*) 15
595 #0x0000015e (n = 1) (*) 16
596 #0x0000015f (n = 7) (*) 17
597 #0x00000160 (n = 1) (*) 18
598 #0x00000161 (n = 3) (*) 19
599 #0x00000162 (n = 1) (*) 20
600 #0x00000163 (n = 12) (*) 21
601 #0x00000164 (n = 1) (*) 22
602 #0x00000165 (n = 3) (*) 23
603 #0x00000166 (n = 1) (*) 24
604 #0x00000167 (n = 4) (*) 25
607 #0x00000150 (n = 1) (*) 1
608 #0x00000151 (n = 3) (*) 2
609 #0x00000152 (n = 1) (*) 3
610 #0x00000153 (n = 7) (*) 4
611 #0x00000154 (n = 1) (*) 5
612 #0x00000155 (n = 3) (*) 6
613 #0x00000156 (n = 1) (*) 7
614 #0x00000157 (n = 12) (*) 8
615 #0x00000158 (n = 1) (*) 9
616 #0x00000159 (n = 3) (*) 10
617 #0x0000015a (n = 1) (*) 11
618 #0x0000015b (n = 4) (*) 12
619 #0x00000168 (n = 25) (*) 13
620 #0x0000015c (n = 1) (*) 14
621 #0x0000015d (n = 3) (*) 15
622 #0x0000015e (n = 1) (*) 16
623 #0x0000015f (n = 7) (*) 17
624 #0x00000160 (n = 1) (*) 18
625 #0x00000161 (n = 3) (*) 19
626 #0x00000162 (n = 1) (*) 20
627 #0x00000163 (n = 12) (*) 21
628 #0x00000164 (n = 1) (*) 22
629 #0x00000165 (n = 3) (*) 23
630 #0x00000166 (n = 1) (*) 24
631 #0x00000167 (n = 4) (*) 25
633 ;; Without joining node.
635 #0x00000169 (n = 1) (*) 1
636 #0x0000016a (n = 3) (*) 2
637 #0x0000016b (n = 1) (*) 3
638 #0x0000016c (n = 7) (*) 4
639 #0x0000016d (n = 1) (*) 5
640 #0x0000016e (n = 3) (*) 6
641 #0x0000016f (n = 1) (*) 7
642 #0x00000170 (n = 12) (*) 8
643 #0x00000171 (n = 1) (*) 9
644 #0x00000172 (n = 3) (*) 10
645 #0x00000173 (n = 1) (*) 11
646 #0x00000174 (n = 4) (*) 12
648 #0x00000175 (n = 1) (*) 14
649 #0x00000176 (n = 3) (*) 15
650 #0x00000177 (n = 1) (*) 16
651 #0x00000178 (n = 7) (*) 17
652 #0x00000179 (n = 1) (*) 18
653 #0x0000017a (n = 3) (*) 19
654 #0x0000017b (n = 1) (*) 20
655 #0x0000017c (n = 12) (*) 21
656 #0x0000017d (n = 1) (*) 22
657 #0x0000017e (n = 3) (*) 23
658 #0x0000017f (n = 1) (*) 24
659 #0x00000180 (n = 4) (*) 25
662 #0x00000169 (n = 1) (*) 1
663 #0x0000016a (n = 3) (*) 2
664 #0x0000016b (n = 1) (*) 3
665 #0x0000016c (n = 7) (*) 4
666 #0x0000016d (n = 1) (*) 5
667 #0x0000016e (n = 3) (*) 6
668 #0x0000016f (n = 1) (*) 7
669 #0x00000170 (n = 12) (*) 8
670 #0x00000171 (n = 1) (*) 9
671 #0x00000172 (n = 3) (*) 10
672 #0x00000173 (n = 1) (*) 11
673 #0x00000174 (n = 4) (*) 12
674 #0x00000175 (n = 24) (*) 14
675 #0x00000176 (n = 6) (*) 15
676 #0x00000177 (n = 1) (*) 16
677 #0x00000178 (n = 5) (*) 17
678 #0x00000179 (n = 1) (*) 18
679 #0x0000017a (n = 3) (*) 19
680 #0x0000017b (n = 1) (*) 20
681 #0x0000017c (n = 11) (*) 21
682 #0x0000017d (n = 1) (*) 22
683 #0x0000017e (n = 3) (*) 23
684 #0x0000017f (n = 1) (*) 24
685 #0x00000180 (n = 4) (*) 25
687 ;;;-------------------------------------------------------------------------
690 ;; Initial state: right-trailing vine.
692 #0x0000018f (n = 15) (*) 1
693 #0x0000018e (n = 14) (*) 2
694 #0x0000018d (n = 13) (*) 3
695 #0x0000018c (n = 12) (*) 4
696 #0x0000018b (n = 11) (*) 5
697 #0x0000018a (n = 10) (*) 6
698 #0x00000189 (n = 9) (*) 7
699 #0x00000188 (n = 8) (*) 8
700 #0x00000187 (n = 7) (*) 9
701 #0x00000186 (n = 6) (*) 10
702 #0x00000185 (n = 5) (*) 11
703 #0x00000184 (n = 4) (*) 12
704 #0x00000183 (n = 3) (*) 13
705 #0x00000182 (n = 2) (*) 14
706 #0x00000181 (n = 1) (*) 15
711 #0x0000019e (n = 1) (*) 1
712 #0x0000019d (n = 3) (*) 2
713 #0x0000019c (n = 1) (*) 3
714 #0x0000019b (n = 7) (*) 4
715 #0x0000019a (n = 1) (*) 5
716 #0x00000199 (n = 3) (*) 6
717 #0x00000198 (n = 1) (*) 7
718 #0x00000197 (n = 15) (*) 8
719 #0x00000196 (n = 1) (*) 9
720 #0x00000195 (n = 3) (*) 10
721 #0x00000194 (n = 1) (*) 11
722 #0x00000193 (n = 7) (*) 12
723 #0x00000192 (n = 1) (*) 13
724 #0x00000191 (n = 3) (*) 14
725 #0x00000190 (n = 1) (*) 15
728 ;; Full path tracking.
729 (#<link root -> node #0x000001a2 12>)
731 #0x000001ad (n = 1) (*) 1
732 #0x000001ac (n = 3) (*) 2
733 #0x000001ab (n = 1) (*) 3
734 #0x000001aa (n = 7) (*) 4
735 #0x000001a9 (n = 1) (*) 5
736 #0x000001a8 (n = 3) (*) 6
737 #0x000001a7 (n = 1) (*) 7
738 #0x000001a6 (n = 15) (*) 8
739 #0x000001a5 (n = 1) (*) 9
740 #0x000001a4 (n = 3) (*) 10
741 #0x000001a3 (n = 1) (*) 11
742 #0x000001a2 (n = 7) (*) 12
743 #0x000001a1 (n = 1) (*) 13
744 #0x000001a0 (n = 3) (*) 14
745 #0x0000019f (n = 1) (*) 15
746 (#<link root -> node #0x000001a2 12>)
748 ;; Empty path tracking.
749 (#<link root -> node #0x000001b1 12>)
751 #0x000001bc (n = 1) (*) 1
752 #0x000001bb (n = 3) (*) 2
753 #0x000001ba (n = 1) (*) 3
754 #0x000001b9 (n = 7) (*) 4
755 #0x000001b8 (n = 1) (*) 5
756 #0x000001b7 (n = 3) (*) 6
757 #0x000001b6 (n = 1) (*) 7
758 #0x000001b5 (n = 15) (*) 8
759 #0x000001b4 (n = 1) (*) 9
760 #0x000001b3 (n = 3) (*) 10
761 #0x000001b2 (n = 1) (*) 11
762 #0x000001b1 (n = 7) (*) 12
763 #0x000001b0 (n = 1) (*) 13
764 #0x000001af (n = 3) (*) 14
765 #0x000001ae (n = 1) (*) 15
766 (#<link root -> node #0x000001b1 12> #<node #0x000001b1 12 left> -> (nil))
767 (#<link root -> node #0x000001c0 12>)
769 #0x000001cb (n = 1) (*) 1
770 #0x000001ca (n = 3) (*) 2
771 #0x000001c9 (n = 1) (*) 3
772 #0x000001c8 (n = 7) (*) 4
773 #0x000001c7 (n = 1) (*) 5
774 #0x000001c6 (n = 3) (*) 6
775 #0x000001c5 (n = 1) (*) 7
776 #0x000001c4 (n = 15) (*) 8
777 #0x000001c3 (n = 1) (*) 9
778 #0x000001c2 (n = 3) (*) 10
779 #0x000001c1 (n = 1) (*) 11
780 #0x000001c0 (n = 7) (*) 12
781 #0x000001bf (n = 1) (*) 13
782 #0x000001be (n = 3) (*) 14
783 #0x000001bd (n = 1) (*) 15
784 (#<link root -> node #0x000001c0 12> #<node #0x000001c0 12 right> -> (nil))
786 ;; A tree with a very long left-leaning tentril in the middle.
788 #0x000001cc (n = 1) (*) 101
789 #0x000001cd (n = 3) (*) 102
790 #0x000001ce (n = 1) (*) 103
791 #0x000001cf (n = 7) (*) 104
792 #0x000001d0 (n = 1) (*) 105
793 #0x000001d1 (n = 3) (*) 106
794 #0x000001d2 (n = 1) (*) 107
795 #0x000001d3 (n = 15) (*) 108
796 #0x000001d4 (n = 1) (*) 109
797 #0x000001d5 (n = 3) (*) 110
798 #0x000001d6 (n = 1) (*) 111
799 #0x000001d7 (n = 7) (*) 112
800 #0x000001d8 (n = 1) (*) 113
801 #0x000001d9 (n = 3) (*) 114
802 #0x000001da (n = 1) (*) 115
803 #0x00000270 (n = 165) (*) 116
804 #0x000001db (n = 1) (*) 117
805 #0x00000263 (n = 137) (*) 118
806 #0x000001dc (n = 1) (*) 490
807 #0x000001dd (n = 2) (*) 491
808 #0x000001de (n = 3) (*) 492
809 #0x000001df (n = 4) (*) 493
810 #0x000001e0 (n = 5) (*) 494
811 #0x000001e1 (n = 6) (*) 495
812 #0x000001e2 (n = 7) (*) 496
813 #0x000001e3 (n = 8) (*) 497
814 #0x000001e4 (n = 9) (*) 498
815 #0x000001e5 (n = 10) (*) 499
816 #0x000001e6 (n = 11) (*) 500
817 #0x000001e7 (n = 12) (*) 501
818 #0x000001e8 (n = 13) (*) 502
819 #0x000001e9 (n = 14) (*) 503
820 #0x000001ea (n = 15) (*) 504
821 #0x000001eb (n = 16) (*) 505
822 #0x000001ec (n = 17) (*) 506
823 #0x000001ed (n = 18) (*) 507
824 #0x000001ee (n = 19) (*) 508
825 #0x000001ef (n = 20) (*) 509
826 #0x000001f0 (n = 21) (*) 510
827 #0x000001f1 (n = 22) (*) 511
828 #0x000001f2 (n = 23) (*) 512
829 #0x000001f3 (n = 24) (*) 513
830 #0x000001f4 (n = 25) (*) 514
831 #0x000001f5 (n = 26) (*) 515
832 #0x000001f6 (n = 27) (*) 516
833 #0x000001f7 (n = 28) (*) 517
834 #0x000001f8 (n = 29) (*) 518
835 #0x000001f9 (n = 30) (*) 519
836 #0x000001fa (n = 31) (*) 520
837 #0x000001fb (n = 32) (*) 521
838 #0x000001fc (n = 33) (*) 522
839 #0x000001fd (n = 34) (*) 523
840 #0x000001fe (n = 35) (*) 524
841 #0x000001ff (n = 36) (*) 525
842 #0x00000200 (n = 37) (*) 526
843 #0x00000201 (n = 38) (*) 527
844 #0x00000202 (n = 39) (*) 528
845 #0x00000203 (n = 40) (*) 529
846 #0x00000204 (n = 41) (*) 530
847 #0x00000205 (n = 42) (*) 531
848 #0x00000206 (n = 43) (*) 532
849 #0x00000207 (n = 44) (*) 533
850 #0x00000208 (n = 45) (*) 534
851 #0x00000209 (n = 46) (*) 535
852 #0x0000020a (n = 47) (*) 536
853 #0x0000020b (n = 48) (*) 537
854 #0x0000020c (n = 49) (*) 538
855 #0x0000020d (n = 50) (*) 539
856 #0x0000020e (n = 51) (*) 540
857 #0x0000020f (n = 52) (*) 541
858 #0x00000210 (n = 53) (*) 542
859 #0x00000211 (n = 54) (*) 543
860 #0x00000212 (n = 55) (*) 544
861 #0x00000213 (n = 56) (*) 545
862 #0x00000214 (n = 57) (*) 546
863 #0x00000215 (n = 58) (*) 547
864 #0x00000216 (n = 59) (*) 548
865 #0x00000217 (n = 60) (*) 549
866 #0x00000218 (n = 61) (*) 550
867 #0x00000219 (n = 62) (*) 551
868 #0x0000021a (n = 63) (*) 552
869 #0x0000021b (n = 64) (*) 553
870 #0x0000021c (n = 65) (*) 554
871 #0x0000021d (n = 66) (*) 555
872 #0x0000021e (n = 67) (*) 556
873 #0x0000021f (n = 68) (*) 557
874 #0x00000220 (n = 69) (*) 558
875 #0x00000221 (n = 70) (*) 559
876 #0x00000222 (n = 71) (*) 560
877 #0x00000223 (n = 72) (*) 561
878 #0x00000224 (n = 73) (*) 562
879 #0x00000225 (n = 74) (*) 563
880 #0x00000226 (n = 75) (*) 564
881 #0x00000227 (n = 76) (*) 565
882 #0x00000228 (n = 77) (*) 566
883 #0x00000229 (n = 78) (*) 567
884 #0x0000022a (n = 79) (*) 568
885 #0x0000022b (n = 80) (*) 569
886 #0x0000022c (n = 81) (*) 570
887 #0x0000022d (n = 82) (*) 571
888 #0x0000022e (n = 83) (*) 572
889 #0x0000022f (n = 84) (*) 573
890 #0x00000230 (n = 85) (*) 574
891 #0x00000231 (n = 86) (*) 575
892 #0x00000232 (n = 87) (*) 576
893 #0x00000233 (n = 88) (*) 577
894 #0x00000234 (n = 89) (*) 578
895 #0x00000235 (n = 90) (*) 579
896 #0x00000236 (n = 91) (*) 580
897 #0x00000237 (n = 92) (*) 581
898 #0x00000238 (n = 93) (*) 582
899 #0x00000239 (n = 94) (*) 583
900 #0x0000023a (n = 95) (*) 584
901 #0x0000023b (n = 96) (*) 585
902 #0x0000023c (n = 97) (*) 586
903 #0x0000023d (n = 98) (*) 587
904 #0x0000023e (n = 99) (*) 588
905 #0x0000023f (n = 100) (*) 589
906 #0x00000240 (n = 101) (*) 590
907 #0x00000241 (n = 102) (*) 591
908 #0x00000242 (n = 103) (*) 592
909 #0x00000243 (n = 104) (*) 593
910 #0x00000244 (n = 105) (*) 594
911 #0x00000245 (n = 106) (*) 595
912 #0x00000246 (n = 107) (*) 596
913 #0x00000247 (n = 108) (*) 597
914 #0x00000248 (n = 109) (*) 598
915 #0x00000249 (n = 110) (*) 599
916 #0x0000024a (n = 111) (*) 600
917 #0x0000024b (n = 112) (*) 601
918 #0x0000024c (n = 113) (*) 602
919 #0x0000024d (n = 114) (*) 603
920 #0x0000024e (n = 115) (*) 604
921 #0x0000024f (n = 116) (*) 605
922 #0x00000250 (n = 117) (*) 606
923 #0x00000251 (n = 118) (*) 607
924 #0x00000252 (n = 119) (*) 608
925 #0x00000253 (n = 120) (*) 609
926 #0x00000254 (n = 121) (*) 610
927 #0x00000255 (n = 122) (*) 611
928 #0x00000256 (n = 123) (*) 612
929 #0x00000257 (n = 124) (*) 613
930 #0x00000258 (n = 125) (*) 614
931 #0x00000259 (n = 126) (*) 615
932 #0x0000025a (n = 127) (*) 616
933 #0x0000025b (n = 128) (*) 617
934 #0x0000025c (n = 129) (*) 618
935 #0x0000025d (n = 130) (*) 619
936 #0x0000025e (n = 131) (*) 620
937 #0x0000025f (n = 132) (*) 621
938 #0x00000260 (n = 133) (*) 622
939 #0x00000261 (n = 134) (*) 623
940 #0x00000262 (n = 135) (*) 624
941 #0x00000267 (n = 141) (*) 920
942 #0x00000264 (n = 1) (*) 921
943 #0x00000265 (n = 3) (*) 922
944 #0x00000266 (n = 1) (*) 923
945 #0x0000026f (n = 149) (*) 924
946 #0x00000268 (n = 1) (*) 925
947 #0x00000269 (n = 3) (*) 926
948 #0x0000026a (n = 1) (*) 927
949 #0x0000026b (n = 7) (*) 928
950 #0x0000026c (n = 1) (*) 929
951 #0x0000026d (n = 3) (*) 930
952 #0x0000026e (n = 1) (*) 931
954 ;; Iteration rebalance.
955 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200
956 (#<link root -> node #0x000002d5 101>)
957 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 920 921 922 923 924 925 926 927 928 929 930 931
958 (#<link root -> node #0x000003b5 598>)
960 ;; Path manoeuvre rebalance.
961 (#<link root -> node #0x000003de 1>)
962 (#<link root -> node #0x000004a6 200>)
963 (#<link root -> node #0x00000587 499>)
964 (#<link root -> node #0x0000062d 500> #<node #0x0000062d 500 left> -> (nil))
965 (#<link root -> node #0x0000073c 129>)
966 (#<link root -> node #0x000007c0 128> #<node #0x000007c0 128 right> -> (nil))
969 #<node #0x00000909 1>
970 (#<link root -> node #0x0000096b 99>)
971 (#<link root -> node #0x000009d1 1>)
973 ;; Removal rebalance.
974 (#<link root -> node #0x00000aa8 117> #<node #0x00000aa8 117 right> -> (nil))
977 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300
979 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300
982 XYLA-SPLAY UNISECT rebalance
983 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 910 911 912 913 914 915 916 917 918 919 920 921 922 923 924 925 926 927 928 929 930 931
984 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 920
985 XYLA-SPLAY DIFFSECT rebalance
986 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 119 120 480 481 482 483 484 485 486 487 488 489 910 911 912 913 914 915 916 917 918 919
987 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 920
989 ;;;----- That's all, folks -------------------------------------------------
~mdw / xyla / blob