Programming Praxis

We wrote a basic library of AVL tree functions in the previous exercise. In today’s exercise we will extend the library with the following functions:

size – Return the number of items in an input tree.

nth – Return the nth item in an input tree, or an error if n is out of range.

rank – Return the ordinal position of a key in an input tree, or an error if the key is not present in the tree.

map – Return a tree with all of the values in an input tree replaced by the results of an input function that takes an existing key and value; the keys of the tree are unchanged.

fold – Return a single value obtained by evaluating a given procedure at each node of the tree, in order. The procedure takes three parameters: the current key, the associated value, and a base value that accumulates the results of previous evaluations of the procedure. Returns the accumulated value after all nodes of the tree have been considered.

for-each – Evaluate a given procedure at each node of the tree, in order. The procedure takes two parameters: the current key and the associated value. Returns nothing; the procedure is evaluated only for its side effects.

to-tree – Return a tree containing the key/value pairs of an input list.

Your task is to add the functions described above to the AVL tree library of the previous exercise. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2