Extending the Binary Tree Class

Purpose

Prerequisites

Understanding of sections 13.1 through 13.4 of Algorithms and Data Structures: The Science of Computing.

Understanding of asymptotic notation, as described in section 9.2 of Algorithms and Data Structures: The Science of Computing.

Background

Binary trees are defined in sections 13.1 and 13.2 of Algorithms and Data Structures: The Science of Computing. Ordered binary trees are defined in section 13.3. The notion of a “fully balanced” tree is defined in section 13.3.5.

Algorithms and Data Structures: The Science of Computing describes a class that represents ordered binary trees. A complete implementation of this class is available, in a file named OrderedTree.java. The “Final Details” section of this document explains where to find this file.

Any Java source file that uses the OrderedTree class should “import” it via a statement of the form

    import geneseo.cs.sc.OrderedTree;

Subclasses of OrderedTree are subtle in several ways. These subtleties generally parallel those of recursive lists, discussed in section 11.5.1 of Algorithms and Data Structures: The Science of Computing. For this lab, pay particular attention to the makeNewTree method, and to the need for casts when using the getLeft and getRight messages to extract subtrees that will receive recursive messages.

Exercise

Design and analyze a subclass of OrderedTree that includes the methods described below. Specifically, do the following for each method:

• Develop an algorithm for the method
• Prove the algorithm correct
• Derive the worst-case asymptotic execution time of the algorithm, as a function of tree size (i.e., the number of elements in the tree).

Finally, write in Java a subclass of OrderedTree that includes all of the methods. Write a main program that tests this subclass (trees of strings are good things to test the subclass with, since strings are objects that are easy to create and that can be stored in ordered trees).

The Size of a Tree

Design a method that counts the elements in a binary tree. Specifically, the method takes no parameters, and returns an integer equal to the number of elements in the tree.

Find the Largest Element

Design a method that returns the largest element in an ordered binary tree. This method has no parameters, and returns a Comparable object.

Do two analyses of worst-case execution time for this algorithm: One analysis that assumes that the tree is fully balanced, and one that allows the tree to be arbitrarily imbalanced.

Final Details

Finding the OrderedTree Class

File OrderedTree.java can be Downloaded from the World Wide Web.

Documentation for the OrderedTree class is also available on the Web. The main documentation page is an index to documentation for all the Java classes written for use with Algorithms and Data Structures: The Science of Computing. To see the documentation for a specific class, click on that class’s name in the left-hand panel of the page.

Submitting Your Work

This lab is due on Tuesday, November 30. Turn in a printout of the code you write, and the correctness proofs and execution time derivations for each method. The proofs and derivations may be comments in your code, or they may be on a separate sheet of paper.

In addition to your code, proofs, and derivations, turn in a short paragraph discussing the extent to which concepts you learned about lists also apply to binary trees. You might discuss either or both of …

• Abstract lists and trees as collections, and the extent to which features of one as a collection seem to generalize to the other, or
• Similarities between our List and OrderedTree classes that allow programming skills learned in connection with one to be applied to the other

or other observations you have about the similarities (or lack thereof) between the two data structures.

Portions copyright © 2004. Charles River Media. All rights reserved.

Revised Nov. 18, 2004