HOMEWORK PROBLEM 2_6         INTRODUCTION TO Ada II   586.2

PURPOSE:      To learn about access types
              Binary trees are used because they rather naturally
              dictate the use of access types.

END RESULT:   A complete Ada program that is a main procedure
              that WITH's a package containing the binary tree
              manipulation routines INSERT,FIND,DELETE and OUTPUT.
              Use OUTPUT as a debugging aid as each feature is added.

PROBLEM:      Use the attached samples as a guide to write a package
              that has binary tree manipulation routines. You must
              add a procedure DELETE that takes a name and deletes
              the names node from the tree. You can build the same
              tree. To show that the cases work delete ( in order )
              "E " , "B " , and "D " . Make provision for doing
              nothing to the tree if the name is not in the tree.
              Output the tree after every delete.
              Note: The next problem is to write a telephone information
              program. The program builds a file from name,phone pairs
              in tree structure form. ( data could come in random name
              order to allow for updating on line ). Then the program 
              will be run interactively, giving a name and getting a
              phone number back. With an auto dialer, you could
              type in a name and automatically phone the person
              or computer. A la superhacker.

TURN IN:      Printout of compilation of main procedure and
              package ( with no errors!)
              Printout of execution for built in test data.

OBSERVE:      These tree manipulation routines are messy if recursive
              procedures and functions are not used. These happen
              to be in the class of "simple" recursive routines that
              can be thoroughly tested to be sure they terminate.

READING :     MIL-STD-1815A 3.8 plus use the index for all
                                references to "access"
              Barnes   11.3

EXTRA :       For extra credit make the INSERT and DELETE work
              to maintain a balanced binary tree. This uses the
              balance factor  BF. The INSERT is not too difficult
              but the DELETE is a bear! It turns out that just plain
              binary trees are very inefficient. But, balanced binary
              trees are very efficient. If the tree is maintained
              in balanced form at most  log2 N searches are needed
              for an INSERT, FIND or DELETE. On a Baltimore phone
              book N is a large number! An unbalanced tree could be
              the worse possible structure if the names were entered
              alphabetically. Zzepth could be all day checking his
              phone number.