Question

USING the built in linux.c linux/rbtree.h can someone build a red and black tree searching, printing, adding and deleting for Players name with their personal ID searching() search for players name an...

USING the built in linux.c

linux/rbtree.h

can someone build a red and black tree searching, printing, adding and deleting for Players name with their personal ID

searching() search for players name and ID if it doesnt exist add to the RB tree

delete () players off the list

print() prints out all the players

0 0
Add a comment Improve this question Transcribed image text
Answer #1

#include <bits/stdc++.h>
using namespace std;
  
enum Color {RED, BLACK};
  
struct Node
{
int data;
bool color;
Node *left, *right, *parent;
  
// Constructor
Node(int data)
{
this->data = data;
left = right = parent = NULL;
}
};
  
// Class to represent Red-Black Tree
class RBTree
{
private:
Node *root;
protected:
void rotateLeft(Node *&, Node *&);
void rotateRight(Node *&, Node *&);
void fixViolation(Node *&, Node *&);
public:
// Constructor
RBTree() { root = NULL; }
void insert(const int &n);
void inorder();
void levelOrder();
};
  
// A recursive function to do level order traversal
void inorderHelper(Node *root)
{
if (root == NULL)
return;
  
inorderHelper(root->left);
cout << root->data << " ";
inorderHelper(root->right);
}
  
/* A utility function to insert a new node with given key
in BST */
Node* BSTInsert(Node* root, Node *pt)
{
/* If the tree is empty, return a new node */
if (root == NULL)
return pt;
  
/* Otherwise, recur down the tree */
if (pt->data < root->data)
{
root->left = BSTInsert(root->left, pt);
root->left->parent = root;
}
else if (pt->data > root->data)
{
root->right = BSTInsert(root->right, pt);
root->right->parent = root;
}
  
/* return the (unchanged) node pointer */
return root;
}
  
// Utility function to do level order traversal
void levelOrderHelper(Node *root)
{
if (root == NULL)
return;
  
std::queue<Node *> q;
q.push(root);
  
while (!q.empty())
{
Node *temp = q.front();
cout << temp->data << " ";
q.pop();
  
if (temp->left != NULL)
q.push(temp->left);
  
if (temp->right != NULL)
q.push(temp->right);
}
}
  
void RBTree::rotateLeft(Node *&root, Node *&pt)
{
Node *pt_right = pt->right;
  
pt->right = pt_right->left;
  
if (pt->right != NULL)
pt->right->parent = pt;
  
pt_right->parent = pt->parent;
  
if (pt->parent == NULL)
root = pt_right;
  
else if (pt == pt->parent->left)
pt->parent->left = pt_right;
  
else
pt->parent->right = pt_right;
  
pt_right->left = pt;
pt->parent = pt_right;
}
  
void RBTree::rotateRight(Node *&root, Node *&pt)
{
Node *pt_left = pt->left;
  
pt->left = pt_left->right;
  
if (pt->left != NULL)
pt->left->parent = pt;
  
pt_left->parent = pt->parent;
  
if (pt->parent == NULL)
root = pt_left;
  
else if (pt == pt->parent->left)
pt->parent->left = pt_left;
  
else
pt->parent->right = pt_left;
  
pt_left->right = pt;
pt->parent = pt_left;
}
  
