This is the function for RB tree not for the BST. In this assignment, you will c

Question

This is the function for RB tree not for the BST.

In this assignment, you will continue working with the movie data from the BST assignment and store that data in a red-black tree. A red-black tree is a selfbalancing binary search tree. The main difference between this assignment and previous assignments is that you will need to balance the tree each time a new movie node is added or deleted. For each of the movies in the movie nodes in the movie tree, the following information is kept:

- IMDB ranking

- Title

- Year released

- Quantity in stock

- Node color Your program will have a menu similar to previous assignments from which the user can select options. In this assignment, your menu needs to include options for finding a movie, renting a movie, printing the inventory, deleting a movie, counting the number of movies, counting levels in the tree, and quitting the program. Use the same Assignment8Movies.txt file that you used for the BST movie assignment. The name of the input file needs to be handled as a command-line argument.

1. Insert all the movies in the tree.

When the user starts the program they will pass it the name of the text file that contains all movie information. Your program needs to handle that command-line argument, open the file, and read all movie data in the file. From this data, build the red-black tree ordered by movie title. As movies are added to the tree, the red-black tree-balancing algorithm should be applied. All information about the movie should also be included in the movie node in the tree. Note: the data should be added to the tree in the order it is read in.

2. Find a movie.

When the user selects this option from the menu, they should be prompted for the name of the movie. If the movie is found in the tree, display the movie information. If the movie is not found, your program should display, “Movie not found.” This option is similar to rent movie, however, you are not updating the quantity.

3. Rent a movie.

When the user selects this option from the menu, they should be prompted for the name of the movie. If the movie is found in the tree, your program should update the Quantity in stock property of the movie and display the new information about the movie. When the Quantity is 0, the movie should be deleted from the tree. When a movie is deleted, the tree should be rebalanced. If the movie is not found, your program should display, “Movie not found.”

4. Print the entire inventory.

When the user selects this option from the menu, your program should display all movie titles and the quantity available in sorted order by title. See the lecture notes on in-order tree traversal for more information.

5. Delete a movie.

When the user selects this option, they should be prompted for the title of the movie to delete. Your code should then search the tree for that movie, delete it if it’s found, and then perform any necessary tree balancing to restore the red-black tree properties. If the movie is not found in the search process, print “Movie not found.” and do not attempt to delete.

6. Count movies in the tree.

When the user selects this option, your program should do an in-order tree traversal and count the total movie nodes in the tree and print the value.

7. Count longest path.

When the user selects this option, your program needs to determine the longest path from the root of the tree to the bottom of tree, not including empty nodes.

8. Quit the program.

When the user selects this option, your program should delete the tree using a post-order traversal.

MovieTree.h:

expected ouput

Display menu

cout << "======Main Menu======" << endl;

cout << "1. Find a movie" << endl;

cout << "2. Rent a movie" << endl;

cout << "3. Print the inventory" << endl;

cout << "4. Delete a movie" << endl;

cout << "5. Count the movies" << endl;

cout << "6. Count the longest path" << endl;

cout << "7. Quit" << endl;

Find a movie

cout << "Enter title:" << endl;

Display found movie information

cout << "Movie Info:" << endl;

cout << "===========" << endl;

cout << "Ranking:" << foundMovie->ranking << endl;

cout << "Title:" << foundMovie->title << endl;

cout << "Year:" << foundMovie->year << endl;

cout << "Quantity:" << foundMovie->quantity << endl;

If movie not found cout << "Movie not found." << endl;

Rent a movie

//If movie is in stock cout << "Movie has been rented." << endl;

cout << "Movie Info:" << endl; cout << "===========" << endl;

cout << "Ranking:" << foundMovie->ranking << endl;

cout << "Title:" << foundMovie->title << endl;

cout << "Year:" << foundMovie->year << endl;
cout << "Quantity:" << foundMovie->quantity << endl;
//If movie not found in tree
cout << "Movie not found." << endl;
Print   the   inventory
//For all movies in tree
cout<<"Movie: "<<node->title<<" "<<node->quantity<<endl;
Count   movies   in   the   tree
cout<<"Tree contains: "<<mt.countMovieNodes()<<" movies."
<< endl;
Longest   path
cout << "Longest Path: " << mt->countLongestPath() << endl;
Delete   movie
cout << "Enter title:" << endl;
//If movie not found in tree
cout << "Movie not found." << endl;
Delete   all   nodes   in   the   tree
//For all movies in tree
cout<<"Deleting: "<<node->title<<endl;
Quit
cout << "Goodbye!" << endl;
File   I/O   Error
cout << "Could not open file ";

