10.27 Updatable Binary Trees—
This libary module provides updatable binary trees with logarithmic access time.
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.
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 List of N elements and constructs a binary Tree
) <=> Lab is the Kth element of List.
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.
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.
- 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.
Send feedback on this subject.