The BST index is implemented as a stand-alone class BSTIndex, with an inner class Node. Each...

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

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