`library(trees)`

This libary module provides updatable binary trees with logarithmic access time. Exported predicates:

`gen_label(`

`?Index`,`+Tree`,`?Value`)-
assumes that Tree is a proper binary tree, and is true when

`Value`is the`Index-th`element in`Tree`. Can be used to enumerate all`Values`by ascending`Index`. `get_label(`

`+Index`,`+Tree`,`-Label`)-
treats the tree as an array of

`N`elements and returns the`Index-th`. If`Index < 1`or`> N`it simply fails, there is no such element. As Tree need not be fully instantiated, and is potentially unbounded, we cannot enumerate`Indices`. `list_to_tree(`

`+List`,`-Tree`)-
takes a given proper

`List`of`N`elements and constructs a binary`Tree`where`get_label(`

<=>`K`,`Tree`,`Lab`)`Lab`is the`Kth`element of`List`. `map_tree(`

`:Pred`,`+OldTree`,`?NewTree`)-
is true when

`OldTree`and`NewTree`are binary trees of the same shape and`Pred(Old,New)`is true for corresponding elements of the two trees. `put_label(`

`+Index`,`+OldTree`,`-Label`,`-NewTree`)-
constructs a new tree the same shape as the old which moreover has the same elements except that the

`Index-th`one is`Label`. Unlike the "arrays" of`library(arrays)`

,`OldTree`is not modified and you can hang on to it as long as you please. Note that`O(lg N)`new space is needed. `put_label(`

`+Index`,`+OldTree`,`-OldLabel`,`-NewTree`,`+NewLabel`)is true when

`OldTree`and`NewTree`are trees of the same shape having the same elements except that the`Index-th`element of`OldTree`is`OldLabel`and the`Index-th`element of`NewTree`is`NewLabel`. You can swap the`<Tree,Label>`argument pairs if you like, it makes no difference.`tree_size(`

`+Tree`,`-Size`)-
calculates the number of elements in the

`Tree`. All trees made by`list_to_tree/2`

that are the same size have the same shape. `tree_to_list(`

`+Tree`,`-List`)-
is the converse operation to

`list_to_tree/2`

. Any mapping or checking operation can be done by converting the tree to a list, mapping or checking the list, and converting the result, if any, back to a tree. It is also easier for a human to read a list than a tree, as the order in the tree goes all over the place.

Send feedback on this subject.