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
-
"In the article Ecological Footprints and Sustainable Development, Ian Moffatt states that one of the advantages of the ecological footprint concept is that the footprint is a stock. Define stock and...
-
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?
-
Draw the stereoisomers of 1-bromo-3-chlorocyclohexane
-
In Exercises 27-32, you are given an equation of a line and a point. Use substitution to determine whether the point is on the line. y = -2x + 8; A(-4, 0)
-
1. In an effort to increase collections, Bishop Company offers a 1/10, n/30 discount for early payment. Assume a sale of \($150,000\) made on August Ist. Determine the total sales, the sales...
-
Role of controller, role of chief financial officer. George Perez is the controller at Allied Electronics, a manufacturer of devices for the computer industry. He is being considered for a promotion...
-
P4-1A. Preparing a bank reconciliation (Learning Objective 1) 20-25 min. The September cash records of Povich Industrial Inc. follow: Cash Receipts (CR) Cash Payments (CP) Date Sep 4 9 Cash Debit...
-
Many institutions have fixed future liabilities to meet (such as pension payments) and they fund these future liabilities using default-free fixed income securities. When discount bonds of all...
-
What does the term Six Sigma refer to? What are the statistical concepts behind Six Sigma? Briefly describe the DMAIC acronym.
-
Discuss how you might approach a high level negotiation (use personal examples as needed) and include risk management as part of your negotiation plan. Use library articles or professional websites...
-
Operating data for Grouper Corp. are presented below. 2022 2021 Sales revenue $842,800 $645,500 Cost of goods sold 529,300 411,200 Selling expenses 124,400 79,500 Administrative expenses 79,500...
-
In periods of rising costs, when compared with other cost flow methods, LIFO will result in Cost of Goods Sold (COGS), Inventory and Net Income values that are: COGS Inventory i Higher Higher Net...
-
Month Hours of Maintenance Total Maintenance Cost January 625 7,950 February 500 7,400 March 700 8,275 April 550 7,625 May 775 9,100 June 800 9,800 Required: 1. Calculate Variable Cost per unit 2....
-
The owner of Manic Manufacturing, Joe Crazy, is considering selling his business. The potential buyer wants to see the most recent months' financial statements. However, Joe Crazy has not done an...
-
What are the different types of sanctions the US can use in terms of achieving foreign policy goals? What are the goals of these sanctions? If you were advising the President to use sanctions against...
-
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.
-
The following information is taken from the Fossil, Inc. 2015 annual report: Calculate Fossils actual and sustainable rate of growth in sales. How do the two rates of growth compare? What advice...
-
Presented below are selected financial data from the 2015 annual report of the Bristol-Myers Squibb Company: Required Using the ratio definitions from Exhibit 4.6, calculate the financial ratios for...
-
Presented below are selected financial data from the 2015 annual report of The Boeing Company: Required Using the ratio definitions from Exhibit 4.6, calculate the financial ratios for The Boeing...
Study smarter with the SolutionInn App