10.49 Dense Arrays as Binary Trees—library(trees)

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.

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.