Explanation / Answer

MovieTree.h

#ifndef MOVIETREE_H
#define MOVIETREE_H

#include <string>

using namespace std;

struct MovieNode
{
int ranking;
std::string title;
int year;
int quantity;
bool isRed;
MovieNode *parent;
MovieNode *leftChild;
MovieNode *rightChild;

MovieNode() {};

MovieNode(int in_ranking, std::string in_title, int in_year, int in_quantity)
{
ranking = in_ranking;
title = in_title;
year = in_year;
quantity = in_quantity;
// Now that we are using nil these NULL's should be overwritten in addMovieNode.
leftChild = NULL;
rightChild = NULL;
parent = NULL;
isRed = true;
}

};

class MovieTree
{

public:
MovieTree();
virtual ~MovieTree();
void printMovieInventory();
int countMovieNodes();
void deleteMovieNode(std::string title);
void addMovieNode(int ranking, std::string title, int releaseYear, int quantity);
void findMovie(std::string title);
void rentMovie(std::string title);
int countLongestPath();

void printEasy();

protected:

private:
void addNode(MovieNode* root, MovieNode* new_node);
void DeleteAll(MovieNode * node); //use this for the post-order traversal deletion of the tree
void printMovieInventory(MovieNode * node);
void rbAddFixup(MovieNode * node); // called after insert to fix tree
void leftRotate(MovieNode * x); //rotate the tree left with x as the root of the rotation
void rbDelete(MovieNode * z); //delete a node. Call this from deleteMovieNode, the actual delete functionality happens here.
void rightRotate(MovieNode * x); //rotate the tree right with x as the root of the rotation
void rbDeleteFixup(MovieNode* node); //called after delete to fix the tree
void rbTransplant(MovieNode * u, MovieNode * v); //replace node u in tree with node v. Your solution doesn't necessarily need to use this method
int rbValid(MovieNode * node); //check if the tree is valid, with node as the root of the tree
int countMovieNodes(MovieNode *node); //number of unique titles in the tree
int countLongestPath(MovieNode *node); //longest path from node to a leaf node in the tree
bool verifyTree(MovieNode* node);

void printNodeInfo(MovieNode* n);
MovieNode* treeMinimum(MovieNode *node);

MovieNode* searchMovieTree(MovieNode * node, std::string title);
MovieNode* getNodeUncle(MovieNode* node);
MovieNode* getNodeGrandparent(MovieNode* node);
MovieNode* getNodeSibling(MovieNode* parent, MovieNode* node);

MovieNode *root;
MovieNode *nil;

void printWholeTree(MovieNode* n, string indent, bool last);
string redify(string text);

};

#endif // MOVIETREE_H

MovieTree.cpp

#include <string>
#include <iostream>
#include "MovieTree.h"
#include <cassert>

using namespace std;

MovieTree::MovieTree()
{
root = NULL;
nil = new MovieNode(-1, "NIL", -1, -1);
nil->isRed = false;
}

MovieTree::~MovieTree()
{
if (root != NULL)
{
DeleteAll(root);
}
delete nil;
}

void MovieTree::printMovieInventory()
{
if (root != NULL)
{
printMovieInventory(root);
}
}

int MovieTree::countMovieNodes()
{
return countMovieNodes(root);
}

int MovieTree::countLongestPath()
{
return countLongestPath(root);
}

void MovieTree::deleteMovieNode(std::string title)
{
MovieNode* to_delete = searchMovieTree(root, title);
if (to_delete != nil)
{
if (to_delete->leftChild != nil && to_delete->rightChild != nil)
{
MovieNode* replacement = treeMinimum(to_delete->rightChild);
to_delete->title = replacement->title;
to_delete->quantity = replacement->quantity;
to_delete->ranking = replacement->ranking;
to_delete->year = replacement->year;
to_delete = replacement;
}
rbDelete(to_delete);
assert(verifyTree(root));
assert(rbValid(root));
}
}

void MovieTree::addMovieNode(int ranking, std::string title, int releaseYear, int quantity)
{
MovieNode* n = new MovieNode(ranking, title, releaseYear, quantity);
n->leftChild = nil;
n->rightChild = nil;
n->isRed = true;
if (root == NULL)
{
root = n;
n->isRed = false;
return;
}
else
{
addNode(root, n);
}
rbAddFixup(n);
assert(verifyTree(root));
if (!rbValid(root))
{
cout << title << endl;
cout << root->parent << endl << endl << endl;
assert(false);
}
//printWholeTree(root, "", true);
}

