YAP 7.1.0
Updatable Binary Trees

The following queue manipulation routines are available once included with the `use_module(library(trees))` command. More...

## Detailed Description

The following queue manipulation routines are available once included with the `use_module(library(trees))` command.

These are the routines I meant to describe in DAI-WP-150, but the wrong version went in We have

• list_to_tree : O(N)
• tree_to_list : O(N)
• tree_size : O(N)
• map_tree : O(N)
• get_label : O(lg N)
• put_label : O(lg N) where N is the number of elements in the tree The way get_label and put_label work is worth noting: they build up a pattern which is matched against the whole tree when the position number finally reaches 1 In effect they start out from the desired node and build up a path to the root They still cost O(lg N) time rather than O(N) because the patterns contain O(lg N) distinct variables, with no duplications put_label simultaneously builds up a pattern to match the old tree and a pattern to match the new tree

## ◆ get_label/3

 class get_label/3

get_label(+ Index, + Tree, ? Label)

Treats the tree as an array of N elements and returns the Index-th

## ◆ list_to_tree/2

 class list_to_tree/2

list_to_tree(+ List, - Tree)

Takes a given List of N elements and constructs a binary Tree

## ◆ map_tree/3

 class map_tree/3

map_tree(+ Pred, + OldTree, - NewTree)

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

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 In fact this routine is perfectly happy constructing either tree given the other, I have given it the mode I have for that bogus reason "efficiency" and because it is normally used this way round This is really meant more as an illustration of how to map over trees than as a tool for everyday use

## ◆ put_label/4

 class put_label/4

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

It 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 Arrays.Pl, 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

## ◆ tree_size/2

 class tree_size/2

tree_size(+ Tree, - Size)

Calculates the number of elements in the Tree

All trees made by list_to_tree that are the same size have the same shape

## ◆ tree_to_list/2

 class tree_to_list/2

tree_to_list(+ Tree, - List)

Is the converse operation to list_to_tree 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