#include "iostream"
#define NIL NULL
typedef enum Color
{
RED = 0,
BLACK = 1
};
typedef struct Node {
int key;
Node* left;
Node* right;
Node* parent;
Color color;
}*PNODE;
typedef struct RBTree {
PNODE root;
Node* parent = NIL;
}*PRBTree;
void LeftRotate(PRBTree& T, PNODE x);
void RightRotate(PRBTree& T, PNODE x);
void RBInsertFixup(PRBTree& T, PNODE& z);
void RBInsert(PRBTree& T, PNODE& z);
void InOrderTree(PNODE root)
{
if (root)
{
InOrderTree(root->left);
std::cout << root->key << "----"<< (root->color == RED ? "红色":"黑色")<<std::endl;
InOrderTree(root->right);
}
}
void InitialNode(PNODE& x, int key);
int main(void)
{
PRBTree T = (PRBTree)malloc(sizeof(RBTree));
T->root = T->parent = NIL;
PNODE x1;
InitialNode(x1, 11);
PNODE x2;
InitialNode(x2, 2);
PNODE x3;
InitialNode(x3, 1);
PNODE x4;
InitialNode(x4, 12);
/*PNODE x5;
InitialNode(x5, 0);
PNODE x6;
InitialNode(x6, 5);
PNODE x7;
InitialNode(x7, 6);
PNODE x8;
InitialNode(x8, 7);*/
RBInsert(T, x1);
RBInsert(T, x2);
RBInsert(T, x3);
RBInsert(T, x4);
/*RBInsert(T, x5);
RBInsert(T, x6);
RBInsert(T, x7);
RBInsert(T, x8);*/
InOrderTree(T->root);
system("pause");
return 0;
}
void LeftRotate(PRBTree & T, PNODE x)
{
if (x->right != NIL)
{
PNODE y = x->right;
x->right = y->left;
if (y->left != NIL)
y->left->parent = x;
y->parent = x->parent;
if (x->parent == NIL)
T->root = y;
else if (x == x->parent->left)
x->parent->left = y;
else
x->parent->right = y;
y->left = x;
x->parent = y;
}
}
void RightRotate(PRBTree & T, PNODE x)
{
if (x->left != NIL)
{
PNODE y = x->left;
x->left = y->right;
if (y->right != NIL)
y->right->parent = x;
y->parent = x->parent;
if (x->parent == NIL)
T->root = y;
else if (x == x->parent->left)
x->parent->left = y;
else
x->parent->right = y;
y->right = x;
x->parent = y;
}
}
void RBInsertFixup(PRBTree & T, PNODE & z)
{
PNODE y;
while ((z->parent) && (z->parent->color == RED)) // 判断父结点是否存在
{
if ((z->parent == z->parent->parent->left))
{
y = z->parent->parent->right;
if (y && y->color == RED) // 要判断 父结点是否存在
{
z->parent->color = BLACK;
y->color = BLACK;
z->parent->parent->color = RED;
z = z->parent->parent;
}
else if( z == z->parent->right)
{
z = z->parent;
LeftRotate(T, z);
}
if (z->parent && z->parent->parent)
{
z->parent->color = BLACK;
z->parent->parent->color = RED;
RightRotate(T, z->parent->parent);
}
}
else if( (z->parent == z->parent->parent->right))
{
y = z->parent->parent->left;
if (y && y->color == RED)
{
y->color = BLACK;
z->parent->color = BLACK;
z->parent->parent->color = RED;
z = z->parent->parent;
}
else if ( z== z->parent->right )
{
z == z->parent;
LeftRotate(T, z);
}
if (z->parent && z->parent->parent)
{
z->parent->color = BLACK;
z->parent->parent->color = RED;
RightRotate(T, z->parent->parent);
}
}
}
T->root->color = BLACK;
}
void RBInsert(PRBTree & T, PNODE & z)
{
if (z == NIL)
return;
PNODE y = NIL;
PNODE x = T->root;
while ( x != NIL)
{
y = x;
if (z->key < x->key)
x = x->left;
else
x = x->right;
}
z->parent = y;
if (y == NIL)
{
T->root = z;
}
else if (z->key < y->key)
{
y->left = z;
}
else
y->right = z;
z->left = z->right = NIL;
z->color = RED;
RBInsertFixup(T, z);
}
void InitialNode(PNODE & x, int key)
{
x = (PNODE)malloc(sizeof(Node));
x->left = x->right = x->parent = NIL;
x->color = RED;
x->key = key;
}
