### Completing the BinarySearchTreeArray

Added on - 13 Sep 2019

13

pages

2940

words

124

views

0

downloads

Completing and Experimenting with theBinarySearchTreeArray<E> classNote that this coursework should be completedindividually. Unlike part A, there is relatively littleprogramming in this assignment and the main task is totest and reflect on the relative performance of three Setclasses. Please read this project specification carefullybefore starting the work.It is intended to contribute to the assessment of thefollowing three learning outcomes:L2. Design and develop implementations of collectionclasses, applying the principles of object-orientedprogramming and conforming to the relevantconventions, standards and accepted best practice in theprogramming language used.L3. Identify and implement algorithms, using recursionwhere appropriate, for a variety of technically demandingtasks including explorations of graphs and search spacesto find and/or arrive at a destination or goal state.L4. Recognise the implications for type safety and theguaranteeing of object invariants that arise when tryingto meet requirements for persistence, and in designingclasses for serialization and de- serialization take fullaccount of these.Completing the BinarySearchTreeArray<E> classYou will have received detailed feedback on yoursubmission for part A. It is recommended that you gothrough the comments you have received and thepublished solution and make any corrections to your

BinarySearchTreeArray<E>class that are necessary toaddress the points raised. At the end of this process youshould have a fully functional implementation of theclass, based on what you submitted for part A, that youcan use as the basis for part B of the coursework but, ifnot, you may use the published solution for theBinarySearchTreeArray<E>class as the basis for thisproject.Some Experiments with BSTsThis part of the coursework involves conducting someexperiments on binary search trees using theBinarySearchTreeArray<E>class that was the subjectof part A of the project.COMP09044 Cswk part B Page 1 Version 2.5The Structure of the TreesThebinary tree theoremrelates the number of elementsin a binary tree to the number of leaves in the tree and tothe height of the tree. The theorem states theserelationships 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 isfull then (n(t) + 1)/2.0 equals 2height(t).For sets implemented using theBinarySearchTreeArray<E>class and the red-black treeof thejava.util.TreeSet<E>class, you willexplore how the number of elements in each set relatesto the height of the tree, and for theBinarySearchTreeArray<E>class you will also explore

how the number of leaves in the tree relates to thenumber of elements, in both cases using treesconstructed with sequences of randomly generatedpositive integer values.TreeSet<E>does not define a method to return theheight of its tree. This can be inferred, however, from thenumber of comparisons required to find the element thatis most distant from the root, and this same approach canbe used to find the height of an instance of theBinarySearchTreeArray<E>class. Here is a method,using anItemclass that counts comparisons (discussedlater in this project specification), that returns the heightof a binary search tree:private static longheight (Set<Item> tree) {longmaxComp = 0;for(Item current : tree) { Item.resetCompCount();tree.contains(current);if(maxComp <Item.getCompCount()) {maxComp = Item.getCompCount(); }}returnmaxComp-1; }For theBinarySearchTreeArray<E> class to determinethe number of leaves you can add the following methodto yourEntry<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 booleanisLeaf() {returnleft == NIL && right== NIL;}and the following methods to theBinarySearchTreeArray<E>class:private intcountLeaves(intnodeIndex) {if(nodeIndex== NIL)return0; Entry<E> node = tree[nodeIndex];if(node.isLeaf())return1;intcount = countLeaves(node.left); count +=countLeaves(node.right);returncount;}protected intleaves() {returncountLeaves(root); }Note that thecountLeaves()method above isrecursive. You may prefer to use an iterativeimplementation. In your report of the work, discusshow it, and any recursive methods in the originalBinarySearchTree<E>class, could be implementediteratively, and whether for any of these methodsyou did, in the final version of theBinarySearchTreeArray<E>class for this assignment,adopt an iterative or recursive implementation ofthe methods.The Performance of three Set classes in SearchesYou will also investigate the number of comparisonsnecessary to search for items in such trees and contrastthese with each other and with the comparisons required

**You’re reading a preview**

To View Complete Document

Become a Desklib Library Member.

Subscribe to our plans