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