void MovieTree::findMovie(std::string title)
{
MovieNode* n = searchMovieTree(root, title);
if (n == nil)
{
cout << "Movie not found." << endl;
}
else
{
printNodeInfo(n);
}
}

void MovieTree::rentMovie(std::string title)
{
MovieNode* n = searchMovieTree(root, title);
if (n == nil)
{
cout << "Movie not found." << endl;
}
else
{
cout << "Movie has been rented." << endl;
n->quantity--;
printNodeInfo(n);
if (n->quantity == 0)
{
deleteMovieNode(n->title);
}
}
}

void MovieTree::printNodeInfo(MovieNode* n)
{
cout << "Movie Info:" << endl;
cout << "===========" << endl;
cout << "Ranking:" << n->ranking << endl;
cout << "Title:" << n->title << endl;
cout << "Year:" << n->year << endl;
cout << "Quantity:" << n->quantity << endl;
}

void MovieTree::addNode(MovieNode* tree, MovieNode* new_node)
{
if (new_node->title < tree->title)
{
if (tree->leftChild == nil)
{
tree->leftChild = new_node;
new_node->parent = tree;
}
else
{
addNode(tree->leftChild, new_node);
}
}
else
{
if (tree->rightChild == nil)
{
tree->rightChild = new_node;
new_node->parent = tree;
}
else
{
addNode(tree->rightChild, new_node);
}
}
}

void MovieTree::DeleteAll(MovieNode * node)
{
if (node->leftChild != nil)
{
DeleteAll(node->leftChild);
node->leftChild = NULL;
}
if (node->rightChild != nil)
{
DeleteAll(node->rightChild);
node->rightChild = NULL;
}
cout << "Deleting: " << node->title << endl;
delete node;
}

int MovieTree::countMovieNodes(MovieNode *node)
{
int count = 0;
if (node->leftChild != nil)
{
count += countMovieNodes(node->leftChild);
}
if (node->rightChild != nil)
{
count += countMovieNodes(node->rightChild);
}
return count + 1;
}

MovieNode* MovieTree::searchMovieTree(MovieNode *node, std::string value)
{
if (node == nil)
{
return nil;
}
else if (node->title == value)
{
return node;
}
else if (value > node->title && node->rightChild != nil)
{
return searchMovieTree(node->rightChild, value);
}
else if (value < node->title && node->leftChild != nil)
{
return searchMovieTree(node->leftChild, value);
}
return nil;
}

MovieNode* MovieTree::treeMinimum(MovieNode *node)
{
if (node->leftChild != nil)
{
return treeMinimum(node->leftChild);
}
return node;
}

bool MovieTree::verifyTree(MovieNode* node)
{
bool result = true;
if (node->leftChild != nil)
{
result &= verifyTree(node->leftChild);
result &= node->leftChild->title < node->title;
if (node->leftChild->parent != node)
{
cout << "parent verification error: " << node->title << " IS NOT PARENT of LC: " << node->leftChild->title
<< "(" << node->leftChild->parent->title << ")"<< endl;
result = false;
}
}
if (node->rightChild != nil)
{
result &= verifyTree(node->rightChild);
result &= node->rightChild->title > node->title;
if (node->rightChild->parent != node)
{
cout << "parent verification error: " << node->title << " IS NOT PARENT of RC: " << node->rightChild->title
<< "(" << node->rightChild->parent->title << ")" << endl;
result = false;
}
}
return result;
}

void MovieTree::printMovieInventory(MovieNode* node)
{
if (node->leftChild != nil)
{
printMovieInventory(node->leftChild);
}
cout << "Movie: " << node->title << " " << node->quantity << endl;
if (node->rightChild != nil)
{
printMovieInventory(node->rightChild);
}
}

