In this module, we learned that a Binary Search Tree (BST) must remain balanced in order to guarantee O(log2 n) operations. This assignment asks you to use and modify a Binary Search Tree implementation in order to determine whether the tree is balanced.
In completing this assignment, you will:
• Apply what you have learned about how Binary Search Trees represent and store data
• Implement tree traversal algorithms for determining the structure of a tree
• Modify an existing Binary Search Tree implementation
Start by downloading BinarySearchTree.java, which implements a BST similar to the one we saw in this module, using Java generics.
The implementation that we have provided constitutes an ordered set of values. Since uniqueness of values is maintained by calling each value’s compareTo method, the implementation will reject any attempt at adding a null value to the set.
Implement the following speciﬁcations in BinarySearchTree.java. Do not change the signatures of these ﬁve methods, and do not create any additional .java ﬁles for your solution. You may add to the BinarySearchTree class and the inner Node class if desired, but if you need additional classes,deﬁne them in BinarySearchTree.java. Also, ensure your BinarySearchTree class is in the default package, i.e. that there is no “package” declaration at the top of the source code.
Given a value that is stored in this BST, this method returns the corresponding Node that holds it, or null if the value is null or does not exist in this BST.
Given a value, this method returns the depth of its Node, or 1 if the value is null or does not exist in this BST. The depth is deﬁned as the number of edges from that node to the root.
The depth of the root is 0, and its immediate children (if any) would have a depth of 1.
static int height(BinarySearchTree<?>.Node)
For the subtree rooted at the given Node, this method returns the height of the subtree. The height of a subtree is deﬁned as the maximum number of edges between the root of the subtree and any descendant leaf. The height of a leaf is 0. The height of an empty subtree, represented as a null Node, is deﬁned to be 1.
static boolean isBalancedNode(BinarySearchTree<?>.Node)
Given null, returns true. Given an instance of Node, returns true only if the absolute value of the diﬀerence in heights of its left and right children is less than 2.
This method returns true only if isBalancedNode(n) returns true for all Nodes n in this BST.
This assignment is scored out of a total of 71 points.
The ﬁndNode method is worth a total of 14 points, based on whether it returns the correct Node and handles errors.
The depth method is worth a total of 13 points, based on whether it correctly calculates the height of the node and handles errors.
The height method is worth a total of 9 points, based on whether it correctly calculates the height of the node and handles errors.
The isBalancedNode method is worth a total of 17 points, based on whether it correctly determines whether the node’s subtrees are balanced and correctly handles errors.
The isBalanced method is worth a total of 18 points, based on whether it correctly determines whether the tree is balanced.
本网站支持淘宝 支付宝 微信支付 paypal等等交易。如果不放心可以用淘宝交易！
E-mail: email@example.com 微信:itcsdx