> For the complete documentation index, see [llms.txt](https://www.lisppad.app/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://www.lisppad.app/libraries/lispkit/lispkit-wt-tree.md).
# (lispkit wt-tree)
Library `(lispkit wt-tree)` implements *weight-balanced binary trees*, a persistent, ordered key/value data structure. A `wt-tree` maps keys to values (like a hash table), but, unlike a hash table, keeps its entries ordered according to a user-supplied ordering predicate on the keys and provides efficient positional (rank-based) access, range splitting, and set-theoretic operations (union, intersection, difference, subset test) on the key sets of two trees. The implementation is an enhanced and bug-corrected variant of Stephen Adams' weight-balanced trees, following Yoichi Hirai and Kazuhiko Yamamoto, ["Balancing weight-balanced trees"](https://yoichihirai.com/bst.pdf), Journal of Functional Programming, 21(3):287-307, 2011.
WT-trees are persistent: operations such as `wt-tree/add` or `wt-tree/delete` return a new tree and leave the argument tree unchanged, sharing structure with it. For performance-sensitive code, destructive counterparts (`wt-tree/add!`, `wt-tree/delete!`, `wt-tree/delete-min!`) are also provided, mutating a tree in place.
## Tree types
Every `wt-tree` is created with respect to a *tree type*, an object that bundles the strict ordering predicate (`key
Returns a new tree type whose keys are ordered by the strict ordering predicate *key\
Returns a new tree type whose keys are ordered according to the ordering predicate of comparator *comp* (see `comparator-ordering-predicate` of library `(lispkit comparator)`).
**(wt-tree-type? *****obj*****)** 
Returns `#t` if *obj* is a tree type (as created by `make-wt-tree-type`, `make-comparator-wt-tree-type`, or one of the predefined tree types below), `#f` otherwise.
**wt-tree-type-tag** 
Symbol representing the `wt-tree-type` type. The `type-of` procedure of library `(lispkit type)` returns a list starting with this symbol for tree type objects (not for `wt-tree` instances themselves; use `wt-tree-type?` respectively `wt-tree?` to distinguish the two).
**number-wt-type**
Predefined tree type ordering keys via `<`, i.e. for using real numbers as keys.
**string-wt-type**
Predefined tree type ordering keys via `string
Predefined tree type ordering keys via `string-ci
Predefined tree type ordering keys via `char
Predefined tree type ordering keys via `char-ci\
**(make-wt-tree *****type*****)**
Returns a new, empty `wt-tree` of tree type *type*. The default for *type* is `number-wt-type`.
**(singleton-wt-tree *****key value*****)** \
**(singleton-wt-tree *****type key value*****)**
Returns a new `wt-tree` of tree type *type* containing a single entry mapping *key* to *value*. The default for *type* is `number-wt-type`.
**(alist->wt-tree *****type alist*****)**
Returns a new `wt-tree` of tree type *type*, populated with the `(key . value)` associations of association list *alist*. If *alist* contains several entries for the same key, the entry that appears later in *alist* takes precedence.
```scheme
(define t
(alist->wt-tree
number-wt-type
'((3 . "c") (1 . "a") (2 . "b"))))
```
**(wt-tree? *****obj*****)**
Returns `#t` if *obj* is a `wt-tree`, `#f` otherwise.
**(wt-tree/copy *****tree*****)**
Returns a new `wt-tree` with the same tree type, keys, and values as *tree*. Since wt-trees are persistent, `wt-tree/copy` is a cheap, O(1) operation; the copy initially shares its internal representation with *tree*, but the two trees evolve independently from each other, in particular with respect to the destructive operations `wt-tree/add!`, `wt-tree/delete!`, and `wt-tree/delete-min!`.
**(wt-tree/valid? *****tree*****)**
Returns `#t` if `wt-tree` *tree* satisfies the weight-balance and ordering invariants of the underlying tree implementation, `#f` otherwise. Since these invariants are maintained automatically by all `wt-tree` operations, this predicate is primarily useful for testing and debugging purposes.
## Basic operations
**(wt-tree/empty? *****tree*****)**
Returns `#t` if `wt-tree` *tree* contains no entries, `#f` otherwise.
**(wt-tree/size *****tree*****)**
Returns the number of entries in `wt-tree` *tree*.
**(wt-tree/add *****tree key value*****)**
Returns a new `wt-tree`, like *tree* but with *key* mapped to *value*. If *key* is already present in *tree*, its associated value is replaced; *tree* itself remains unchanged.
**(wt-tree/add! *****tree key value*****)**
Destructively adds an entry mapping *key* to *value* to `wt-tree` *tree*, replacing any value that *key* was previously mapped to. Returns an unspecified result.
**(wt-tree/delete *****tree key*****)**
Returns a new `wt-tree`, like *tree* but with any entry for *key* removed. If *key* is not present in *tree*, a copy of *tree* is returned. *tree* itself remains unchanged.
**(wt-tree/delete! *****tree key*****)**
Destructively removes the entry for *key*, if any, from `wt-tree` *tree*. Returns an unspecified result.
**(wt-tree/member? *****key tree*****)**
Returns `#t` if `wt-tree` *tree* contains an entry for *key*, `#f` otherwise. Note that, unlike most other procedures of this library, `wt-tree/member?` expects *key* as its first and *tree* as its second argument.
**(wt-tree/lookup *****tree key default*****)**
Returns the value associated with *key* in `wt-tree` *tree*, or *default* if *tree* does not contain an entry for *key*.
```scheme
(define t (singleton-wt-tree 2 "b"))
(wt-tree/lookup t 2 #f) ⇒ "b"
(wt-tree/lookup t 9 #f) ⇒ #f
(wt-tree/lookup t 1 'none) ⇒ none
```
## Ordered and positional access
Since the entries of a `wt-tree` are kept in key order, they can also be accessed by their zero-based position (*rank*) in this order, from the smallest key (position `0`) to the largest key (position `(- (wt-tree/size tree) 1)`).
**(wt-tree/index *****tree index*****)**
Returns the key at position *index* of `wt-tree` *tree*, in ascending key order. Signals an error if *index* is not in the range `[0, (wt-tree/size tree))`.
**(wt-tree/index-datum *****tree index*****)**
Like `wt-tree/index`, but returns the value associated with the key at position *index* instead of the key itself.
**(wt-tree/index-pair *****tree index*****)**
Like `wt-tree/index`, but returns a pair `(key . value)` for the entry at position *index*.
**(wt-tree/rank *****tree key*****)**
Returns the zero-based position of *key* within `wt-tree` *tree* in ascending key order, or `#f` if *tree* does not contain an entry for *key*. `wt-tree/rank` is the inverse operation of `wt-tree/index`.
**(wt-tree/min *****tree*****)**
Returns the smallest key of `wt-tree` *tree*. Signals an error if *tree* is empty.
**(wt-tree/min-datum *****tree*****)**
Returns the value associated with the smallest key of `wt-tree` *tree*. Signals an error if *tree* is empty.
**(wt-tree/min-pair *****tree*****)**
Returns a pair `(key . value)` for the entry with the smallest key of `wt-tree` *tree*. Signals an error if *tree* is empty.
**(wt-tree/delete-min *****tree*****)**
Returns a new `wt-tree`, like *tree* but with the entry for the smallest key removed. *tree* itself remains unchanged. Signals an error if *tree* is empty.
**(wt-tree/delete-min! *****tree*****)**
Destructively removes the entry for the smallest key from `wt-tree` *tree*. Returns an unspecified result. Signals an error if *tree* is empty.
## Splitting trees
**(wt-tree/split< *****tree key*****)**
Returns a new `wt-tree` containing all entries of *tree* whose key is strictly less than *key* (the entry for *key* itself, if present, is excluded).
**(wt-tree/split> *****tree key*****)**
Returns a new `wt-tree` containing all entries of *tree* whose key is strictly greater than *key* (the entry for *key* itself, if present, is excluded).
## Set-like operations
The following procedures combine two wt-trees based on their key sets. *tree1* and *tree2* must have been created with the same tree type object (e.g. both via `number-wt-type`, or both via the same tree type returned from `make-wt-tree-type`); otherwise, an error is signalled.
**(wt-tree/union *****tree1 tree2*****)**
Returns a new `wt-tree` containing all entries whose key is in *tree1* or *tree2* (or both). For a key present in both trees, the value from *tree2* is used.
**(wt-tree/union-merge *****tree1 tree2 merge*****)**
Like `wt-tree/union`, but for a key present in both trees, the associated value is computed by calling *merge* with three arguments: the key, the value associated with the key in *tree2*, and the value associated with the key in *tree1*.
```scheme
(define t1 (alist->wt-tree number-wt-type '((1 . "a1") (2 . "b1"))))
(define t2 (alist->wt-tree number-wt-type '((2 . "b2") (3 . "c2"))))
(wt-tree/fold
(lambda (k v acc) (cons (cons k v) acc))
'()
(wt-tree/union-merge t1 t2
(lambda (key v2 v1) (string-append v1 "+" v2))))
⇒ ((1 . "a1") (2 . "b1+b2") (3 . "c2"))
```
**(wt-tree/intersection *****tree1 tree2*****)**
Returns a new `wt-tree` containing all entries whose key is present in both *tree1* and *tree2*. For each such key, the value from *tree2* is used.
**(wt-tree/difference *****tree1 tree2*****)**
Returns a new `wt-tree` containing all entries of *tree1* whose key is not present in *tree2*.
**(wt-tree/subset? *****tree1 tree2*****)**
Returns `#t` if the set of keys of *tree1* is a subset of the set of keys of *tree2*, `#f` otherwise. Only key membership is compared; associated values are not taken into account.
**(wt-tree/set-equal? *****tree1 tree2*****)**
Returns `#t` if *tree1* and *tree2* have the same set of keys, `#f` otherwise. Just like `wt-tree/subset?`, only keys are compared, not values. `wt-tree/set-equal?` is implemented like this:
```scheme
(define (wt-tree/set-equal? tree1 tree2)
(and (wt-tree/subset? tree1 tree2)
(wt-tree/subset? tree2 tree1)))
```
## Traversal
**(wt-tree/fold *****combiner init tree*****)**
Combines all entries of `wt-tree` *tree*, in ascending key order, with combining function *combiner*, using *init* as the value for the smallest entry not yet part of the combined result. *combiner* is a procedure of three arguments, a key, its associated value, and the so-far accumulated result; it returns a new accumulated result. `wt-tree/fold` corresponds to a right fold over the ascending sequence of entries, i.e. it computes
```scheme
(combiner k₁ v₁ (combiner k₂ v₂ (... (combiner kₙ vₙ init) ...)))
```
for a tree with entries `k₁ < k₂ < ... < kₙ`. For instance, `wt-tree/fold` can be used to convert a `wt-tree` into a sorted association list:
```scheme
(wt-tree/fold (lambda (key value alist) (cons (cons key value) alist)) '() t)
```
**(wt-tree/for-each *****proc tree*****)**
Invokes *proc* once for every entry of `wt-tree` *tree*, in ascending key order, passing the key and the associated value as two arguments. The result of `wt-tree/for-each` is unspecified.