Question: Can someone help me make a delete function on my Red Black Tree on C++ Here is my code so far -----------stdc++.h------------------------ #include #include #include
Can someone help me make a delete function on my Red Black Tree on C++
Here is my code so far
-----------stdc++.h------------------------
#include #include
--------------main.h-------------------------
#include "stdc++.h"
using namespace std;
enum Color { RED, BLACK };
class RBT
{
struct node
{
std::string data;
bool color;
node *left, *right, *parent;
node(std::string data)
{
this->data = data;
left = right = parent = NULL;
}
};
node* root;
void inorder(node* root)
{
if (root == NULL)
{
return;
}
inorder(root->left);
cout << root->data << " ";
inorder(root->right);
}
node* insertBST(node* root, node* pt)
{
if (root == NULL)
{
return pt;
}
else if (pt->data < root->data)
{
root->left = insertBST(root->left, pt);
root->left->parent = root;
}
else if (pt->data > root->data)
{
root->right = insertBST(root->right, pt);
root->right->parent = root;
}
return root;
}
void leftrotation(node* root, node* pt)
{
node* right_child = pt->right;
pt->right = right_child->left;
if (pt->right != NULL)
{
pt->right->parent = pt;
}
right_child->parent = pt->parent;
if (pt->parent == NULL)
{
root = right_child;
}
else if (pt == pt->parent->left)
{
pt->parent->left = right_child;
}
else
{
pt->parent->right = right_child;
}
right_child->left = pt;
pt->parent = right_child;
}
void rightrotation(node* root, node* pt)
{
node* left_child = pt->left;
pt->left = left_child->right;
if (pt->left != NULL)
{
pt->left->parent = pt;
}
left_child->parent = pt->parent;
if (pt->parent == NULL)
{
root = left_child;
}
else if (pt == pt->parent->left)
{
pt->parent->left = left_child;
}
else
{
pt->parent->right = left_child;
}
left_child->right = pt;
pt->parent = left_child;
}
void fixInsertRBTree(node* pt)
{
node* parent = NULL;
node* grandparent = NULL;
node* uncle = NULL;
while ((pt != root) && (pt->color != BLACK) && (pt->parent->color == RED))
{
parent = pt->parent;
grandparent = pt->parent->parent;
//parent is left child
if (parent == grandparent->left)
{
uncle = grandparent->right;
//uncle is also red
if (uncle != NULL && uncle->color == RED)
{
grandparent->color = RED;
parent->color = BLACK;
uncle->color = BLACK;
pt = grandparent;
}
else
{
//pt is right child
if (pt == parent->right)
{
leftrotation(root, parent);
pt = parent;
parent = pt->parent;
}
//pt is left child
else
{
rightrotation(root, grandparent);
swap(parent->color, grandparent->color);
pt = parent;
}
}
}
//parent is right child
else
{
uncle = grandparent->left;
if (uncle != NULL && uncle->color == RED)
{
grandparent->color = RED;
parent->color = BLACK;
uncle->color = BLACK;
pt = grandparent;
}
else
{
//pt is left child
if (pt == parent->left)
{
leftrotation(root, parent);
pt = parent;
parent = pt->parent;
}
//pt is right child
else
{
rightrotation(root, grandparent);
swap(parent->color, grandparent->color);
pt = parent;
}
}
}
}
root->color = BLACK;
}
public:
RBT()
{
root = NULL;
}
void insert(std::string data)
{
node* pt = new node(data);
root = insertBST(root, pt);
fixInsertRBTree(pt);
}
void display()
{
inorder(root);
cout << endl;
}
};
----------main.cpp-----------------
#include "main.h"
int main()
{
RBT root;
std::string value;
std::ifstream file("ex04.txt");
std::string line;
if (file.is_open())
{
while (getline(file, line))
{
root.insert(line);
}
}
root.display();
system("PAUSE");
}
---------------ex04.txt----------------
apple
caste
comer
zebra
years
water
tears
words
other
?
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
Study Help