Can someone help me make a delete function on my Red Black Tree on C++ Here is m
ID: 3905161 • Letter: C
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 <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
--------------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
?
Explanation / Answer
void RBTree::fixDeleteRBTree(Node *&node) { if (node == nullptr) return; if (node == root) { root = nullptr; return; } if (getColor(node) == RED || getColor(node->left) == RED || getColor(node->right) == RED) { Node *child = node->left != nullptr ? node->left : node->right; if (node == node->parent->left) { node->parent->left = child; if (child != nullptr) child->parent = node->parent; setColor(child, BLACK); delete (node); } else { node->parent->right = child; if (child != nullptr) child->parent = node->parent; setColor(child, BLACK); delete (node); } } else { Node *sibling = nullptr; Node *parent = nullptr; Node *ptr = node; setColor(ptr, DOUBLE_BLACK); while (ptr != root && getColor(ptr) == DOUBLE_BLACK) { parent = ptr->parent; if (ptr == parent->left) { sibling = parent->right; if (getColor(sibling) == RED) { setColor(sibling, BLACK); setColor(parent, RED); rotateLeft(parent); } else { if (getColor(sibling->left) == BLACK && getColor(sibling->right) == BLACK) { setColor(sibling, RED); if(getColor(parent) == RED) setColor(parent, BLACK); else setColor(parent, DOUBLE_BLACK); ptr = parent; } else { if (getColor(sibling->right) == BLACK) { setColor(sibling->left, BLACK); setColor(sibling, RED); rotateRight(sibling); sibling = parent->right; } setColor(sibling, parent->color); setColor(parent, BLACK); setColor(sibling->right, BLACK); rotateLeft(parent); break; } } } else { sibling = parent->left; if (getColor(sibling) == RED) { setColor(sibling, BLACK); setColor(parent, RED); rotateRight(parent); } else { if (getColor(sibling->left) == BLACK && getColor(sibling->right) == BLACK) { setColor(sibling, RED); if (getColor(parent) == RED) setColor(parent, BLACK); else setColor(parent, DOUBLE_BLACK); ptr = parent; } else { if (getColor(sibling->left) == BLACK) { setColor(sibling->right, BLACK); setColor(sibling, RED); rotateLeft(sibling); sibling = parent->left; } setColor(sibling, parent->color); setColor(parent, BLACK); setColor(sibling->left, BLACK); rotateRight(parent); break; } } } } if (node == node->parent->left) node->parent->left = nullptr; else node->parent->right = nullptr; delete(node); setColor(root, BLACK); } } Node* RBTree::deleteBST(Node *&root, int data) { if (root == nullptr) return root; if (data data) return deleteBST(root->left, data); if (data > root->data) return deleteBST(root->right, data); if (root->left == nullptr || root->right == nullptr) return root; Node *temp = minValueNode(root->right); root->data = temp->data; return deleteBST(root->right, temp->data); } void RBTree::deleteValue(int data) { Node *node = deleteBST(root, data); fixDeleteRBTree(node); }Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.