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


Class Documentation

◆ 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