// This function fixes violations caused by BST insertion
void RBTree::fixViolation(Node *&root, Node *&pt)
{
Node *parent_pt = NULL;
Node *grand_parent_pt = NULL;
  
while ((pt != root) && (pt->color != BLACK) &&
(pt->parent->color == RED))
{
  
parent_pt = pt->parent;
grand_parent_pt = pt->parent->parent;
  
/* Case : A
Parent of pt is left child of Grand-parent of pt */
if (parent_pt == grand_parent_pt->left)
{
  
Node *uncle_pt = grand_parent_pt->right;
  
/* Case : 1
The uncle of pt is also red
Only Recoloring required */
if (uncle_pt != NULL && uncle_pt->color == RED)
{
grand_parent_pt->color = RED;
parent_pt->color = BLACK;
uncle_pt->color = BLACK;
pt = grand_parent_pt;
}
  
else
{
/* Case : 2
pt is right child of its parent
Left-rotation required */
if (pt == parent_pt->right)
{
rotateLeft(root, parent_pt);
pt = parent_pt;
parent_pt = pt->parent;
}
  
/* Case : 3
pt is left child of its parent
Right-rotation required */
rotateRight(root, grand_parent_pt);
swap(parent_pt->color, grand_parent_pt->color);
pt = parent_pt;
}
}
  
/* Case : B
Parent of pt is right child of Grand-parent of pt */
else
{
Node *uncle_pt = grand_parent_pt->left;
  
/* Case : 1
The uncle of pt is also red
Only Recoloring required */
if ((uncle_pt != NULL) && (uncle_pt->color == RED))
{
grand_parent_pt->color = RED;
parent_pt->color = BLACK;
uncle_pt->color = BLACK;
pt = grand_parent_pt;
}
else
{
/* Case : 2
pt is left child of its parent
Right-rotation required */
if (pt == parent_pt->left)
{
rotateRight(root, parent_pt);
pt = parent_pt;
parent_pt = pt->parent;
}
  
/* Case : 3
pt is right child of its parent
Left-rotation required */
rotateLeft(root, grand_parent_pt);
swap(parent_pt->color, grand_parent_pt->color);
pt = parent_pt;
}
}
}
  
root->color = BLACK;
}
  
// Function to insert a new node with given data
void RBTree::insert(const int &data)
{
Node *pt = new Node(data);
  
// Do a normal BST insert
root = BSTInsert(root, pt);
  
// fix Red Black Tree violations
fixViolation(root, pt);
}
  
// Function to do inorder and level order traversals
void RBTree::inorder() { inorderHelper(root);}
void RBTree::levelOrder() { levelOrderHelper(root); }
  
// Driver Code
int main()
{
RBTree tree;
  
tree.insert(7);
tree.insert(6);
tree.insert(5);
tree.insert(4);
tree.insert(3);
tree.insert(2);
tree.insert(1);
  
cout << "Inoder Traversal of Created Tree\n";
tree.inorder();
  
cout << "\n\nLevel Order Traversal of Created Tree\n";
tree.levelOrder();
  
return 0;
}

Add a comment
Know the answer?
Add Answer to:
USING the built in linux.c linux/rbtree.h can someone build a red and black tree searching, printing, adding and deleting for Players name with their personal ID searching() search for players name an...
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Not the answer you're looking for? Ask your own homework help question. Our experts will answer your question WITHIN MINUTES for Free.
Similar Homework Help Questions
  • Part B (BI). Implement a Red-Black tree with only operation Insert(). Your program should read from...

    Part B (BI). Implement a Red-Black tree with only operation Insert(). Your program should read from a file that contain positive integers and should insert those numbers into the RB tree in that order. Note that the input file will only contain distinct integers. Print your tree by level using positive values for Black color and negative values for Red color Do not print out null nodes. Format for a node: <Node_value>, <Parent_value>). For example, the following tree is represented...

  • Implement a program that: reads a number of personal records (for example, using PERSON struct from...

    Implement a program that: reads a number of personal records (for example, using PERSON struct from the earlier lab) from the standard input, creates a database of personal records, allows for adding new entries to the database, allows for deleting entries from the database, includes functions to acquire a record of personal data, and includes functions to display (print) a single selected record from the database, and also allows for printing all records in the database. NOTES: if name is...

  • Question 2: Finding the best Scrabble word with Recursion using java Scrabble is a game in...

    Question 2: Finding the best Scrabble word with Recursion using java Scrabble is a game in which players construct words from random letters, building on words already played. Each letter has an associated point value and the aim is to collect more points than your opponent. Please see https: //en.wikipedia.org/wiki/Scrabble for an overview if you are unfamiliar with the game. You will write a program that allows a user to enter 7 letters (representing the letter tiles they hold), plus...

ADVERTISEMENT
Free Homework Help App
Download From Google Play
Scan Your Homework
to Get Instant Free Answers
Need Online Homework Help?
Ask a Question
Get Answers For Free
Most questions answered within 3 hours.
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT