#include <stdio.h>
#include <stdlib.h>
//////////////////////////////////////////////////////////////////////
#define RED 0 // 红色节点
#define BLACK 1 // 黑色节点
typedef int Type;
// 红黑树的节点
typedef struct RBTreeNode{
unsigned char color; // 颜色(RED 或 BLACK)
Type key; // 关键字(键值)
struct RBTreeNode *left; // 左孩子
struct RBTreeNode *right; // 右孩子
struct RBTreeNode *parent; // 父结点
}Node, *RBTree;
// 红黑树的根
typedef struct rb_root{
Node *node;
}RBRoot;
RBRoot* create_rbtree();
Node* rb_parent(Node* n);
Node* create_node(Type key, Node *parent, Node *left, Node* right);
void left_rotate(RBRoot *root, Node *x);
void right_rotate(RBRoot *root, Node *y);
static void insert_fixup(RBRoot *root, Node *node);
int insert(RBRoot *root, Node *node);
static void inorder(Node *root);
static Node* rbtree_search(RBRoot* root, Type key);
void rb_delete_fixup(RBRoot *root, Node *parent,Node *node);
void rb_delete(RBRoot *root, Node *del);
//#define rb_is_black(r) ((r)->color==BLACK)
//#define rb_set_black(r) do { (r)->color = BLACK; } while (0)
//#define rb_set_red(r) do { (r)->color = RED; } while (0)
#define rb_set_parent(r,p) do { (r)->parent = (p); } while (0)
#define rb_set_color(r,c) do { (r)->color = (c); } while (0)
inline bool rb_is_red(Node *n) { if(n) return n->color==RED ; else return false; }
inline bool rb_is_black(Node*n) { return n->color==BLACK; }
inline void rb_set_black(Node*n) { n->color=BLACK; }
inline void rb_set_red(Node*n) { n->color=RED; }
bool rb_is_red(Node *node);
// #endif
//=========================================================================================================================
int main()
{
RBRoot* root =create_rbtree();
Node* n= create_node(3, NULL, NULL, NULL);
int a[100]={13,45,23,7,8,9,11,14,16,18, 29, 33, 31, 6, 3, 2, 42};
for( int i=0;i<10;i++)
{
n= create_node(a[i], NULL, NULL, NULL);
insert(root,n);
}
inorder(root->node);
printf("\n");
Node* del=rbtree_search(root,23);
if(del)
rb_delete(root,del);
inorder(root->node);
return 0;
}
static void inorder(Node *root)
{
if(root != NULL)
{
inorder(root->left);
printf("%d ", root->key);
inorder(root->right);
}
}
/*
* 创建红黑树，返回"红黑树的根"！
*/
RBRoot* create_rbtree()
{
RBRoot *root = (RBRoot *)malloc(sizeof(RBRoot));
root->node = NULL;
return root;
}
Node* create_node(Type key, Node *parent, Node *left, Node* right)
{
Node* p;
if ((p = (Node *)malloc(sizeof(Node))) == NULL)
return NULL;
p->key = key;
p->left = left;
p->right = right;
p->parent = parent;
p->color = BLACK; // 默认为黑色
return p;
}
/*
227 * 对红黑树的节点(x)进行左旋转
228 *
229 * 左旋示意图(对节点x进行左旋)： 右子变父,父变左子
230 * px px
231 * / /
232 * x y
233 * / \ --(左旋)--> / \ #
234 * lx y x ry
235 * / \ / \
236 * ly ry lx ly
237 *
238 *
239 */
void left_rotate(RBRoot *root, Node *x)
{
// 设置x的右孩子为y
Node *y = x->right;
// 将 “y的左孩子” 设为 “x的右孩子”；
// 如果y的左孩子非空，将 “x” 设为 “y的左孩子的父亲”
x->right = y->left;
if (y->left != NULL)
y->left->parent = x;
// 将 “x的父亲” 设为 “y的父亲”
y->parent = x->parent;
if (x->parent == NULL)
{
root->node = y; // 如果 “x的父亲” 是空节点，则将y设为根节点
}
else
{
if (x->parent->left == x)
x->parent->left = y; // 如果 x是它父节点的左孩子，则将y设为“x的父节点的左孩子”
else
x->parent->right = y; // 如果 x是它父节点的右孩子，则将y设为“x的父节点的右孩子”
}
// 将 “x” 设为 “y的左孩子”
y->left = x;
// 将 “x的父节点” 设为 “y”
x->parent = y;
}
/*
274 * 对红黑树的节点(y)进行右旋转
275 *
276 * 右旋示意图(对节点y进行左旋)：
277 * py py
278 * / /
279 * y x
280 * / \ --(右旋)--> / \ #
281 * x ry lx y
282 * / \ / \ #
283 * lx rx rx ry
284 *
285 */
void right_rotate(RBRoot *root, Node *y)
{
// 设置x是当前节点的左孩子。
Node *x = y->left;
// 将 “x的右孩子” 设为 “y的左孩子”；
// 如果"x的右孩子"不为空的话，将 “y” 设为 “x的右孩子的父亲”
y->left = x->right;
if (x->right != NULL)
x->right->parent = y;
// 将 “y的父亲” 设为 “x的父亲”
x->parent = y->parent;
if (y->parent == NULL)
{
root->node = x; // 如果 “y的父亲” 是空节点，则将x设为根节点
}
else
{
if (y == y->parent->right)
y->parent->right = x; // 如果 y是它父节点的右孩子，则将x设为“y的父节点的右孩子”
else
y->parent->left = x; // (y是它父节点的左孩子) 将x设为“x的父节点的左孩子”
}
// 将 “y” 设为 “x的右孩子”
x->right = y;
// 将 “y的父节点” 设为 “x”
y->parent = x;
}
/*
321 * 红黑树插入修正函数
322 *
326 * 参数说明：
327 * root 红黑树的根
328 * node 插入的结点
329 */
static void insert_fixup(RBRoot *root, Node *node)
{
Node *parent, *gparent;
//由于插入结点都是红色 如果插入结点的父结点是黑色,不影响红黑树平衡,无需调整 ,
//因此只需考虑父结点为红色的情况
// 若“父节点存在，并且父节点的颜色是红色”
while ((parent = node->parent) && rb_is_red(parent))
{
gparent = parent->parent; //因为父结点是红色,祖父必然是黑色
//情况1:叔叔结点存在且是红色
Node *uncle = gparent->left==parent? gparent->right:gparent->left;//父是左子,则叔是右子,反之
if (uncle && rb_is_red(uncle))
{
rb_set_black(uncle); //父辈都翻黑
rb_set_black(parent); //父辈都翻黑
rb_set_red(gparent); //祖辈翻红
node = gparent; //由于祖辈翻红, 会与祖辈的上辈违反红黑树的要求,因此 把祖辈设为当前结点,继续调整
continue;
}
//情况2: 以下是叔叔不存在或者为黑色的情况 其实 叔叔只能不存在,不可能为黑色
//情况2.1 若“父节点”是“祖父节点的左孩子”
if (parent == gparent->left)
{
//情况2.1.1 插入结点是父节点的右孩子
if (parent->right == node)
{
left_rotate(root,parent); //先把父左旋 变成 左-左使之与2.1.2称为一样的形态 调整还没有完成, 到2.1.2进一步调整
Node *tmp= parent; //左旋后,父子地位互换, 要把父设为当前结点node,而node变为父,才能在2.1.2中得到进一步处理
parent = node;
node = tmp;
}
//情况2.1.2 插入结点是父节点的左孩子 左-左
{
rb_set_black(parent); //父亲变黑
rb_set_red(gparent); //祖父变红
right_rotate(root, gparent); //把祖父右旋转
}
}
//情况2.2 若“父节点”是“祖父节点的右孩子”
else
{
//情况2.2.1 插入结点是父节点的左孩子
if (parent->left == node)
{
right_rotate(root,parent); //先把父右旋 变 右-左 为右-右 使之与2.2.2一样的形态,到2.2.2中进一步调整
Node *tmp= parent; //右旋后,父子地位互换, 要把父设为当前结点node,而node变为父
parent = node;
node = tmp;
}
//情况2.2.2 插入结点是父节点的右孩子
{
rb_set_black(parent); //父亲变黑
rb_set_red(gparent); //祖父变红
left_rotate(root, gparent); //把祖父左旋转
}
}
}
// 将根节点设为黑色
rb_set_black(root->node);
}
/*
407 * 添加节点：将节点(node)插入到红黑树中
408 *
409 * 参数说明：
410 * root 红黑树的根
411 * node 插入的结点
412 */
int insert(RBRoot *root, Node *node)
{
Node *y = NULL;
Node *x = root->node;
// 1. 将红黑树当作一颗二叉查找树，将节点添加到二叉查找树中。
while (x != NULL) //y迭代当前结点,x迭代当前结点的左右子结点
{
y = x;
if (node->key < x->key)
x = x->left;
else if (node->key > x->key)
x = x->right;
else //找到相等的key了
return -1; //key值已经存在 插入失败
}
node->parent = y;
if (y != NULL)
{
if (node->key < y->key)
y->left = node; // 情况2：若“node所包含的值” < “y所包含的值”，则将node设为“y的左孩子”
else
y->right = node; // 情况3：(“node所包含的值” >= “y所包含的值”)将node设为“y的右孩子”
}
else
{
root->node = node; // 情况1：若y是空节点，则将node设为根
}
// 2. 设置插入节点的颜色为红色
node->color = RED;
// 3. 将它重新修正为一颗红黑树
insert_fixup(root, node);
return 1;
}
void rb_delete(RBRoot *root, Node *del)
{
Node *child=NULL, *parent;
int color;
// 先处理被删除节点的"左右孩子都不为空"的情况,找到它的替代点, 再把替代点变为真正要删除的结点
if ( (del->left!=NULL) && (del->right!=NULL) )
{
//搜寻替代结点
Node *replace = del;
replace = replace->right;
while (replace->left != NULL)
replace = replace->left;
// (1)用替代结点替换删除结点
if(del->parent)
{
if(del->parent->left==del) del->parent->left=replace;
else del->parent->right=replace;
}
else root->node = replace;
//记录替代节点的父亲和孩子
parent =replace->parent;
child = replace->right; //替代结点只有右子
color = replace->color;
//替代结点脱离原来的关系
if(parent==del) // 如果替代结点的父亲恰好就是删除结点
{
parent= replace; // 此时关系是 del->右-> replace->右->child 所以 child无需和替代结点R脱离 ,替代点就是child的父亲
}
else{
if(child ) child->parent = parent;
parent->left =child;
// (2)用替换结点变为删除结点// // 放到这里是因为避免出现删除结点是替代结点的父亲的情况,从而导致替代结点的右子结点指向自己
replace->right = del->right;
del->right->parent = replace;
}
// 经过(1)(2)(3)三步才完成替换了删除结点
//替代删除结点为替代结点一共有6个操作，分别是设置左子结点（2个），右子结点（2个），父亲结点（2个）
// (3) 用替换结点变为删除结点
replace->parent = del->parent;
replace->color = del->color;
replace->left = del->left;
del->left->parent = replace;
if(color==BLACK)
rb_delete_fixup(root, parent,child) ;
}
//剩下都是被删点为单子树的情况
//情况 A) 被删除结点是红色 则被删除结点的左或着右孩子必为空 直接删除,不需调整
//情况 B) 被删除结点为黑 被删除的黑结点如有孩子, 则孩子必是红色 删除后 孩子变黑既可,后续无需调整
//情况 C) 被删除的黑结点无孩子 ,要修正
else
{
if(del->right)
child =del->right ;
else child = del->left;
parent=del->parent;
color = del->color;
//删除点从树中脱离
if(child) {
child->parent =parent;
child->color =BLACK; //被删除的黑结点如有孩子, 则孩子必是红色, 删去黑结点, 让孩子变黑达到平衡
}
if(parent) {
if(parent->left==del) parent->left = child;
else parent->right = child;
}
else root->node =child;
if(color==BLACK && child==NULL) //黑结点且无孩子,则需要修正
rb_delete_fixup(root, parent,child) ;
}
free(del);
rb_set_black(root->node);
}
/*
501 * 红黑树删除修正函数
502 *
503 * 在从红黑树中删除插入节点之后(红黑树失去平衡)，再调用该函数；
504 * 目的是将它重新塑造成一颗红黑树。
505 *
506 * 参数说明：
507 * root 红黑树的根
508 * node 待修正的节点
509 */
inline void rb_delete_fixup(RBRoot *root, Node *parent,Node *node)
{
Node* brother; //被删除黑结点必有兄弟,否则以parent为根的子树不能平衡
while( ( !node || rb_is_black(node) ) && node!=root->node )
{
/**
* 分为四种情况，分别是
* 1.兄弟结点是红色
* 2.兄弟结点是黑色，其子结点也是黑色
* 3.兄弟结点是黑色，其左子结点为红色，右子结点任意颜色
* 4.兄弟结点是黑色，其左子结点任意颜色，右子结点为红色
*/
//分两大情况, 1 删除结点是父亲左孩子, 2 删除结点是父亲右孩子
if (parent->left == node)
{
brother= parent->right; //兄弟是右
if (rb_is_red(brother) ) //1 若兄弟是红色, 为保证平衡,则兄弟必有两个黑子树
{
brother->color=BLACK;
parent->color =RED;
left_rotate(root, parent); //旋转后,仍不平衡,此时,删除结点的兄弟变了,是原兄弟的左黑子树 ,因此兄弟要重设
brother = parent->right; //重设兄弟, 现在的兄弟是黑色,转到下面黑兄弟的情况执行
}
//以下都是黑兄弟的情况 根据平衡条件 黑兄弟只能有红孩子. 分有左红孩子, 有右红孩子,没孩子三种情况
if( brother->left && rb_is_red(brother->left) ) //3 兄弟有左红孩子
{
brother->left->color = parent->color; // brother的左红孩子变为父亲的颜色
rb_set_black(parent); //父亲变黑
right_rotate(root, brother); //兄弟右旋转, 左红孩子上位
left_rotate(root,parent); //父亲左旋,补充左边的黑子数目
break;
}
else if(brother->right && rb_is_red(brother->right) ) //4 兄弟有右红孩子
{
brother->color = parent->color; // brother变为父亲的颜色
rb_set_black(brother->right); //兄弟右红孩子变黑
rb_set_black(parent); //父亲变黑
left_rotate(root,parent); //父亲左旋,补充左边的黑子数目
break;
}
else // 2 黑兄弟只有黑孩子,或者没孩子
{
//又分两种情况 父为红, 父为黑
if( rb_is_red(parent) ) // 父为红
{
rb_set_black(parent); //父亲变黑 补充删去的黑结点
rb_set_red(brother); //为保证平衡, 兄弟变为红
break;
}
else // 父为黑
{
rb_set_red(brother); //为保证平衡, 兄弟只能变为红
node =parent; //父亲作为子树比其他树要少一个黑点了,因此要把 父亲当作新的待平衡点, 继续循环 上溯继续平衡
}
}
}
//2大情况 删除结点是父亲右孩子
else
{
brother= parent->left; //兄弟是左
if (rb_is_red(brother) ) //1 若兄弟是红色, 为保证平衡,则兄弟必有两个黑孩子
{
rb_set_black(brother);
rb_set_red(parent);
right_rotate(root, parent); //旋转后,仍不平衡,此时,删除结点的兄弟变了,是黑兄弟 ,因此兄弟要重设
brother = parent->left; //重设兄弟, 转到下面兄弟为黑兄弟的情况执行
}
//以下都是黑兄弟的情况 根据平衡条件 黑兄弟只能有红孩子. 分有左红孩子, 有右红孩子,没孩子三种情况
if( brother->left && rb_is_red(brother->left) ) //兄弟有左红孩子
{
brother->color = parent->color; // brother变为父亲的颜色
rb_set_black(brother->left); //兄弟左红孩子变黑
rb_set_black(parent); //父亲变黑
right_rotate(root,parent); //父亲右旋,补充右边的黑子数目
break;
}
else if( brother->right && rb_is_red(brother->right)) //兄弟有右红孩子
{
brother->right->color = parent->color; // brother的右红孩子变为父亲的颜色
rb_set_black(parent); //父亲变黑
left_rotate(root, brother); //兄弟左旋转, 右红孩子上位
right_rotate(root,parent); //父亲右旋,补充右边的黑子数目
break;
}
else //黑兄弟没孩子的情况
{
//又分两种情况 父为红, 父为黑
if( rb_is_red(parent) ) // 父为红
{
rb_set_black(parent); //父亲变黑 补充删去的黑结点
rb_set_red(brother); //为保证平衡, 兄弟变为红
break;
}
else // 父为黑
{
rb_set_red(brother); //为保证平衡, 兄弟只能变为红
node =parent; //父亲作为子树比其他树要少一个黑点了,因此要把 父亲当作新的待平衡点,上溯继续平衡
}
}
}
} //循环结束
//if (node)
// rb_set_black(node);
}
Node* rbtree_search(RBRoot* root, Type key)
{
Node* x=root->node;
while ((x!=NULL) && (x->key!=key))
{
if (key < x->key)
x = x->left;
else
x = x->right;
}
return x;
}