Updatable Binary Trees¶

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.

• tree_to_list/3

• tree_size/3
• put_label/5
• map_tree/4
• list_to_tree/3
• prolog::tree_to_list/2
• prolog::tree_size/2
• prolog::put_label/4
• prolog::map_tree/3
• prolog::list_to_tree/2
• prolog::get_label/3