A binary search tree contains a series of keys--in our case, numeric keys--and associated values. Each non-empty tree node has a key, a value, and left and right children that are also trees. The distinguishing feature of a binary search tree is that all the key values in the left child of any node are less than the key value of the node (while all key values in the right child are greater than the key values in the node). This ordering property allows for very efficient insertion, deletion, and lookup operations.

To represent the trees, we use an unevaluated function call of the form BINARYTREE(key, value, left, right). The empty tree, a special case of a tree, is represented as BINARYTREE( ). For example, the tree

                              2 f(x)
                                / \
                               /   \
                              /     \
                            1 e(x)  3 g(x)
is represented as

This is a form similar to the nested parenthesis used in LISP and other languages. Using function calls in this way is equivalent to records, except that our field names are referred to positionally as op(1,...) or op(2,...). By defining some simple utility procedures, we can regain this simple access, and we can also make the data structure more robust by adding error checking.

The advantages to using unevaluated function calls as opposed to records in this case are:

Unevaluated function calls are immutable, low-storage data structures;

Testing equality is a simple pointer comparison, which is fast, while using records would require comparing all the fields; and,

We can extend the pretty printer to display unevaluated function calls nicely.

To make the programming and use of binary trees easier, we define a constant emptytree for the empty tree. Because of our choice of data structure, all empty trees are equal to this object.

For now, define the leftchild and rightchild operations as:

Now we can simply refer to leftchild(tree) or rightchild(tree) without having to remember the operand numbers. More importantly, if we later decide to rearrange the order in which the various fields are stored, this need only change in this one place.

The Maple type procedure is used to test whether an object has a stated property. We must add a test for the property "is a binary tree?" We also want to be able to test whether a tree is empty. To define a new type, define a procedure or type expression `type/name`, where name is the name for the new type.

The following two definitions perform these tests:

So now we can ask questions such as:

For some applications, the definition of `type/binarytree` is too simplistic. In many cases, it does not suffice to check that an object is a binary tree; the type of the values in the tree are also required. In other words, we want to define a type binarytree(type) that checks whether an object is a binary tree with values of the correct type. The Maple structured types allow the specification of more complicated type tests. Structure arguments are passed as the second argument to a  `type/...` procedure, so implementing a structured type requires that we check the number of arguments passed to the procedure by using nargs, and then perform any extra type tests.

A structured form of the binarytree type can be implemented by using:

Note: When used as a structured type test, this procedure not only checks the top-level node, but also verifies all of its descendents. The type "binarytree(anything)" can be used to test the complete structure of the tree without testing the types of the node values.

Using this version of `type/binarytree`, we can use a much stronger test, such as:

We should upgrade our definitions of leftchild and rightchild to take advantage of these type tests. For now, we will restrict ourselves to updating the access procedures to check that their argument is a binary tree, although we could also replace the internal comparison to emptytree with a type test.

This section defines the insert, delete, and lookup operations on binary trees.

A short test session verifies that these routines perform the required operations:

While the previous test demonstrated that the binary tree code appears to be functioning, it also clearly demonstrated that the BINARYTREE structure is quite large and hard to read. Maple provides a print preprocessing stage that gives programmers limited control over the printing of their data structures.

When printing a function call f(x), Maple first looks for a procedure `print/f `. If Maple finds `print/f `, it passes the arguments of the function to the `print/...` procedure. The result of this call is printed, instead of the original structure. In this way, a programmer can define a different print form for any function call data structure.

We can define a more compact printing form for BINARYTREE objects by using nested lists and suppressing the printing of the empty tree.

The previous sections described a basic implementation of a binary tree, including extensions to the type system and printing. In this section, we turn this assortment of procedures into a Maple package.

A Maple package is a set of routines and data that is placed in a module with option package. Existing packages include LinearAlgebra, numapprox, and many others (For a complete list, see index/package.) The distinguishing feature of a package is that all the package procedures are local to the module and exported (although the with command allows access by short names). Because of this, the same procedure name can exist in multiple packages without name collisions.

(Note that, prior to the introduction of modules, packages were usually implemented as tables. Many existing packages are implemented as tables, but new packages should use modules.)