void MovieTree::rbAddFixup(MovieNode * node)
{
MovieNode* uncle = NULL;
MovieNode* current_node = node;
while (1)
{
if (current_node->parent == NULL)
{
current_node->isRed = false;
return;
}
else if (!current_node->parent->isRed)
{
return;
}
else if (((uncle = getNodeUncle(current_node)) != NULL) && (uncle->isRed))
{
current_node->parent->isRed = false;
uncle->isRed = false;
current_node = getNodeGrandparent(current_node);
current_node->isRed = true;
}
else
{
break;
}
}
//cout << "finished insert loop" << endl;
MovieNode* p = current_node->parent;
MovieNode* g = getNodeGrandparent(current_node);
MovieNode* n = current_node;
//left left case
if (g->leftChild == p && p->leftChild == n)
{
rightRotate(g);
bool temp = p->isRed;
p->isRed = g->isRed;
g->isRed = temp;
}
else if (g->leftChild == p && p->rightChild == n)
{
leftRotate(p);
rightRotate(g);
bool temp = n->isRed;
n->isRed = g->isRed;
g->isRed = temp;
}
else if (g->rightChild == p && p->rightChild == n)
{
leftRotate(g);
bool temp = p->isRed;
p->isRed = g->isRed;
g->isRed = temp;
}
else
{
rightRotate(p);
leftRotate(g);
bool temp = n->isRed;
n->isRed = g->isRed;
g->isRed = temp;
}
}

void MovieTree::leftRotate(MovieNode * x)
{
MovieNode* r = x->rightChild;
x->rightChild = r->leftChild;
if (x->rightChild != nil)
{
x->rightChild->parent = x;
}

r->parent = x->parent;
if (x->parent == NULL)
{
root = r;
}
else if (x->parent->leftChild == x)
{
x->parent->leftChild = r;
}
else
{
x->parent->rightChild = r;
}
r->leftChild = x;
x->parent = r;

nil->parent = NULL;
nil->leftChild = NULL;
nil->rightChild = NULL;
}

void MovieTree::rbDelete(MovieNode* n)
{
if (n->parent)
{
MovieNode** n_ptr = n->parent->leftChild == n ? &n->parent->leftChild : &n->parent->rightChild;
(*n_ptr) = n->rightChild; //can only be right child because in-order successor is used
}
n->rightChild->parent = n->parent;
if (n->isRed || n->rightChild->isRed)
{
n->rightChild->isRed = false;
}
else
{
rbDeleteFixup(n->rightChild);
}
delete n;
}

void MovieTree::rightRotate(MovieNode * x)
{
MovieNode* r = x->leftChild;
x->leftChild = r->rightChild;
if (x->leftChild != nil)
{
x->leftChild->parent = x;
}

r->parent = x->parent;
if (x->parent == NULL)
{
root = r;
}
else if (x->parent->leftChild == x)
{
x->parent->leftChild = r;
}
else
{
x->parent->rightChild = r;
}

r->rightChild = x;
x->parent = r;

nil->parent = NULL;
nil->leftChild = NULL;
nil->rightChild = NULL;
}

void MovieTree::rbDeleteFixup(MovieNode* node) //this function has a lot of side effects...
{
MovieNode* parent = node->parent;
if (parent)
{
MovieNode* s = getNodeSibling(parent, node);
if (s->isRed)
{
parent->isRed = true;
s->isRed = false;
node == parent->leftChild ? leftRotate(parent) : rightRotate(parent);

parent = node->parent;
s = getNodeSibling(parent, node);
}
if (!parent->isRed &&
!s->isRed &&
!s->leftChild->isRed &&
!s->rightChild->isRed)
{
s->isRed = true;
rbDeleteFixup(parent);
}
else
{
if (parent->isRed && !s->isRed && !s->leftChild->isRed && !s->rightChild->isRed)
{
s->isRed = true;
node->parent->isRed = false;
}
else
{
if ((node == parent->leftChild) && (!s->rightChild->isRed) && (s->leftChild->isRed))
{
s->isRed = true;
s->leftChild->isRed = false;

rightRotate(s);
parent = node->parent;
s = getNodeSibling(parent, node);
}
else if ((node == parent->rightChild) && (!s->leftChild->isRed))
{
s->isRed = true;
s->rightChild->isRed = false;

leftRotate(s);
parent = node->parent;
s = getNodeSibling(parent, node);
}
s->isRed = parent->isRed;
parent->isRed = false;
if (node == parent->leftChild)
{
s->rightChild->isRed = false;
leftRotate(parent);
}
else
{
s->leftChild->isRed = false;
rightRotate(parent);
}
}
}
}
else
{
root = node;
}
}

void MovieTree::rbTransplant(MovieNode * u, MovieNode * v)
{

}

