内容纲要
参考博文
http://blog.csdn.net/eric491179912/article/details/6179908
http://blog.csdn.net/v_JULY_v/article/details/6109153
http://blog.csdn.net/v_JULY_v/article/details/6114226
http://blog.csdn.net/v_JULY_v/article/details/6124989
可视化数据结构
#define DeBUG
#include <iostream>
#include <queue>
#include <stack>
#include <malloc.h>
using namespace std ;
#define zero {0}
#define RED 0
#define BLACK 1
struct RBTree
{
RBTree *right;
RBTree *left;
RBTree *parent;
bool color;
int key;
RBTree(int d)
{
key = d;
color = RED;
right = left = NULL;
parent = NULL;
}
};
void PreOrder(RBTree *p)
{
if (p != NULL)
{
printf("(%d)%s ", p->key, p->color == BLACK ? "黑" : "红");
PreOrder(p->left);
PreOrder(p->right);
}
}
void InOrder(RBTree *p)
{
if (p != NULL)
{
InOrder(p->left);
printf("(%d)%s ", p->key, p->color == BLACK ? "黑" : "红");
InOrder(p->right);
}
}
void PostOrder(RBTree *p)
{
if (p != NULL)
{
PostOrder(p->left);
PostOrder(p->right);
printf("(%d)%s ", p->key, p->color == BLACK ? "黑" : "红");
}
}
int Depth(RBTree *current)//深度
{
int Depthleft;
int Depthright;
int dp = 0;
if (current == NULL)
{
return 0;
}
else
{
Depthleft = Depth(current->left);
Depthright = Depth(current->right);
dp = 1 + (Depthright >= Depthleft ? Depthright : Depthleft);
}
return dp;
}
void layerOrder(RBTree *p)
{
if (p != NULL)
{
queue<RBTree *>st;
st.push(p);
while (!st.empty())
{
RBTree *now = st.front();
st.pop();
if ( now->parent != NULL)
{
if (now->parent->right == now)
printf("(%d->%d)%s ", now->parent->key, now->key, now->color == BLACK ? "黑" : "红");
else
printf("(%d<-%d)%s ", now->parent->key, now->key, now->color == BLACK ? "黑" : "红");
}
else
printf("(%d-%d)%s ", 0, now->key, now->color == BLACK ? "黑" : "红");
if (now->left != NULL)
{
st.push(now->left);
}
if (now->right != NULL)
{
st.push(now->right);
}
}
}
printf("\n");
}
//左旋
/*-----------------------------------------------------------
| node right
| / \ ==> / \
| a right node y
| / \ / \
| b y a b
-----------------------------------------------------------*/
RBTree *LeftRotate(RBTree *node, RBTree *root)
{
RBTree *right = node->right;
if (node->right = right->left)
{
right->left->parent = node;
}
right->left = node;
if ( right->parent = node->parent)
{
if (node == node->parent->right)
node->parent->right = right;
else
node->parent->left = right;
}
else
root = right;
node->parent = right;
return root;
}
//右旋
/*-----------------------------------------------------------
| node left
| / \ / \
| left y ==> a node
| / \ / \
| a b b y
-----------------------------------------------------------*/
RBTree *RightRotate(RBTree *node, RBTree *root)
{
RBTree *left = node->left;
if (node->left = left->right)
{
left->right->parent = node;
}
left->right = node;
if (left->parent = node->parent)
{
if (node == node->parent->right)
node->parent->right = left;
else
node->parent->left = left;
}
else
root = left;
node->parent = left;
return root;
}
RBTree *Search(int key, RBTree *root, RBTree **parent)
{
RBTree *node = root;
int ret;
while (node)
{
if (parent)
*parent = node;
ret = node->key - key;
if (0 < ret)
node = node->left;
else if (0 >= ret)//key唯一时取消=
node = node->right;
else
return node;
}
return NULL;
}
RBTree *GetNode(int key, RBTree *root)
{
RBTree *node = root;
int ret;
while (node)
{
ret = node->key - key;
if (0 < ret)
node = node->left;
else if (0 > ret)
node = node->right;
else
return node;
}
return NULL;
}
RBTree *RB_insert_rebalance(RBTree *node, RBTree *root)
{
RBTree *parent, *gparent, *uncle;
while ((parent = node->parent) && parent->color == RED)
{
// if(node->key==8)
// {
// layerOrder(root);
// printf("\n");
// }
gparent = parent->parent;
if (parent == gparent->left)
{
uncle = gparent->right;
if (uncle && uncle->color == RED)//情况1
{
uncle->color = BLACK;
parent->color = BLACK;
gparent->color = RED;
node = gparent;
}
else//情况2,3，右黑叔叔
{
if (parent->right == node)
{
root = LeftRotate(parent, root);
swap(parent, node);
}
parent->color = BLACK;
gparent->color = RED;
root = RightRotate(gparent, root);
}
}
else//对称情况
{
uncle = gparent->left;
if (uncle && uncle->color == RED)
{
uncle->color = BLACK;
parent->color = BLACK;
gparent->color = RED;
node = gparent;
}
else//左黑叔叔
{
if (parent->left == node)
{
root = RightRotate(parent, root);
swap(parent, node);
}
parent->color = BLACK;
gparent->color = RED;
root = LeftRotate(gparent, root);
}
}
}
root->color = BLACK;
return root;
}
RBTree *Insert(int key, RBTree *root)
{
RBTree *parent = NULL, *node;
if (Search(key, root, &parent))
{
//return root;//通过键值唯一确定一个数据
}
node = new RBTree(key);
node->parent = parent;
if (parent)
{
if (parent->key > key)
parent->left = node;
else
parent->right = node;
}
else
root = node;
return RB_insert_rebalance(node, root);
}
RBTree *RB_del_rebalance(RBTree *node, RBTree *parent, RBTree *root)
{
RBTree *other, *o_left, *o_right;
while ((!node || node->color == BLACK) && node != root)
{
if (parent->left == node)
{
other = parent->right;
if (other->color == RED) //情况1：x兄弟节点是红色
{
other->color = BLACK;
parent->color = RED;
root = LeftRotate(parent, root);
other = parent->right;
}
else if ((!other->left || other->left->color == BLACK) &&
(!other->right || other->right->color == BLACK))
//情况2：x的兄弟节点为黑色且w的两个孩子为黑色
{
other->color = RED;
node = parent;
parent = node->parent;
}
else
{
//情况3：x的兄弟w是黑色的，且w的左孩子是红色，w的右孩子是黑色。
if (!other->right || other->right->color == BLACK
)
{
if ((o_left = other->left))
{
o_left->color = BLACK;
}
other->color = RED;
root = RightRotate(other, root);
other = parent->right;
}
//情况4：x的兄弟节点w是黑色，且w的右孩子为红
other->color = parent->color;
parent->color = BLACK;
//change
other->right->color = BLACK;
root = LeftRotate(parent, root);
node = root;
break;
}
}
else
{
other = parent->left;
if (other->color == RED) //1
{
other->color = BLACK;
parent->color = RED;
root = RightRotate(parent, root);
other = parent->left;
}
//2
if ((!other->left || other->left->color == BLACK) &&
(!other->right || other->right->color == BLACK))
{
other->color = RED;
node = parent;
parent = node->parent;
}
else
{
//3
if (!other->left || other->left->color == BLACK)
{
if ((o_right = other->right))
{
o_right->color = BLACK;
}
other->color = RED;
root = LeftRotate(other, root);
other = parent->left;
}
//4
other->color = parent->color;
parent->color = BLACK;
//change
other->left->color = BLACK;
root = RightRotate(parent, root);
node = root;
break;
}
}
}
if (node)
node->color = BLACK;
return root;
}
RBTree *delnode(int key, RBTree *root)
{
RBTree *child, *parent, *old, *left, *right, *node;
bool color;
if (!(node = GetNode(key, root)))
{
printf("key %d is not exist!\n", key);
return root;
}
old = node;
if (node->left && node->right)
{
node = node->left;
while ((right = node->right) != NULL)
//用左边的最右节点替代
{
node = right;
}
child = node->left;
parent = node->parent;
color = node->color;
if (child)
{
child->parent = parent;
}
if (parent)
{
if (parent->left == node)
parent->left = child;
else
parent->right = child;
}
else
root = child;
if (node->parent == old)
parent = node;
node->parent = old->parent;
node->color = old->color;
node->right = old->right;
node->left = old->left;
if (old->parent)
{
if (old->parent->left == old)
old->parent->left = node;
else
old->parent->right = node;
}
else
root = node;
if (old->left)
old->left->parent = node;
if (old->right)
old->right->parent = node;
}
else
{
if (node->left == NULL)
child = node->right;
else if (node->right == NULL)
child = node->left;
parent = node->parent;
color = node->color;
if (child)
child->parent = parent;
if (parent)
{
if (parent->left == node)
parent->left = child;
else
parent->right = child;
}
else
root = child;
}
delete(old);
if (color == BLACK)
root = RB_del_rebalance(child, parent, root);
return root;
}
int main()
{
#ifdef DeBUGs
freopen("C:\\Users\\Sky\\Desktop\\1.in", "r", stdin);
#endif
char op[10];
RBTree *root = NULL;
// int N = 15;
// for (int i = 1; i <= N; i++)
// {
// root = Insert(i, root);
// }
// layerOrder(root);
// PreOrder(root);
// puts("");
// InOrder(root);
// puts("");
// PostOrder(root);
// puts("");
// printf("深度%d\n", Depth(root));
int key;
do
{
printf("请输入操作（i）插入（d）删除:\n");
scanf("%s", op);
if (op[0] == 'd')
{
printf("输入数值：");
scanf("%d", &key);
root = delnode(key, root);
printf("删除后结果：（层序遍历）\n");
layerOrder(root);
printf("深度%d\n", Depth(root));
}
else
{
printf("输入数值：");
scanf("%d", &key);
root = Insert(key, root);
printf("插入后结果：（层序遍历）\n");
layerOrder(root);
printf("深度%d\n", Depth(root));
}
}
while (true);
return 0;
}