You are to develop a simple Binary Search Tree ADT and run it against a test...
Fantastic news! We've Found the answer you've been seeking!
Question:
Transcribed Image Text:
You are to develop a simple Binary Search Tree ADT and run it against a test program. Avoid the temptation of finding code online. I am aware of all the available solutions and will be looking closely at your code. You do not need to balance your tree. ⚫ Basic Level (for a maximum grade of 85%): Develop the BST as a class that uses doubles as keys and Strings as values. Advanced Level (for a maximum grade of 100%): Develop the BST as a generic class that uses any objects as keys and values. Remember that a BST is a proper Binary Tree with the following property: Let u, v, and w be three nodes such that u is in the left subtree of v and w is in the right subtree of v. We have key(u) <key(v) <key(w) Basic Level: The complete design of the BST class (non-generic) is shown below. You will need to create the inner class Node. Node BST -root: Node -size: int +BSTO +insert(key: double, value: String): void +find(key: double): String -find(key: double, n: Node): String +delete(key: double): String +size(): int -key: double -value: String -left: Node -right: Node +Node(k: double, v: String) +getKey(): double +getValue(): String +getLeft): Node +getRight: Node +setLeft(n: Node): void +toString: String +setRight(n: Node): void +toString(): String +toString(level: int): String BST(): Construct an empty BST. ■void insert(double key, String value): Insert the element (key, value) into the BST into the proper position. String find(double key): Find the first value with the matching key. Return null if the key is not found. You may want to define a private helper method find(double, Node) to help with the recursive solution. ■String delete(double key): Remove the first element with the matching key and return the value. Return null if the key is not found. ■int size(): Return the number of elements in the BST. • Page < 2 > of 4 ZOOM " String toString(): Convert the BST to a hierarchical, indented String, as shown in the output below. Notice that I have also included a String toString(int level) in the Node class to help implement this hierarchy. Advanced Level: The complete design of the generic BST class is shown below. You will need to create the inner class Node. Refer to the Basic Level description above for a definition of the methods. BST -root: Node -size: int +BST() +insert(key: K, value: V): void +find(key: K): V -find(key: K, node n): V +delete(key: K): V +toString(): String +size(): int Node -key: K -value: V -left: Node -right: Node +Node(k: K, v: V) +getKey(): K +getValue(): V +getLeft(): Node +getRight(): Node +setLeft(n: Node): void +setRight(n: Node): void. +toString(): String +toString(level: int): String With either solution, when your implementation is complete, run it with the test driver BSTTest.java (provided). Review the results to make sure that your BST ADT is working correctly. The expected output is included in the file BSTExpected Output.txt and portions are shown below. Your output must include your name. 2. Notes • You must use the test driver code found with this assignment: BSTTest.java. You should not modify BSTTest.java except to add your name. • Turn in only your source files: BST.java and BSTTest.java. If you have created other classes as part of the solution, you need to turn those in as well. • Make sure your class is not in a package (that is, it is in the default package). • We normally must be careful when comparing double values. However, for the purposes of this assignment, you can assume that d1 == d2 will work for matching double keys. • For the generic solution (Advanced level), you can assume that keys are Comparable. • You will need to download the file words.txt and put it at the Project level within Eclipse. 3. Required Main Class BSTTest, provided 4. Required Input Not applicable + K لا Page < 3 > of 4 ZOOM 5. Required Output Your output should look like the following. The complete output is too long to include here, so I have removed selected lines (shown as ...). The complete output is available in BSTExpected Output.txt for comparison purposes. The Large Tree is random so your tree will not match mine. BST Test Program Your Name 1) Building a Tree ======================== Initially: null Insert (3.0, A): (k=3.00, v=A) null null Insert (4.0, E) (k=3.00, v=A) (k=2.00, v=C) null null (k=5.00, v=B) (k=4.00, v=E) null null (k=6.00, v=D) null null 2) Finding Elements ============ b1.find(2.0): C 3) Deleting Elements Delete (1.0) Left child, leaf: A (k=6.00, v=E) (k=3.00, v=H) (k=2.00, v=F) null null (k=5.00, v=C) (k=4.00, v=G) null null null (k=9.00, v=I) (k=7.00, v=J) null (k=8.00, v=B) null null (k=10.00, v=D) null (k=11.00, v=K) null null Delete (5.0) Has left child, internal: C (k=6.00, v=E) (k=3.00, v=H) (k=2.00, v=F) Page 3 + K لا null null (k=4.00, v=G) null null (k=9.00, v=I) (k=7.00, v=J) null null (k=10.00, v=D) null (k-11.00, v=K) null null Delete (6.0) Has two children, internal: E (k=7.00, v=J) (k=3.00, v=H) (k=2.00, v=F) null null (k=4.00, v=G) null null (k=9.00, v=I) null (k=11.00, v=K) null null 4) A Large Tree ======================== First 10: Size is now 10 Remaining Elements: Size is now 100000 Page < 4 of 4 ZOOM + K لا You are to develop a simple Binary Search Tree ADT and run it against a test program. Avoid the temptation of finding code online. I am aware of all the available solutions and will be looking closely at your code. You do not need to balance your tree. ⚫ Basic Level (for a maximum grade of 85%): Develop the BST as a class that uses doubles as keys and Strings as values. Advanced Level (for a maximum grade of 100%): Develop the BST as a generic class that uses any objects as keys and values. Remember that a BST is a proper Binary Tree with the following property: Let u, v, and w be three nodes such that u is in the left subtree of v and w is in the right subtree of v. We have key(u) <key(v) <key(w) Basic Level: The complete design of the BST class (non-generic) is shown below. You will need to create the inner class Node. Node BST -root: Node -size: int +BSTO +insert(key: double, value: String): void +find(key: double): String -find(key: double, n: Node): String +delete(key: double): String +size(): int -key: double -value: String -left: Node -right: Node +Node(k: double, v: String) +getKey(): double +getValue(): String +getLeft): Node +getRight: Node +setLeft(n: Node): void +toString: String +setRight(n: Node): void +toString(): String +toString(level: int): String BST(): Construct an empty BST. ■void insert(double key, String value): Insert the element (key, value) into the BST into the proper position. String find(double key): Find the first value with the matching key. Return null if the key is not found. You may want to define a private helper method find(double, Node) to help with the recursive solution. ■String delete(double key): Remove the first element with the matching key and return the value. Return null if the key is not found. ■int size(): Return the number of elements in the BST. • Page < 2 > of 4 ZOOM " String toString(): Convert the BST to a hierarchical, indented String, as shown in the output below. Notice that I have also included a String toString(int level) in the Node class to help implement this hierarchy. Advanced Level: The complete design of the generic BST class is shown below. You will need to create the inner class Node. Refer to the Basic Level description above for a definition of the methods. BST -root: Node -size: int +BST() +insert(key: K, value: V): void +find(key: K): V -find(key: K, node n): V +delete(key: K): V +toString(): String +size(): int Node -key: K -value: V -left: Node -right: Node +Node(k: K, v: V) +getKey(): K +getValue(): V +getLeft(): Node +getRight(): Node +setLeft(n: Node): void +setRight(n: Node): void. +toString(): String +toString(level: int): String With either solution, when your implementation is complete, run it with the test driver BSTTest.java (provided). Review the results to make sure that your BST ADT is working correctly. The expected output is included in the file BSTExpected Output.txt and portions are shown below. Your output must include your name. 2. Notes • You must use the test driver code found with this assignment: BSTTest.java. You should not modify BSTTest.java except to add your name. • Turn in only your source files: BST.java and BSTTest.java. If you have created other classes as part of the solution, you need to turn those in as well. • Make sure your class is not in a package (that is, it is in the default package). • We normally must be careful when comparing double values. However, for the purposes of this assignment, you can assume that d1 == d2 will work for matching double keys. • For the generic solution (Advanced level), you can assume that keys are Comparable. • You will need to download the file words.txt and put it at the Project level within Eclipse. 3. Required Main Class BSTTest, provided 4. Required Input Not applicable + K لا Page < 3 > of 4 ZOOM 5. Required Output Your output should look like the following. The complete output is too long to include here, so I have removed selected lines (shown as ...). The complete output is available in BSTExpected Output.txt for comparison purposes. The Large Tree is random so your tree will not match mine. BST Test Program Your Name 1) Building a Tree ======================== Initially: null Insert (3.0, A): (k=3.00, v=A) null null Insert (4.0, E) (k=3.00, v=A) (k=2.00, v=C) null null (k=5.00, v=B) (k=4.00, v=E) null null (k=6.00, v=D) null null 2) Finding Elements ============ b1.find(2.0): C 3) Deleting Elements Delete (1.0) Left child, leaf: A (k=6.00, v=E) (k=3.00, v=H) (k=2.00, v=F) null null (k=5.00, v=C) (k=4.00, v=G) null null null (k=9.00, v=I) (k=7.00, v=J) null (k=8.00, v=B) null null (k=10.00, v=D) null (k=11.00, v=K) null null Delete (5.0) Has left child, internal: C (k=6.00, v=E) (k=3.00, v=H) (k=2.00, v=F) Page 3 + K لا null null (k=4.00, v=G) null null (k=9.00, v=I) (k=7.00, v=J) null null (k=10.00, v=D) null (k-11.00, v=K) null null Delete (6.0) Has two children, internal: E (k=7.00, v=J) (k=3.00, v=H) (k=2.00, v=F) null null (k=4.00, v=G) null null (k=9.00, v=I) null (k=11.00, v=K) null null 4) A Large Tree ======================== First 10: Size is now 10 Remaining Elements: Size is now 100000 Page < 4 of 4 ZOOM + K لا
Expert Answer:
Answer rating: 100% (QA)
Combining the information from all four images we can address the problem of efficiently managing a collection of elements likely implementing a custo... View the full answer
Related Book For
Statistics For Business And Economics
ISBN: 9780132745659
8th Edition
Authors: Paul Newbold, William Carlson, Betty Thorne
Posted Date:
Students also viewed these programming questions
-
re Regular Languages and Finite Automata (a) Let L be the set of all strings over the alphabet {a, b} that end in a and do not contain the substring bb. Describe a deterministic finite automaton...
-
Planning is one of the most important management functions in any business. A front office managers first step in planning should involve determine the departments goals. Planning also includes...
-
How do accounting differences impact the usefulness of financial ratio comparisons?
-
Ohio's SIP was submitted to the EPA. Approval of a portion of the plan was denied because it was not adequate to ensure the attainment and maintenance of the primary standard for photochemical...
-
Write the function in the form y = (u) and u = g(x). Then find dy/dx as a function of x. y = 3x - 4x + 6
-
Copy your worksheet from Question 6 into another worksheet. Change the increase from 10% to 18%. Protect the worksheet, so that changes cannot be made. Question 6 Open a new spreadsheet. Type...
-
Clearcast Communications Inc. is considering allocating a limited amount of capital investment funds among four proposals. The amount of proposed investment, estimated income from operations, and net...
-
A certain substance has a mass per mole of 53 g/mol. When 312 J is added as heat to a 26.0 g sample, the sample's temperature rises from 21.0C to 45.0C. What are the (a) specific heat and (b) molar...
-
IBS is a global provider of point-of-sale systems and related services that enable businesses to accept electronic payments. As a new hire in the companys international headquarters accounting...
-
G.I. Jane was a soldier in the Iraq war. Her salary was $2600 per month and she was in the war zone for eight months. How much of her salary is taxable for the eight months? Please cite the...
-
solve this error? I'll attach the instructions, my code, and the error images here. The language is Java. Instructions: Exception in thread "main" java.lang.NullPointerException: Cannot invoke...
-
Explain specifically in detail about the connection between Prospect theory vs Expected Utility and how do they relate in decision making.
-
Your client made a substantial donation to a public charity that exceeded A GIlimits for deductibility purposes in the year the gift was made. What is the bestway to capture this in eMoney so that...
-
A machine can fill 3 jugs with juice in 10 minutes. Each jug contains 1.5 liters of juice. a. How many jugs can be filled in 1 hour?
-
modeled by the equation: Radioactive decay of radio active materials can be log2, A Age where A, is the amount of the material at time t, A, is the original amount and h is the half-life....
-
How do I get the equation for sodium aluminate + sodium silicate Zeolite-A and limiting reagent if the values are 1.3 g of sodium aluminated disoolved in 30mL of 12% sodium hydroxide and 1.1g of...
-
Distinguish among total-moisture content, free-moisture content, equilibrium-moisture content, unbound moisture, and bound moisture.
-
Suppose that you were asked by your state office of elections to assist in resolving an election dispute between two candidates, or perhaps you were asked to be a statistical expert in a lawsuit...
-
The following model was fitted to a sample of 30 families in order to explain household milk consumption: y = 0 + 1x1 + 2x2 + where y = milk consumption, in quarts per week x1 = weekly income, in...
-
Let the random variable represent the number of times that you will miss class this semester. Prepare a table that shows the probability distribution and the cumulative probability distribution.
-
W hat is diauxic growth? Explain the roles of cAMP and CAP in this process.
-
What is antisense RNA? How does it affect the translation of a complementary mRNA?
-
List and describe three general ways that the functions of transcription factors can be modulated.
Study smarter with the SolutionInn App