int MovieTree::rbValid(MovieNode * node)
{
int lh = 0;
int rh = 0;

// If we are at a nil node just return 1
if (node == nil)
{
return 1;
}
else
{
// First check for consecutive red links.
if (node->isRed)
{
if (node->leftChild->isRed || node->rightChild->isRed)
{
cout << "This tree contains a red violation" << endl;
return 0;
}
}

// Check for valid binary search tree.
if ((node->leftChild != nil && node->leftChild->title.compare(node->title) > 0) || (node->rightChild != nil && node->rightChild->title.compare(node->title) < 0))
{
cout << "This tree contains a binary tree violation" << endl;
return 0;
}

// Deteremine the height of let and right children.
lh = rbValid(node->leftChild);
rh = rbValid(node->rightChild);

// black height mismatch
if (lh != 0 && rh != 0 && lh != rh)
{
cout << "This tree contains a black height violation" << endl;
return 0;
}

// If neither height is zero, incrament if it if black.
if (lh != 0 && rh != 0)
{
if (node->isRed)
return lh;
else
return lh + 1;
}

else
return 0;

}
}

void MovieTree::printEasy()
{
printWholeTree(root, "", true);
}

int MovieTree::countLongestPath(MovieNode *node)
{
int left = 1;
int right = 1;
if (node->rightChild != nil)
{
right += countLongestPath(node->rightChild);
}
if (node->leftChild != nil)
{
left += countLongestPath(node->leftChild);
}
return left > right ? left : right;
}

MovieNode* MovieTree::getNodeUncle(MovieNode* node)
{
MovieNode* grandparent = getNodeGrandparent(node);
if (grandparent)
{
return grandparent->leftChild == node->parent ? grandparent->rightChild : grandparent->leftChild;
}
cout << "node has no parent and/or grandparent, cannot have uncle" << endl;
return NULL;
}

MovieNode* MovieTree::getNodeGrandparent(MovieNode* node)
{
if (node->parent)
{
return node->parent->parent;
}
return NULL;
}

MovieNode* MovieTree::getNodeSibling(MovieNode* parent, MovieNode* node)
{
return parent->leftChild == node ? parent->rightChild : parent->leftChild;
}

void MovieTree::printWholeTree(MovieNode* n, string indent, bool last)
{
cout << indent;
if (last)
{
cout << "\-";
indent += " ";
}
else
{
cout << "|-";
indent += "| ";
}
if (n->isRed)
{
cout << redify(to_string(n->ranking)) << endl;
}
else
{
cout << n->ranking << endl;
}

if (n->leftChild != nil)
{
printWholeTree(n->leftChild, indent, n->rightChild == nil);
}
if (n->rightChild != nil)
{
printWholeTree(n->rightChild, indent, true);
}
}

string MovieTree::redify(string text)
{
return "" + text + "";
}

main.cpp

#include "MovieTree.h"
#include <sstream>
#include <fstream>
#include <iostream>
#include <string>

using namespace std;

void load_movies(MovieTree& tree, char* file_name);

int main(int argc, char** argv)
{
char* file_name = argv[1];
MovieTree tree;
load_movies(tree, file_name);
bool should_quit = false;
while (!should_quit)
{
cout << "======Main Menu======" << endl;
cout << "1. Find a movie" << endl;
cout << "2. Rent a movie" << endl;
cout << "3. Print the inventory" << endl;
cout << "4. Delete a movie" << endl;
cout << "5. Count the movies" << endl;
cout << "6. Count the longest path" << endl;
cout << "7. Quit" << endl;

char input;
cin >> input;
cin.ignore(1);
cin.clear();
string input_title;
switch (input)
{
default:
break;
case '1':
cout << "Enter title:" << endl;
getline(cin, input_title);
tree.findMovie(input_title);
break;
case '2':
cout << "Enter title:" << endl;
getline(cin, input_title);
tree.rentMovie(input_title);
break;
case '3':
tree.printMovieInventory();
break;
case '4':
cout << "Enter title:" << endl;
getline(cin, input_title);
tree.deleteMovieNode(input_title);
break;
case '5':
cout << "Tree contains: " << tree.countMovieNodes() << " movies." << endl;
break;
case '6':
cout << "Longest Path: " << tree.countLongestPath() << endl;
break;
case '7':
should_quit = true;
break;
case '8':
tree.printEasy();
break;
}
}
cout << "Goodbye!" << endl;
}

void load_movies(MovieTree& tree, char* file_name)
{
ifstream fs(file_name);

string line;
while (getline(fs, line))
{
stringstream ss(line);
string rank;
string title;
string year;
string quantity;
getline(ss, rank, ',');
getline(ss, title, ',');
getline(ss, year, ',');
getline(ss, quantity, ',');

tree.addMovieNode(stoi(rank), title, stoi(year), stoi(quantity));
}
}

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.