Description
OBJECTIVES
-
Delete nodes in a BST
-
Create a super data structure combining BST and LL
[NOTE: Starter code for MovieTree.cpp will be released after closure of assignment 6]
Overview
This assignment builds off of the previous one conceptually, although the data structure is fundamentally different. Make sure to use the MovieTree.hppfile uploaded on Moodle for assignment 7,not the MovieTree.hppof the previous assignment 6. As usual, do not modify the header file. You may implement helper functions in your .cpp file to facilitate recursion if you want as long as you don’t add those functions to the MovieTree class.
MovieTree Class
Your task is to implement a binary search tree of linked lists of movies and perform left rotation on the nodes of this tree.Disclaimer: this diabolical super data structure is not practical; it is meant to challenge you and improve your skills manipulating and traversing BST’s and LL’s. Tree nodes will contain a letter of the alphabet and a linked list. The linked list will be an alphabetically sorted list of movies which start with that letter. For example:
Instructors: Zagrodzki, Ashraf, Trivedi
MovieTree::MovieTree()
-
Constructor: Initialize any member variables of the class to default
MovieTree::~MovieTree()
-
Destructor: Free all memory that was allocated
void MovieTree::printMovieInventory()
-
Print every movie in the data structure in alphabetical order of titles using the following format. For TreeNode tand LLMovieNode m:
// for every TreeNode (t) in the tree
cout<<“Movies starting with letter: “<<t->titleChar<<endl;
// for every LLMovieNode (m) attached to t
cout<<” >> “<<m->title <<” “<< m->rating <<endl;
Sample output format
Movies starting with letter: B
-
Bowling for Columbine 8 Movies starting with letter: D
Instructors: Zagrodzki, Ashraf, Trivedi
-
Dancin’ Outlaw 8.1
-
Dogtown and Z-Boys 7.7
-
Down from the Mountain 7.4
void MovieTree::addMovie(int ranking,std::string title,int year,float rating)
-
Add a movie to the data structure in the correct place based on its title.
-
If there is no tree node corresponding to the first letter of title,create it and insert it in the tree in the alphabetically correct position
-
Create a linked list node with ranking,title,year andrating,and insert it in the linked list associated with the tree node associated with the first letter of title.The linked list must also be in alphabetical order, such that for each node,
-
node->title < node->next->title
Hint: you can compare strings with <, >, ==, etc. Also, you may assume that no two movies have the same title
-
Make sure to set the parent pointers when adding a new node to the tree.
void MovieTree:: deleteMovie(std::string title)
-
Delete the linked list node that contains the title. If as a result of this deletion, the linked list becomes empty, delete the associated tree node. When deleting a tree node with both children take the replacement from its inorder successor (min of the right sub-tree). If the movie does not exist in the data structure, print the following message
cout<< “Movie: “ << title << ” not found, cannot delete.”<< endl;
-
Make sure to adjust the parent pointer when deleting a tree node.
void MovieTree::leftRotation(TreeNode* curr)
Rotate the node curr towards the left. Refer to the following illustration. A left rotation is performed at node x.
-
Set the parent pointers accordingly: After the rotation, the parent of x now becomes the parent of y.y becomes parent of x.
-
Set the children pointers: Three children pointers are modified. i) The left subtree of y becomes the right subtree of x.ii) x and it’s left descendants become the left subtree of y,with x as the left child. iii) If x was the left (or right) child of xp before
Instructors: Zagrodzki, Ashraf, Trivedi
the rotation, make y the left (or right) child of xp after rotation accordingly. This can be implemented by comparing the titles of y and xp:if y.title < xp.title,make y the left child of xp,else make y the right child of xp.A less riskier approach is to keep track of whether x was the left child or the right child before the rotation, and make ythe left or the right child accordingly.
-
Take care of the boundary cases: i) If x was the root before rotation, make y the new root. ii) If x does not have a right child, don’t perform any rotation.
void MovieTree::inorderTraversal()
This function performs an inorder traversal in the tree, printing the title character at each node. This will print the title characters in an inorder fashion. This function is available in the starter code. This will be useful for debugging purposes. If you want, you may use this function to create your preorderTraversal() and postorderTraversal() functions.
TreeNode* MovieTree::searchChar(char key)
This function returns a node in the tree with the titleChar key. This function is available in the starter code.
Driver
Code for the driver (main function) is given as part of the starter code. Here is a brief about the main function.
Instructors: Zagrodzki, Ashraf, Trivedi
Your main function should first read information about each movie from a file and store that
information in a MovieTree object. The name of the file with this information should be passed in as a command-line argument. An example file is Movies.csv on Moodle. It is in the format:
<Movie 1 ranking>,<Movie 1 title>,<Movie 1 year>,<Movie 1 rating> <Movie 2 ranking>,<Movie 2 title>,<Movie 2 year>,<Movie 2 rating> Etc…
Note: For autograding’s sake, insert the nodes to the tree in the order they are read in.After reading in the information on each movie from the file, display a menu to the user.
cout<< “======Main Menu======”<< endl; cout<< “1. Delete a movie”<< endl; cout<< “2. Print the inventory” << endl; cout<< “3. Left rotate the tree” << endl; cout<< “4. Quit”<< endl;
The options should have the following behavior:
-
Print the inventory: Call your tree’s printMovieInventoryfunction
-
Delete a movie: Call your deleteMoviefunction on a title specified by the user. Prompt the user for a movie title using the following code:
cout<< “Enter a movie title:”<< endl;
-
Left rotate the tree: Ask the user to enter the titleChar for the node to rotate left. If that is a valid node perform the rotation.
cout<< “”give the titleChar of the node:””<< endl;
string nodename;
getline(cin, nodename);
TreeNode* rNode = movies.searchChar(nodename[0]); if (rNode)
movies.leftRotation(rNode);
-
Quit: Exit after printing a friendly message to the user: cout<< “Goodbye!”<< endl;
Instructors: Zagrodzki, Ashraf, Trivedi
“Please note that once you are done with your assignment on code runner you need to click on ‘finish attempt’ and the ‘submit all and finish’. If you don’t do this, you will not get graded.”
