Version: 5.1.1
4 Splay Trees
Splay trees are an efficient data structure for mutable dictionaries
with totally ordered keys. They were described in the paper
“Self-Adjusting Binary Search Trees” by Daniel Sleator and Robert
Tarjan in Journal of the ACM 32(3) pp652-686.
A splay-tree is a ordered dictionary (dict? and
ordered-dict?).
Makes a new empty splay-tree. The splay tree uses ord to
order keys; in addition, the domain contract of ord is
combined with key-contract to check keys.
Examples: |
| > (splay-tree-set! splay-tree "dot" 10) | > (splay-tree-set! splay-tree "cherry" 500) | > (dict-map splay-tree list) | '(("cherry" 500) ("dot" 10)) | > (splay-tree-ref splay-tree "dot") | 10 | > (splay-tree-remove! splay-tree "cherry") | > (splay-tree-count splay-tree) | 1 | > (splay-tree-set! splay-tree 'pear 3) | contract violation: expected <string?>, given: 'pear | contract on splay-tree-set! from | (file | /var/tmp/racket/collects/data/splay-tree.rkt) | blaming top-level | contract: | (->i | ((s splay-tree?) (key (s) ...) (v (s) ...)) | (_r void?)) | at: <collects>/data/splay-tree.rkt:1112.2 |
|
Makes a new empty splay-tree that permits only exact integers as keys
(in addition to any constraints imposed by
key-contract). The
resulting splay tree answers true to
adjustable-splay-tree?
and supports efficient key adjustment.
Returns #t if x is a splay-tree, #f otherwise.
Removes all keys in [from, to); that is, all keys
greater than or equal to from and less than to.
This operation takes O(N) time, or O(log N) time if
(adjustable-splay-tree? s).
This operation is only allowed on adjustable splay trees, and it takes
O(log N) time.
Increases the value of all keys greater than or equal to
from
by
(- to from).
This operation is only allowed on adjustable splay trees, and it takes
O(log N) time.
Returns #t if x represents a position in a
splay-tree, #f otherwise.
Returns an association list with the keys and values of s, in
order.