First you need to configure your Maple session to work with a private repository. While the directions vary from platform to platform, the following basic steps are needed.

 1. Create a directory or folder of any appropriate name. For this example, assume that the repository is called "bstlib".

 2. Use march to create a Maple repository in the chosen directory or folder. On DOS/Windows and UNIX, this is accomplished by using the march command, for example, march( 'create', "bstlib", 100 ).

 3. Add the directory or folder name to the start of the list of locations in the libname variable. In your Maple session, add the command libname := "bstlib", libname;.

The last step has to be repeated for every Maple session, so you may want to place it in your Maple initialization file. Note that in most of what follows, your private library is assumed to be at the start of libname.

To protect against unintentional changes to the main Maple library, you should ensure that it is marked as read-only.

To actually construct the package, you must write a module and assign it to the name chosen for the package. In this case, the name BinaryTree will be used for the package name.

The names of all the user-accessible routines are listed as exports of the module. You should also include  option package among the declarations for the module so that it can be distinguished from modules used for other purposes.

Since you will want to make your new types available to your users, you should install them when the package is read from the repository.  This can be done by writing an initialization routine and using it in the load = option of the module.  Here, the local routine setup is used to install the types for binarytree  and emptytree and the pretty printer extension `print/BINARYTREE`.

The complete source code for BinaryTree appears below.

To save this package to your private Maple repository, ensure that the directory in which it is stored appears first among the paths listed in the global variable libname.

After first ensuring that the standard Maple repository is not writable, uncomment the next execution group and execute it. (To uncomment the line, remove the # character.)

A short test of the loaded binary tree package shows that the package is still functioning. (These commands will produce errors unless you have built the BinaryTree package and included its directory in your libname, as described in the previous sections.

Note that if you have not placed the directory in your initialization file, a restart; will remove it from your libname.  To replace it, use:

Now that we have created the package, we must document the procedures and update the help browser with entries for the new procedures.

For the moment, assume that you have written five worksheets that document these routines: "lefttree.mws", "insert.mws", "delete.mws", "lookup.mws", and "binarytree.mws". The commands that follow will generate errors if these files do not exist. The first step is to read these files into a TEXT object in a Maple session. Create the following program to perform this function:

The TEXT object returned by this procedure can be inserted into the help database by using the INTERFACE_HELP commands. For our example package, the following commands are sufficient. Again, these commands will produce errors if you have not created the appropriate files.

You could also use the makehelp procedure or the GUI facilities to save these files into the help system.

As well as adding these pages to the help system, we must add an entry to the help browser for the top-level description.

Because the Maple help system uses caching, you might need to exit Maple and restart it before your new help pages become visible. Remember to reassign libname when you run Maple again.

This section provides some brief notes about distributing your package to other users. You may want to share your code for demonstrations, for use by colleagues or students, or for submission to the Maple Application Center.

You have two main options for distributing your package: source form and archive form.

In a source form distribution, you distribute flat files or worksheets that contain all of the executable procedures and data for the package. Each file or worksheet should include any savelib statements needed to store the package in a Maple repository. In addition, you should include any help worksheets and a flat file or worksheet containing any makehelp or INTERFACE_HELP commands needed to update the help system. This worksheet is itself an example of a source form distribution, because its execution installs the BinaryTree package. Source form distribution has the advantage, and disadvantage, of easily allowing the receiver of the package to modify it and upgrade it as required. The main disadvantage of a source form distribution is that the receiver must execute all the flat files or worksheets before the package is usable.

In an archive distribution, you distribute the contents of the Maple repository directory created after you have loaded all the executable procedures and help pages into the repository. The receiver of such a package need only place the files in a directory and add that directory to libname for it to be usable. While installation is easier, the receiver of such a package has a more difficult time updating the package than if they had received a source distribution.

An important point to remember is that the Maple archive files are binary files, and care must be taken to ensure that they are not corrupted during an archive distribution. Maple source files and worksheets consist of simple ASCII text, and so they can be properly e-mailed by most systems.

In both cases, it is a good idea to include a simple test worksheet that the receiver can use to check whether the package is correctly installed.

For more information, refer to the following help pages: type, Definition of a structured type in Maple, nargs, index/package, with, savelib, march, libname, macro, INTERFACE_HELP, makehelp.