Completing the BinarySearchTreeArray
13 Pages2940 Words283 Views
Added on 2019-09-13
Completing the BinarySearchTreeArray
Added on 2019-09-13
ShareRelated Documents
Completing and Experimenting with the BinarySearchTreeArray<E> class Note that this coursework should be completed individually. Unlike part A, there is relatively little programming in this assignment and the main task is to test and reflect on the relative performance of three Set classes. Please read this project specification carefully before starting the work. It is intended to contribute to the assessment of the following three learning outcomes: L2. Design and develop implementations of collection classes, applying the principles of object-oriented programming and conforming to the relevant conventions, standards and accepted best practice in the programming language used. L3. Identify and implement algorithms, using recursion where appropriate, for a variety of technically demandingtasks including explorations of graphs and search spaces to find and/or arrive at a destination or goal state. L4. Recognise the implications for type safety and the guaranteeing of object invariants that arise when trying to meet requirements for persistence, and in designing classes for serialization and de- serialization take full account of these. Completing the BinarySearchTreeArray<E> class You will have received detailed feedback on your submission for part A. It is recommended that you go through the comments you have received and the published solution and make any corrections to your
BinarySearchTreeArray<E> class that are necessary to address the points raised. At the end of this process you should have a fully functional implementation of the class, based on what you submitted for part A, that you can use as the basis for part B of the coursework but, if not, you may use the published solution for the BinarySearchTreeArray<E> class as the basis for this project. Some Experiments with BSTs This part of the coursework involves conducting some experiments on binary search trees using the BinarySearchTreeArray<E> class that was the subject of part A of the project. COMP09044 Cswk part B Page 1 Version 2.5 The Structure of the Trees The binary tree theorem relates the number of elements in a binary tree to the number of leaves in the tree and tothe height of the tree. The theorem states these relationships to be: leaves(t) <= (n(t) + 1)/2.0 <= 2height(t) If t is a two-tree then leaves(t) equals (n(t) + 1)/2.0, if t is full then (n(t) + 1)/2.0 equals 2height(t). For sets implemented using the BinarySearchTreeArray<E> class and the red-black treeof the java.util.TreeSet<E> class, you will explore how the number of elements in each set relates to the height of the tree, and for the BinarySearchTreeArray<E> class you will also explore
how the number of leaves in the tree relates to the number of elements, in both cases using trees constructed with sequences of randomly generated positive integer values. TreeSet<E> does not define a method to return the height of its tree. This can be inferred, however, from the number of comparisons required to find the element that is most distant from the root, and this same approach canbe used to find the height of an instance of the BinarySearchTreeArray<E> class. Here is a method, using an Item class that counts comparisons (discussed later in this project specification), that returns the height of a binary search tree: private static long height (Set<Item> tree) { long maxComp = 0; for (Item current : tree) { Item.resetCompCount(); tree.contains(current);if (maxComp < Item.getCompCount()) { maxComp = Item.getCompCount(); } } return maxComp-1; } For the BinarySearchTreeArray<E> class to determine the number of leaves you can add the following method to your Entry<E> class (this assumes you have declared a constant, equal to -1, to represent a “null reference” – here this has been calledNIL): COMP09044 Cswk part B Page 2 Version 2.5
public boolean isLeaf() {return left == NIL && right == NIL; }and the following methods to the BinarySearchTreeArray<E> class: private int countLeaves(int nodeIndex) { if (nodeIndex == NIL) return 0; Entry<E> node = tree[nodeIndex];if (node.isLeaf()) return 1; int count = countLeaves(node.left); count += countLeaves(node.right); return count; } protected int leaves() { return countLeaves(root); } Note that the countLeaves() method above is recursive. You may prefer to use an iterative implementation. In your report of the work, discusshow it, and any recursive methods in the original BinarySearchTree<E> class, could be implemented iteratively, and whether for any of these methods you did, in the final version of the BinarySearchTreeArray<E> class for this assignment, adopt an iterative or recursive implementation of the methods. The Performance of three Set classes in Searches You will also investigate the number of comparisons necessary to search for items in such trees and contrast these with each other and with the comparisons required
End of preview
Want to access all the pages? Upload your documents or become a member.
Related Documents
CS193P IPHONE APPLICATION DEVELOPMENTlg...
|7
|1737
|170
CS193P IPHONE APPLICATION DEVELOPMENTlg...
|7
|1737
|58
CS193P IPHONE APPLICATION DEVELOPMENTlg...
|7
|1737
|381
CS193P IPHONE APPLICATION DEVELOPMENTlg...
|7
|1737
|403
CS193P IPHONE APPLICATION DEVELOPMENTlg...
|7
|1737
|136
CS193P IPHONE APPLICATION DEVELOPMENTlg...
|7
|1737
|309