Trees


  1. Viewing the algorithm

  2. Insert, find, and delete functions

  3. Restrictions and other issues

  4. HeapSort

Viewing the algorithm

After starting a tree algorithm, a tree such as the one above will appear (HeapSort is different and will be discussed later).  In the text field labeled "Messages Displayed Here," a description of each step of the algorithm is displayed.  To clearly view each step, the algorithm should either be run at a very slow speed or run in step mode.  In the next text field, the mode is displayed.  The algorithm can be in running, suspended, or step mode.  Note that once the initial set of insertions are done, the program may be in running mode, but nothing is happening.  The program is waiting for the user to run an insert, find, or delete.

Insert, find, and delete functions

The insert, find, and delete functions are located at the top of the frame.  They will not respond to the user until the program is done with the initial set of insertions.  After that, the user may enter a number in one of the text fields at the top and press the corresponding button to insert, find, or delete.  The button must be pressed in order to run the operation, pressing 'enter' does not do anything.  If the input is not legal, a message will appear telling the user to correct the input.  These operations must be run one at a time.  If the user tries to run one of these while another one is still running, a warning will be displayed to finish the other process first.

Restrictions and other issues

Although the user may do as many insertions as he or she wants, the tree will not insert nodes that would appear below the fifth level.  The tree is therefore effectively limited to 63 nodes.  The red-black tree may draw nodes in the sixth level because of a rotation.  For this reason the frame for red-black trees is a little larger.  The nodes at this level may be found and deleted, but other insertions at this level are not allowed.

HeapSort

HeapSort has some differences from the other tree algorithms.  It is not really a tree, it is an array.  It is included with the trees because that is how it is represented visually.  There is no find function for HeapSort.  This is because its nodes are not ordered the same way as in a binary search tree.  For HeapSort, the parent must be greater than or equal to the child.  Since the algorithm will not search for nodes, the delete function will always delete the maximum value in the heap.  The text field beside the delete maximum function is only for displaying messages to the user.  The user may not enter values in this field.  To delete the maximum value, simply press the button and start the algorithm.