This library 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.
takes a given proper List of N elements and constructs a binary Tree
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
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.
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.
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.