The BST index is implemented as a stand-alone class BSTIndex, with an inner class Node. Each...
Fantastic news! We've Found the answer you've been seeking!
Question:
Transcribed Image Text:
The BST index is implemented as a stand-alone class BSTIndex, with an inner class Node. Each node within a BSTIndex tree contains 4 fields: key (of type String), data (of type MovieInfo), and left and right links to the children nodes. The BST index tree should never contain duplicate nodes; i.e. each node key needs to be unique across the tree. You will complete the implementation of the following methods and operations in class BSTIndex. All BST operations should be implemented using recursion. ⚫ [20 points] public int calcHeight() • This method should calculate and return the height of the current BSTIndex tree. We define the height of a tree (similar to our lecture slides) as the maximum depth in the tree plus 1. The height of a tree with only one node is 1, and the height of an empty tree is 0. Important: Notice that this is a public method that calls another private method calcNode- Height(Node t) and passes it a reference to the root. This is a common way of structuring BST methods such that external client code will not have direct access to the tree root. You will thus be implementing the code in the private calcNodeHeight (Node t) method. This applies to the rest of the methods in this assignment as well. [15 points] public void insert Movie (Movie Info data) This method should insert the given data element into the proper place in the BST structure. If the input file turned out to have duplicate keys (i.e. repeated short movie titles), then your insertion method should detect that and not add the new duplicated movie to the tree. [20 points] public Movie Info find Movie (String key) This method should return the data element (i.e. the MovieInfo object) of the node where the movie's shortTitle matches the given key. Return null if the movie is not found. ⚫ [20 points] public ArrayList<String> getMoviesPrefix (String prefixStr) This method should return (as an ArrayList) all movies (i.e., full title) in the tree whose • [15 points] public ArrayList<Integer> inorderTraversal () This method should traverse the tree in order and return the IDs of the movie based on the key order of the tree.) The IndexTester class is provided which will test your BSTIndex class. The IndexTester creates an empty BSTIndex object then reads the data from an input movie file, builds a MovieInfo object for each row, and inserts it into the BST index (using the insert method you implemented in BSTIndex class). At this point, the BST index will be built for all the movie entries in the file. Then, the program will ask the user to enter a string. The code for parsing the input string and deciding which operation to invoke is part of the starter code. Here's an example of how a program run might look like. Note that the data file name is passed as an argument to the program's main() method here using the command line: > java IndexTester data/movies100K.txt Inserted 10000 records. Inserted 20000 records. Inserted 30000 records. Inserted 40000 records. Inserted 50000 records. Inserted 60000 records. Inserted 70000 records. Inserted 80000 records. Inserted 90000 records. Inserted 100000 records. Index building complete. Inserted 100000 records. Elapsed time = here> seconds. Welcome to the IMDB movie search engine! - Enter search string to find a specific movie. <your_result_ - Enter search string ending with '*' to print all movies that match this prefix - Enter 'h' to print tree height. Enter 'q' to quit. Enter Option: h Height of BSTIndex tree = <your_result_here> Enter Option: Gang Movie Gang Not Found Enter Option: Gang* [Finding all movies that start with Gang..] Gang tai Gang Gangster Squad Gang Wars Gangotri <rest_of_matches_here> Enter Option: q The BST index is implemented as a stand-alone class BSTIndex, with an inner class Node. Each node within a BSTIndex tree contains 4 fields: key (of type String), data (of type MovieInfo), and left and right links to the children nodes. The BST index tree should never contain duplicate nodes; i.e. each node key needs to be unique across the tree. You will complete the implementation of the following methods and operations in class BSTIndex. All BST operations should be implemented using recursion. ⚫ [20 points] public int calcHeight() • This method should calculate and return the height of the current BSTIndex tree. We define the height of a tree (similar to our lecture slides) as the maximum depth in the tree plus 1. The height of a tree with only one node is 1, and the height of an empty tree is 0. Important: Notice that this is a public method that calls another private method calcNode- Height(Node t) and passes it a reference to the root. This is a common way of structuring BST methods such that external client code will not have direct access to the tree root. You will thus be implementing the code in the private calcNodeHeight (Node t) method. This applies to the rest of the methods in this assignment as well. [15 points] public void insert Movie (Movie Info data) This method should insert the given data element into the proper place in the BST structure. If the input file turned out to have duplicate keys (i.e. repeated short movie titles), then your insertion method should detect that and not add the new duplicated movie to the tree. [20 points] public Movie Info find Movie (String key) This method should return the data element (i.e. the MovieInfo object) of the node where the movie's shortTitle matches the given key. Return null if the movie is not found. ⚫ [20 points] public ArrayList<String> getMoviesPrefix (String prefixStr) This method should return (as an ArrayList) all movies (i.e., full title) in the tree whose • [15 points] public ArrayList<Integer> inorderTraversal () This method should traverse the tree in order and return the IDs of the movie based on the key order of the tree.) The IndexTester class is provided which will test your BSTIndex class. The IndexTester creates an empty BSTIndex object then reads the data from an input movie file, builds a MovieInfo object for each row, and inserts it into the BST index (using the insert method you implemented in BSTIndex class). At this point, the BST index will be built for all the movie entries in the file. Then, the program will ask the user to enter a string. The code for parsing the input string and deciding which operation to invoke is part of the starter code. Here's an example of how a program run might look like. Note that the data file name is passed as an argument to the program's main() method here using the command line: > java IndexTester data/movies100K.txt Inserted 10000 records. Inserted 20000 records. Inserted 30000 records. Inserted 40000 records. Inserted 50000 records. Inserted 60000 records. Inserted 70000 records. Inserted 80000 records. Inserted 90000 records. Inserted 100000 records. Index building complete. Inserted 100000 records. Elapsed time = here> seconds. Welcome to the IMDB movie search engine! - Enter search string to find a specific movie. <your_result_ - Enter search string ending with '*' to print all movies that match this prefix - Enter 'h' to print tree height. Enter 'q' to quit. Enter Option: h Height of BSTIndex tree = <your_result_here> Enter Option: Gang Movie Gang Not Found Enter Option: Gang* [Finding all movies that start with Gang..] Gang tai Gang Gangster Squad Gang Wars Gangotri <rest_of_matches_here> Enter Option: q
Expert Answer:
Answer rating: 100% (QA)
Heres a breakdown of the functionalities mentioned in the image BSTIndex is a class that represents a Binary Search Tree A Binary Search Tree BST is a tree data structure where each node has at most t... View the full answer
Related Book For
Practical Introduction To Data Structures And Algorithm Analysis Java Edition
ISBN: 9780136609117
1st Edition
Authors: Clifford A. Shaffer
Posted Date:
Students also viewed these programming questions
-
Mark as Complete 17. Refer to the following table. Assume the following data for Smithsonian Company for 2013: Beginning inventory March 18 sale June 10 purchase October 30 sale 10 units at $70 each...
-
Abstract - Intrusion detection plays important role in examining the malicious activity which occurs in a network or a system. Its a software or a device which scans the system or network for a...
-
answer the question clearly You are building a flight-control system for which a convincing safety case must be made. Would you assign the tasks of safety requirements engineering, test case...
-
Accounting Today identified top accounting firms in 10 geographic regions across the United States. All 10 regions reported growth in 2016. The Southeast and Gulf Coast regions reported growths of...
-
Ri = 4 with probability 0.25, Ri = 0.25 with probability 0.75. Find the probability that P25 lies between 1 and 3. In a population growing by reproduction, the logarithm of population size can be...
-
Why would an outline help in preparing for telephone conversations and for leaving voicemail messages?
-
A company purchases a machine for $96,000 on January I, 2005. Its useful life is five years or 100,000 units of product, and its salvage value is $8,000. During 2005, 10,000 units of product are...
-
Refer to the lottery payout options summarized in Exhibit 21-9. Requirement 1. Rather than comparing the payout options at their present values (as done in the chapter), compare the payout options at...
-
Suppose you are developing an Excel spreadsheet that finds the unit price of any object. You plan to put the number of units in cell D2, and the price of the object in cell E2. Which formula would...
-
Hi Tutor, Could you please fill in the tables below? Many thanks!
-
Law enforcement authorities and officials of regulatory agencies frequently receive anonymous "hot tips." The shy tipsters typically charge that an individual or organization has violated one or more...
-
What are the implications of pursuing each of the three courses of action suggested by JohnnyTan?
-
Lore Levi was worried as she scanned the March 1983 bank statement for the Howard Street Jewelers. \({ }^{1}\) For more than four decades, she and her husband, Julius, had owned and operated the...
-
In the context of sales channels, why is it important to engage in segmentation and targeting?
-
What can Johnny Tan do to revitalise his distribution channel?
-
Vaughn Company owns equipment that cost $1,035,000 and has accumulated depreciation of $437,000. The expected future net cash flows from the use of the asset are expected to be $625,000. The fair...
-
A bar of a steel alloy that exhibits the stress-strain behavior shown in Figure 6.22 is subjected to a tensile load; the specimen is 375 mm (14.8 in.) long and has a square cross section 5.5 mm (0.22...
-
Implement a priority queue class based on the max-heap class implementation of Figure 5.19. The following methods should be supported for manipulating the priority queue: void enqueue(int ObjectID,...
-
What fraction of the values in a matrix must be zero for the sparse matrix representation of Section 12.2 to be more space efficient than the standard two-dimensional matrix representation when data...
-
Most programming languages have a built-in integer data type. Normally this representation has a fixed size, thus placing a limit on how large a value can be stored in an integer variable. Describe a...
-
Name two companies that provide benchmarking data to hotels.
-
Explain the four dimensions of the Balanced Scorecard.
-
Why is it important to use both internal and external benchmarking data?
Study smarter with the SolutionInn App