/*
* RBT.h
*
* Created on: Nov 30, 2015
* Author: chris
*/
#pragma once
#include
enum NodeColor{RED, BLACK};
typedef int KeyType;
struct RBTNode{
RBTNode *right, *left, *p;
NodeColor color;
KeyType key;
RBTNode() : right(NULL), left(NULL),
p(NULL), color(RED),key(0) {}
};
struct RBTree{
RBTNode * root, * nil;
RBTree() {}
};
bool RBTreeCreate(RBTree & T);
void RBTreeDestroy(RBTree & T);
bool RBTreeSearchKey(RBTree & T, KeyType key, RBTNode*& p);
bool RBTreeInsert(RBTree & T, KeyType key);
bool RBTreeDelete(RBTree & T, KeyType key);
void RBTreeWalkThrough(RBTree & T);
/*
* RBT.cpp
*
* Created on: Nov 30, 2015
* Author: chris
*/
#include "RBT.h"
#include
using namespace std;
bool RBTreeCreate(RBTree & T)
{
T.nil = new RBTNode();
if (!T.nil) return false;
T.nil->color = BLACK;
T.nil->left = T.nil->right = T.nil->p = T.nil;
T.root = T.nil;
return true;
}
void RBTreeClearSubTree(RBTree & T, RBTNode* & sub)
{
if (sub == T.nil) return;
RBTreeClearSubTree(T, sub->left);
RBTreeClearSubTree(T, sub->right);
delete sub;
sub = T.nil;
}
void RBTreeDestroy(RBTree & T)
{
RBTreeClearSubTree(T, T.root);
delete T.nil;
T.nil = T.root = NULL;
}
bool RBTreeSearchKey(RBTree & T, KeyType key, RBTNode*& p)
{
// search key in T, if found p => key, if not found, p => ins pos
p = T.nil;
RBTNode * x = T.root;
while (x != T.nil) {
p = x;
if (key < x->key)
x = x->left;
else if (key > x->key)
x = x->right;
else break;
} // endw.
if (x != T.nil) // found
return true;
else // not found
return false;
}
void Left_Rotate(RBTree & T, RBTNode * x)
{
RBTNode * y = x->right; // set y
// turn y's left subtree into x's right subtree.
x->right = y->left;
if (y->left != T.nil)
y->left->p = x;
// y take the place of x.
y->p = x->p;
if (x->p == T.nil)
T.root = y;
else if (x == x->p->left)
x->p->left = y;
else
x->p->right = y;
y->left = x;
x->p = y;
} // end rot left
void Right_Rotate(RBTree & T, RBTNode * x)
{
RBTNode * y = x->left; // set y
// turn y's right subtree into x's left subtree.
x->left = y->right;
if (y->right != T.nil)
y->right->p = x;
// y take the place of x
y->p = x->p;
if (x->p == T.nil)
T.root = y;
else if (x == x->p->left)
x->p->left = y;
else
x->p->right = y;
y->right = x;
x->p = y;
} // end rot right
void RB_Insert_FixUp(RBTree & T, RBTNode * z)
{
RBTNode * y = T.nil;
while (z->p->color == RED) {
if (z->p == z->p->p->left) {
y = z->p->p->right; // uncle
if (y->color == RED) {
// uncle is red, repaint and continue.
z->p->color = BLACK;
y->color = BLACK;
z->p->p->color = RED;
z = z->p->p;
}
else {
// uncle is black, rotate and break.
if (z == z->p->right) { // LR case
z = z->p;
Left_Rotate(T, z);
}
// LL case
z->p->color = BLACK;
z->p->p->color = RED;
Right_Rotate(T, z->p->p);
}
} // end if z.p == z.p.p.left
else {
y = z->p->p->left; // uncle
if (y->color == RED) {
// uncle is red, repaint and continue.
z->p->color = BLACK;
y->color = BLACK;
z->p->p->color = RED;
z = z->p->p;
}
else {
// uncle is black, rotate and break.
if (z == z->p->left) {
// RL case
z = z->p;
Right_Rotate(T, z);
}
// RR case
z->p->color = BLACK;
z->p->p->color = RED;
Left_Rotate(T, z->p->p);
}
} // end if z.p == z.p.p.right
} // endw z.p red
T.root->color = BLACK;
}
bool RBTreeInsert(RBTree & T, KeyType key)
{
RBTNode * y;
if (RBTreeSearchKey(T, key, y))
return false;
// load
RBTNode * z = new RBTNode();
if (!z) return false;
z->key = key;
// insert
z->p = y;
if (y == T.nil)
T.root = z;
else if (z->key < y->key)
y->left = z;
else
y->right = z;
z->left = T.nil;
z->right = T.nil;
z->color = RED;
RB_Insert_FixUp(T, z);
return true;
}
void RB_Transplant(RBTree & T, RBTNode* u, RBTNode* v)
{
if (u->p == T.nil)
T.root = v;
else if (u == u->p->left)
u->p->left = v;
else
u->p->right = v;
v->p = u->p;
}
RBTNode * RB_Tree_Minimum(RBTree & T, RBTNode * z)
{
RBTNode * y = z;
while (z != T.nil) {
y = z;
z = z->left;
} // endw
return y;
}
void RB_Delete_FixUp(RBTree & T, RBTNode * x)
{
RBTNode * w = T.nil;
while (x != T.root && x->color == BLACK) {
if (x == x->p->left) {
w = x->p->right;
// case 1: w is red, x.p is black
if (w->color == RED) {
w->color = BLACK;
x->p->color = RED;
Left_Rotate(T, x->p);
w = x->p->right;
}
// case 2: w is black, with black left and right siblings
if (w->left->color == BLACK && w->right->color == BLACK) {
w->color = RED;
x = x->p;
}
else {
// case 3: w is black, with red left.
if (w->right->color == BLACK) {
w->left->color = BLACK;
w->color = RED;
Right_Rotate(T, w);
w = x->p->right;
}
// case 4: w is black, with red right or both.(RR case)
w->color = x->p->color;
x->p->color = BLACK;
w->right->color = BLACK;
Left_Rotate(T, x->p);
x = T.root;
}
} // end if x == x.p.left
else {
w = x->p->left;
// case 1: w is red
if (w->color == RED) {
w->color = BLACK;
x->p->color = RED;
Right_Rotate(T, x->p);
w = x->p->left;
}
// case 2: w is black, with black left and right
if (w->right->color == BLACK && w->left->color == BLACK) {
w->color = RED;
x = x->p;
}
else {
// case 3: w is black, with red right
if (w->left->color == BLACK) {
w->right->color = BLACK;
w->color = RED;
Left_Rotate(T, w);
w = x->p->left;
}
// case 4: w is black, with red left or both(LL case)
w->color = x->p->color;
x->p->color = BLACK;
w->left->color = BLACK;
Right_Rotate(T, x->p);
x = T.root;
}
} // end if x == x.p.right
} // endw
x->color = BLACK;
}
bool RBTreeDelete(RBTree & T, KeyType key)
{
RBTNode *x, *y, *z;
if (!RBTreeSearchKey(T, key, z))
return false;
y = z; // node to be deleted.
NodeColor y_original_color = y->color;
// z has one or no child.
if (z->left == T.nil) {
x = z->right;
RB_Transplant(T, z, z->right);
}
else if (z->right == T.nil) {
x = z->left;
RB_Transplant(T, z, z->left);
}
else{
// z has two children.
y = RB_Tree_Minimum(T, z->right); // successor of z
y_original_color = y->color;
// y move into z's position.
// x is the only branch(right) from original y
x = y->right;
// splice right branch
if (y->p == z)
x->p = y; // important
else {
RB_Transplant(T, y, y->right);
y->right = z->right;
y->right->p = y;
}
// splice left branch
RB_Transplant(T, z, y);
y->left = z->left;
y->left->p = y;
y->color = z->color;
} // endif z has two children
delete y;
// treat x as a newly inserted branch,
// and check property violation.
if (y_original_color == BLACK)
// black height deficiency between root and x
RB_Delete_FixUp(T, x);
}
void _RB_WalkThrough(RBTree & T, RBTNode* sub)
{
static int depth = 0;
if (sub == T.nil) return;
++depth;
bool running = true;
while (running) {
cout << "Now at: " << (void*)sub << "; depth: " << depth << endl;
cout << "Cur Color: " << sub->color << "; Cur Key: " << sub->key << endl;
cout << "Parent: " << (void*)sub->p << "; Left: " << (void*)sub->left << "; Right: " << (void*)sub->right << endl;
// oper
int ans = 0;
do{
cout << "1: to left; 2: to right; 3: back up" << endl;
cin >> ans;
if (ans >= 1 && ans <= 3)
break;
} while (true);
switch (ans)
{
case 1:
if (sub->left != T.nil)
_RB_WalkThrough(T, sub->left);
else
cout << "Failed." << endl;
break;
case 2:
if (sub->right != T.nil)
_RB_WalkThrough(T, sub->right);
else
cout << "Failed." << endl;
break;
case 3:
running = false;
break;
} // endsw
} // endw
--depth;
}
void RBTreeWalkThrough(RBTree & T)
{
_RB_WalkThrough(T, T.root);
}
/*
* Main.cpp
*
* Created on: Oct 31, 2015
* Author: chris
*/
#include
#include "RBT.h"
using namespace std;
int main(void)
{
RBTree T;
if (!RBTreeCreate(T)) return 0;
RBTreeInsert(T, 11);
RBTreeInsert(T, 2);
RBTreeInsert(T, 14);
RBTreeInsert(T, 1);
RBTreeInsert(T, 7);
RBTreeInsert(T, 15);
RBTreeInsert(T, 5);
RBTreeInsert(T, 8);
RBTreeInsert(T, 4);
RBTreeWalkThrough(T);
RBTreeDestroy(T);
system("pause");
return 0;
}