2023年11月25日

Java代写 | CIT 594 Module 6 Programming Assignment Binary Search Trees

本次代写是一个二叉搜索树相关assignment的java代写

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.

Learning Objectives

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

Getting Started

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.

Activity

Implement the following specifications in BinarySearchTree.java. Do not change the signatures of these five methods, and do not create any additional .java files for your solution. You may add to the BinarySearchTree class and the inner Node class if desired, but if you need additional classes,define 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.

Node findNode(E)

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.

int depth(E)

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 defined 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 defined 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 defined 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 difference in heights of its left and right children is less than 2.

boolean isBalanced()

This method returns true only if isBalancedNode(n) returns true for all Nodes n in this BST.

Assessment

This assignment is scored out of a total of 71 points.

The findNode 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.