#include <iostream>
class CRedBlackTree {
enum colorType {red, black};
struct node {
colorType color;
int data;
node* left;
node* right;
node* parent;
};
/**
* Strores the adress of root node of tree
*
* @type node*
*/
node* root;
/**
* gets sibling of node
*
* @param node*
* @return node* sibling of node n
*/
node* sibling(node*) const;
/**
* get grandparent node of current node
*
* @param node*
* @return node*
*/
node* grandparent(node*) const;
/**
* get uncle node of current node
*
* @param node*
* @return node*
*/
node* uncle(node*) const;
/**
* Right rotate the node
*
* @return true | false
*/
bool rightRotate(node*);
/**
* Left rotate the node
*
* @return true | false
*/
bool leftRotate(node*);
/**
* Add item into tree but don't correct balance
*
* @return void
*/
node* add(const int);
/**
* Change color two node for each
*
* @return void
*/
void changeColor(node*&, node*&);
/**
* Print all node of tree
*
* @param node* the root node of tree
*/
friend const void print(const node*);
public:
/**
* Constructor of class
*/
CRedBlackTree();
/**
* Destructor of class
*/
~CRedBlackTree();
/**
* Search exist key in tree
*
* @param int
* @return bool
*/
bool search(const int);
/**
* Insert new node into root tree
*
* @return void
*/
void insert(const int);
/**
* Delete node from tree
*
* @return void
*/
void deleteNode(const int);
/**
* Free all allocated memory
*
* @return void
*/
void clear();
/**
* Print all node
*
* @return void
*/
const node* getRootNode() const;
/**
* Test the left and right rotate function
*
* @return void
*/
void testRotate();
};
CRedBlackTree::CRedBlackTree() {
root = NULL;
}
CRedBlackTree::~CRedBlackTree() {
clear();
}
bool CRedBlackTree::search(int key) {
node* temp = root;
while (NULL != temp) {
if (key < temp->data) {
temp = temp->left;
} else if (key > temp->data) {
temp = temp->right;
} else if (key == temp->data) {
return true;
}
}
return false;
}
CRedBlackTree::node* CRedBlackTree::sibling(node* n) const {
if (NULL == n->parent || NULL == n) {
return NULL;
}
if (n == n->parent->left) {
return n->parent->right;
} else if (n == n->parent->right) {
return n->parent->left;
}
}
CRedBlackTree::node* CRedBlackTree::grandparent(node* n) const {
if (NULL == n->parent || NULL == n) {
return NULL;
}
return n->parent->parent;
}
CRedBlackTree::node* CRedBlackTree::uncle(node* n) const {
if (NULL == grandparent(n) || NULL == n) return NULL;
if (grandparent(n)->left == n->parent) {
return grandparent(n)->right;
}
return grandparent(n)->left;
}
bool CRedBlackTree::leftRotate(node* n) {
node* r = n->right;
if (NULL == r) {
return false;
}
if (NULL != r->left) {
r->left->parent = n;
}
n->right = r->left;
r->left = n;
if (root == n) {
root = r;
r->parent = NULL;
n->parent = r;
} else {
node* p = n->parent;
if (NULL == p) {
return false;
}
if (n == p->right) {
p->right = r;
} else if (n == p->left) {
p->left = r;
}
n->parent = r;
r->parent = p;
}
return true;
}
bool CRedBlackTree::rightRotate(node* n) {
node* l = n->left;
std::cout<<n<<std::endl;
if (NULL == l) {
return false;
}
if (NULL != l->right) {
l->right->parent = n;
}
n->left = l->right;
l->right = n;
if (root == n) {
root = l;
l->parent = NULL;
n->parent = l;
} else {
node* p = n->parent;
if (NULL == p) {
return false;
}
if (n == p->right) {
p->right = l;
} else if (n == p->left) {
p->left = l;
}
n->parent = l;
l->parent = p;
}
return true;
}
void CRedBlackTree::testRotate() {
node* temp = root;
node* last;
while (NULL != temp) {
last = temp;
temp = temp->left;
}
rightRotate(last);
}
CRedBlackTree::node* CRedBlackTree::add(const int key) {
node* newNode = new node;
newNode->data = key;
newNode->left = NULL;
newNode->right = NULL;
newNode->parent = NULL;
newNode->color = red;
if (NULL == root) {
root = newNode;
return newNode;
}
node* last;
node* temp = root;
while (NULL != temp) {
if (key < temp->data) {
last = temp;
temp = temp->left;
} else {
last = temp;
temp = temp->right;
}
}
newNode->parent = last;
if (key < last->data) {
last->left = newNode;
} else last->right = newNode;
return newNode;
}
void CRedBlackTree::changeColor(node*& a, node*& b) {
colorType temp;
temp = a->color;
a->color = b->color;
b->color = temp;
}
void CRedBlackTree::insert(const int key) {
node* n;
if (!search(key)) {
n = this->add(key);
} else {
n = root;
while (key != n->data) {
if (key > n->data) {
n = n->right;
} else {
n = n->left;
}
}
}
// case 1: add into root tree
if (NULL == n->parent) {
n->color = black;
return;
}
// case 2: color of insert-node is black
if (black == n->parent->color) {
return;
}
// case 3: color of uncle and parent is red, then we change color to black
if (NULL != uncle(n) && red == uncle(n)->color) {
n->parent->color = black;
uncle(n)->color = black;
grandparent(n)->color = red;
if (root == uncle(n)) {
grandparent(n)->color = black;
return;
}
return insert(grandparent(n)->data);
}
// case 4: when insert-node, parent and grandparent are not the same direction
if (n == n->parent->right && n->parent == grandparent(n)->left) {
leftRotate(n->parent);
n = n->left;
return insert(n->data);
} else if (n == n->parent->left && n->parent == grandparent(n)->right) {
rightRotate(n->parent);
n = n->right;
return insert(n->data);
}
// case 5: when insert-node, parent and grandparent are the same direction
n->parent->color = black;
grandparent(n)->color = red;
if (n == n->parent->left && n->parent == grandparent(n)->left) {
rightRotate(grandparent(n));
return insert(n->data);
} else if (n == n->parent->right && n->parent == grandparent(n)->right) {
leftRotate(grandparent(n));
return insert(n->data);
}
}
void CRedBlackTree::deleteNode(const int key) {
if (false == search(key)) {
std::cout<<"Not match key"<<std::endl;
return;
}
node* matchNode = root;
while (key != matchNode->data) {
if (matchNode->data < key) {
matchNode = matchNode->right;
} else if (matchNode->data > key) {
matchNode = matchNode->left;
}
}
node* parent = matchNode->parent;
if (NULL == matchNode->left && NULL == matchNode->right) {
if (parent->data > key) {
parent->left = NULL;
} else {
parent->right = NULL;
}
delete matchNode;
} else if (NULL == matchNode->left && NULL != matchNode->right) {
if (black == matchNode->color) {
if (red == matchNode->right->color) {
if (parent->data > matchNode->data) {
parent->left = matchNode->right;
matchNode->right->parent = parent->left;
} else {
parent->right = matchNode->right;
matchNode->right->parent = parent->right;
}
matchNode->right->color = black;
return deleteNode(matchNode->data);
}
if (NULL == matchNode) {
return;
}
if (red == sibling(matchNode)->color) {
matchNode->parent->color = red;
sibling(matchNode)->color = black;
if (matchNode == matchNode->parent->left) {
leftRotate(matchNode->parent);
} else {
rightRotate(matchNode->parent);
}
return deleteNode(matchNode->data);
}
if (black == matchNode->parent->color &&
black == sibling(matchNode)->color &&
black == sibling(matchNode)->left->color &&
black == sibling(matchNode)->right->color) {
sibling(matchNode)->color = red;
return deleteNode(matchNode->data);
} else return deleteNode(matchNode->data);
if (red == matchNode->parent->color &&
black == sibling(matchNode)->color &&
black == sibling(matchNode)->left->color &&
black == sibling(matchNode)->right->color) {
sibling(matchNode)->color = red;
matchNode->parent->color = black;
} else return deleteNode(matchNode->data);
if (matchNode == matchNode->parent->left &&
black == sibling(matchNode)->color&&
red == sibling(matchNode)->left->color &&
black == sibling(matchNode)->right->color)
{
sibling(matchNode)->color = red;
sibling(matchNode)->left->color = black;
rightRotate(sibling(matchNode));
return deleteNode(matchNode->data);
}
else if (matchNode == matchNode->parent->right &&
black == sibling(matchNode)->color&&
red == sibling(matchNode)->right->color &&
black == sibling(matchNode)->left->color)
{
sibling(matchNode)->color = red;
sibling(matchNode)->right->color = black;
leftRotate(sibling(matchNode));
return deleteNode(matchNode->data);
}
sibling(matchNode)->color = matchNode->parent->color;
matchNode->parent->color = black;
if (matchNode == matchNode->parent->left) {
sibling(matchNode)->right->color = black;
leftRotate(matchNode->parent);
return deleteNode(matchNode->data);
} else {
sibling(matchNode)->left->color = black;
rightRotate(matchNode->parent);
return deleteNode(matchNode->data);
}
}
delete matchNode;
} else if (NULL != matchNode->left && NULL == matchNode->right) {
if (parent->data > matchNode->data) {
parent->left = matchNode->left;
matchNode->left->parent = parent->left;
} else {
parent->right = matchNode->left;
matchNode->left->parent = parent->right;
}
delete matchNode;
}
// In this case the balance of tree is not changed
else if (NULL != matchNode->left && NULL != matchNode->right) {
node* temp = matchNode->left;
node* parentTemp;
while (NULL != temp) {
parentTemp = temp;
temp = temp->right;
}
int saved = parentTemp->data;
deleteNode(parentTemp->data);
matchNode->data = saved;
}
}
const CRedBlackTree::node* CRedBlackTree::getRootNode() const {
return root;
}
void CRedBlackTree::clear() {
if (root == NULL) {
delete root;
return;
}
node* tempLeft = root->left;
node* tempRight = root->right;
delete root;
root = tempLeft;
clear();
root = tempRight;
clear();
}
const void print(const CRedBlackTree::node* root) {
if (NULL == root) {
std::cout<<"NIL"<<std::endl;
return;
}
std::cout<<"node: "<<root->data<<" with color: "<<root->color
<<" parent: "<<(NULL == root->parent ? 0 : root->parent->data)
<<std::endl;
print(root->left);
print(root->right);
}
int main() {
CRedBlackTree root;
root.insert(11);
root.insert(2);
root.insert(14);
root.insert(1);
root.insert(7);
root.insert(15);
root.insert(5);
root.insert(8);
root.insert(4);
root.testRotate();
root.deleteNode(15);
print(root.getRootNode());
return 0;
}