【数据结构】红黑树 C语言代码
2024-08-26 15:40:23
连看带写花了三天，中途被指针引用搞得晕晕乎乎的。 插入和删除的调整过程没有看原理，只看了方法，直接照着写的。
看了两份资料，一份是算法导论第12-13章， 另一份是网上的资料http://blog.csdn.net/v_JULY_v/article/details/6105630
下面C代码是我根据 算法导论的伪码写的。
#include <stdio.h>
#include <stdlib.h>
#include <string.h> typedef int DataType; typedef struct RBNode
{
RBNode *parent, *left, *right; //指向结点的父结点、左右孩子结点
DataType key; //结点数据
int color; //颜色 红（r） 或 黑（b）
}RBNode; //定义红黑树结点 RBNode Nil;
RBNode * nil = &Nil; void left_rotate( RBNode * &T, RBNode * x) //左旋 x一定不能有引用 因为如果引用后 x与y->parent就是等价的了， y->parent改变 x就会改变
{
RBNode * y;
y = x->right;
/************第一部分 y的左孩子 与 x间关联*************/
x->right = y->left; //x认右孩子
if(y->left != nil)
{
y->left->parent = x; //孩子认parent
}
/************第一部分 y的左孩子 与 x间关联 end*************/ /************第二部分 y 与 x的parent 关联*************/
y->parent = x->parent; //y认 x的parent为自己的parent //y的parent与x的地址是一样的 int isroot = ;
if(x->parent == nil) //x的parent根据自己的情况 认y为左或右孩子
{
isroot = ;
}
else if(x == x->parent->left)
{
x->parent->left = y;
}
else
{
x->parent->right = y;
}
/************第二部分 y 与 x的parent 关联 end*************/ /************第部分 x 与 y的关联 *************/
y->left = x; //y认x为孩子
x->parent = y; //x认y为parent
/************第部分 x 与 y的关联 end*************/
if(isroot == )
{
T = y;
}
} void right_rotate(RBNode * &T, RBNode * x) //右旋
{
RBNode * y;
y = x->left; x->left = y->right; if(y->right != nil)
{
y->right->parent = x;
} y->parent = x->parent;
int isroot = ;
if(x->parent == nil)
{
isroot = ;
}
else if(x == x->parent->right)
{
x->parent->right = y;
}
else
{
x->parent->left = y;
} y->right = x;
x->parent = y; if(isroot == )
{
T = y;
}
} void rb_insert_fixup(RBNode * &T, RBNode * z) //红黑树插入后的调整 注意z不能要引用 因为调整的过程中z的值作为位置标记会改变 但我们不希望树的结构因为z而变化
{ RBNode * y;
while(z->parent->color == 'r')
{
if(z->parent == z->parent->parent->left) //z的parent是左子的情况
{
//copy(z->parent->parent->right, y);
y = z->parent->parent->right;
if(y->color == 'r') //情况1 z的parent和uncle都是红色 把这两个红色染成黑色 把grandparent染成红色 令z = grandparent 再次循环
{
y->color = 'b';
z->parent->color = 'b';
z->parent->parent->color = 'r';
z = z->parent->parent;
}
else if(z == z->parent->right) //当前节点的父节点是红色,叔叔节点是黑色，当前节点是其父节点的右子 对策：当前节点的父节点做为新的当前节点，以新当前节点为支点左旋。
{
z = z->parent;
left_rotate(T, z);
}
else //当前节点的父节点是红色,叔叔节点是黑色，当前节点是其父节点的左子 解法：父节点变为黑色，祖父节点变为红色，在祖父节点为支点右旋
{
z->parent->color = 'b';
z->parent->parent->color = 'r';
right_rotate(T, z->parent->parent);
}
}
else //z的parent是右子的情况
{
y = z->parent->parent->left;
if(y->color == 'r')
{
z->parent->color = 'b';
y->color = 'b';
z->parent->parent->color = 'r';
z = z->parent->parent;
}
else if(z == z->parent->left)
{
z = z->parent;
right_rotate(T, z);
}
else
{
z->parent->color = 'b';
z->parent->parent->color = 'r';
left_rotate(T, z->parent->parent);
}
}
} if(z->parent == nil)
{
z->color = 'b';
return;
}
else
{
return;
}
} void rb_insert(RBNode * &T, RBNode * z) //红黑树 插入工作 注意 z不要有引用
{
RBNode * y = nil;
RBNode * x = T;
while(x != nil) //找到z适当的插入位置
{
y = x;
if(z->key < x->key)
x = x->left;
else
x = x->right;
} z->parent = y;
if(y == nil) //parent 认孩子总是麻烦一些的 毕竟要区分是左是右 是否为根
{
T = z;
}
else if(z->key < y->key)
{
y->left = z;
}
else
{
y->right = z;
} //对新插入的点处理， 染成红色
z->left = nil;
z->right = nil;
z->color = 'r'; //调整红黑树
rb_insert_fixup(T, z); } RBNode * rb_findmax(RBNode * z) //找到以z为树根的树的最大结点
{
while(z->right != nil)
{
z = z->right;
}
return z;
} RBNode * rb_findmin(RBNode * z) //找到以z为树根的树的最小结点
{
while(z->left != nil)
{
z = z->left;
}
return z;
} RBNode * rb_successor(RBNode * z) //找z的后继
{
if(z->right != nil)
{
return rb_findmin(z->right); //如果z的right不为空 后继就是z的右子树中最小的点
}
else
{
RBNode * y = z->parent;
while(y != nil && z == y->right)
{
z = y;
y = y->parent;
}
return y;
}
} void rb_delete_fixup(RBNode * &T, RBNode * x)
{
RBNode* w;
while(x != T && x->color == 'b')
{
if(x == x->parent->left)
{
w = x->parent->right;
if(w->color == 'r')
{
w->color = 'b';
x->parent->color = 'r';
left_rotate(T, x->parent); w = x->parent->right;
}
if(w->left->color == 'b' && w->right->color == 'b')
{
w->color = 'r';
x = x->parent;
}
else
{
if(w->right->color == 'b')
{
w->left->color = 'b';
w->color = 'r';
right_rotate(T, w);
w = x->parent->right;
} w->color = x->parent->color;
x->parent->color = 'b';
w->right->color = 'b';
left_rotate(T, x->parent);
x = T;
}
}
else
{
w = x->parent->left;
if(w->color == 'r')
{
w->color = 'b';
x->parent->color = 'r';
right_rotate(T, x->parent); w = x->parent->left;
}
if(w->left->color == 'b' && w->right->color == 'b')
{
w->color = 'r';
x = x->parent;
}
else if(w->left->color == 'b')
{
if(w->left->color == 'b')
{
w->right->color = 'b';
w->color = 'r';
left_rotate(T, w);
w = x->parent->left;
} w->color = x->parent->color;
x->parent->color = 'b';
w->left->color = 'b';
right_rotate(T, x->parent);
x = T;
}
}
}
x->color = 'b';
} RBNode * rb_delete(RBNode * &T, RBNode * z) //红黑树 删除节点
{
//y 确定删除的结点是z还是z的后继
RBNode * y;
y = (z->left == nil || z->right == nil) ? z : rb_successor(z); //x 是y的非nil子女 或是 nil
RBNode * x;
x = (y->left != nil) ? y->left : y->right; //无条件令x的parent = y的parent
x->parent = y->parent; //删除y 建立x与y的parent之间的联系
if(y->parent == nil)
{
T = x;
}
else if(y == y->parent->left)
{
y->parent->left = x;
}
else
{
y->parent->right = x;
} //如果y!=z 将y的数据拷贝到z
if(y != z)
{
//z的颜色不变
z->parent = y->parent;
z->left = y->left;
z->right = y->right;
z->key = y->key;
} if(y->color == 'b')
{
rb_delete_fixup(T, x);
}
return y;
}
int main()
{
nil->color = 'b'; //叶子结点都是黑的
nil->left = nil;
nil->right = nil;
nil->parent = nil;
RBNode *T;
T = nil;
RBNode data[];
for(int i = ; i < ; i++)
{
data[i].key = i + ;
RBNode * z = &data[i];
rb_insert(T, z);
} RBNode * x = T->left->left;
rb_delete(T, x); return ;
}
最新文章
- 岛屿（洛谷 U5399）
- swift3.0 coredata 的使用
- 如何把 excel 设为文本格式？
- Yii中Ajax的使用，如收藏功能
- STL之deque（双向队列）
- iOS系统自带的 UIAlertView 自动旋转的实现
- jenkins学习之自动打包构建nodejs应用
- [数据清洗]- Pandas 清洗“脏”数据（三）
- Tree Recovery（由先、中序列构建二叉树）
- python介绍篇
- linux 存在多个版本的情况下，切换python版本
- mysql 日期 字符串
- Linux中断管理 (1)Linux中断管理机制
- Notepad++快捷使用
- word/excel/cad中插入二维码
- Linux 下挂载新硬盘方法
- JavaScript之作用域
- 蓝图Tips
- 补充照片：某基同学使用Bing词典
- java第一次考试