More precisely, your class should have public methods insert(Comparable), delete(Comparable), and traverse() that respectively add the given element to the tree, remove the given element from the tree, and traverse the tree in inorder by printing the data values (all on the same line). It should also have methods getCounter() and resetCounter() that return and reset to zero the current count of element comparisons. Finally, it should have a public method deleteSymmetric(Comparable), as described below.

You may define any other additional classes and methods (including constructors) that you find helpful. It is recommended that you use a BinaryNode class along the lines of the Weiss text. In general, you may use the Weiss text for guidance if you give proper credit. Note that the coding standards for this section of CS 146 discourage (1) public instance variables, (2) unrestricted public mutators, and (3) the use of default protection for classes. Also note the differences described below between what your code should do and the Weiss implementation.

The deleteSymmetric(Comparable) method should alternately replace keys to be deleted by their inorder predecessor and their inorder successor, in cases where the key has two children. The first such deletion should be from the right subtree. The delete method should always delete the inorder successor. Both delete and deleteSymmetric should return a boolean value of true when a deletion succeeds and false when the item to be deleted is not in the tree. Both of these methods, as well as traverse, should print an error message if they are passed to an empty tree.

The insert method should return true if the item to be inserted was not in the tree, and false if it was. In the latter case, it should not perform the duplicate insertion.

For full credit, you should use message passing in any auxiliary methods, rather than passing nodes or trees as arguments as in the BinaryNode methods of Weiss's Figure 4.17. There will be a small penalty if you use Weiss's strategy.

When performing and counting element comparisons, you should avoid comparing the same two elements more than once, as, for example, the Weiss text does in Figure 4.18. In any case, you might want to compare your counts of comparisons with the theoretical average-case values.