学习笔记：C++红黑树
·
一、红黑树简介
红黑树是一种自平衡的二叉平衡树，是一种高效的查找树。它是由 Rudolf Bayer 于1972年发明，在当时被称为对称二叉 B树(symmetric binary B-trees)。后来，在1978年被 Leo J. Guibas 和 Robert Sedgewick 修改为如今的红黑树。
红黑树具有良好的效率，它可在 O(logN) 时间内完成查找、增加、删除等操作。因此，红黑树在业界应用很广泛。
二、红黑树性质
1.节点是红色或黑色。
2.根是黑色。
3.所有叶子都是黑色（叶子是NIL节点）。
4.每个红色节点必须有两个黑色的子节点。
5.从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。
三、红黑树的简易生成
typedef struct _rbtree_node{
KEY_TYPE key;
void *value;
unsigned char color;
struct _rbtree_node *right;
struct _rbtree_node *left;
struct _rbtree_node *parent;
}rbtree_node;
typedef struct _rbtree{
struct _rbtree_node *root;
struct _rbtree_node *nil;
}rbtree;
如果遇到需要同时生成多种不同类型的红黑树的情况，比如说为"ready","wait","sleep","exit"四种状态生成红黑树，可以选择创建模板来简便的生成。
typedef int KEY_TYPE;
#define RBTREE_ENTRY(name,type)
struct name{
unsigned char color;
struct type *right;
struct type *left;
struct type *parent;
};
typedef struct thread{
KEY_TYPE key;
void *value;
#if 1
unsigned char color;
struct _rbtree_node *right;
struct _rbtree_node *left;
struct _rbtree_node *parent;
#else
RBTREE_ENTRY(,thread) ready;
RBTREE_ENTRY(,thread) wait;
RBTREE_ENTRY(,thread) sleep;
RBTREE_ENTRY(,thread) exit;
#endif
}rbtree_node;
typedef struct _rbtree{
struct _rbtree_node *root;
struct _rbtree_node *nil;
}rbtree;四、红黑树的旋转
1. 左旋代码实现
void rbtree_left_rotate(rbtree *T,rbtree_node *x){
rbtree_node *y = x->right;
x->right = y->left;
if(y->left != T->nil){ //判断y的左子节点是否为叶子节点
y->left->parent = x;
}
y->parent = x->parent;
if(x->parent == T->nil){ //判断x是否为根节点
T->root = y;
}else if(x == x->parent->left){
x->parent->left = y; //判断x是左子树还是右子树
}else{
x->parent->right = y;
}
y->left = x;
x->parent = y;
}可以看出，在旋转过程中共有三条指针断开并重新连接，分别是：x指向父节点的指针、x指向y的指针，y指向左子树的指针。
2.右旋代码实现
void rbtree_right_rotate(rbtree *T,rbtree_node *y){
rbtree_node *x = y->right;
y->right = x->left;
if(x->left != T->nil){
x->left->parent = y;
}
x->parent = y->parent;
if(y->parent == T->nil){
T->root = x;
}else if(y == y->parent->left){
y->parent->left = x;
}else{
y->parent->right = x;
}
x->left = y;
y->parent = x;
}五、红黑树的插入
void rbtree_insert(rbtree *T,rbtree_node *z){
rbtree_node *y = T->nil;
rbtree_node *x = T->root;
while (x != T->nil){
y = x;
if(z -> key < x->key){
x = x -> left;
}else if(z->key > x->key){
x = x->right;
}else{ //Exist
}
}
if(y == T->nil){
T->root = z;
}else{
if (y->key > z->key){
y->left = z;
}else{
y->right = z;
}
}
z->parent = y;
z->left = T->nil;
z->right = T->nil;
z->color = RED;
rbtree_insert_fixup(T,z);
}这里插入节点的过程与二叉树别无二致，但是要注意一个问题就是插入节点的颜色问题：
红黑树插入后要满足红黑树的性质，所以需要进行颜色修正，在插入时，预设z为红色，先满足“黑高”的性质。
void rbtree_insert_fixup(rbtree *T,rbtree_node *z){
while(z->parent->color == RED){ //z的父节点为红色
if(z->parent == z->parent->parent->left){ //判断z的父节点是否为左子树
rbtree_node *y = z->parent->parent->right; //y为z的叔父节点
if(y->color == RED){ //若z的叔父节点y为红色
z->parent->color = BLACK;
y->color = BLACK;
z->parent->parent->color = RED;
z = z->parent->parent;
}else{
if(z == z->parent->right){ //若z为右子树
z = z->parent;
rbtree_left_rotate(T,z); //以z的父节点进行左旋
}
if(z == z->parent->left){ //若z为左子树
z->parent->color = BLACK;
z->parent->parent->color = RED;
rbtree_right_rotate(T,z->parent->parent);//变色后进行右旋
}
}
}
}
情况1：
父节点是祖父节点的左子树的情况
1.叔结点是红色的
将父节点与叔节点变为黑色，祖父节点变为蓝色，而后进行下一次迭代（即z = z->parent->parent)
2.叔节点是黑色的，且当前节点为右子树
以z的父节点进行左旋，而后进行下一次迭代（z = z->parent）。
3.叔节点是黑色的，而且当前节点为左子树
将z的父节点变为黑色，z的祖父节点变为红色，而后以z的祖父节点进行右旋。
简单来讲，红黑树在插入过程中通过旋转来实现自平衡，避免出现二叉树退化为链表的情况。
六、完整代码
#define RED 0
#define BLACK 1
typedef int KEY_TYPE;
#define RBTREE_ENTRY(name,type)
struct name{
unsigned char color;
struct type *right;
struct type *left;
struct type *parent;
};
typedef struct _rbtree_node{
KEY_TYPE key;
void *value;
#if 1
unsigned char color;
struct _rbtree_node *right;
struct _rbtree_node *left;
struct _rbtree_node *parent;
#else
RBTREE_ENTRY(,rb_node) node;
#endif
}rbtree_node;
typedef struct _rbtree{
struct _rbtree_node *root;
struct _rbtree_node *nil;
}rbtree;
void rbtree_left_rotate(rbtree *T,rbtree_node *x){
rbtree_node *y = x->right;
x->right = y->left;
if(y->left != T->nil){
y->left->parent = x;
}
y->parent = x->parent;
if(x->parent == T->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 rbtree_right_rotate(rbtree *T,rbtree_node *y){
rbtree_node *x = y->right;
y->right = x->left;
if(x->left != T->nil){
x->left->parent = y;
}
x->parent = y->parent;
if(y->parent == T->nil){
T->root = x;
}else if(y == y->parent->left){
y->parent->left = x;
}else{
y->parent->right = x;
}
x->left = y;
y->parent = x;
}
void rbtree_insert_fixup(rbtree *T,rbtree_node *z){
while(z->parent->color == RED){ //z的父节点为红色
if(z->parent == z->parent->parent->left){ //判断z的父节点是否为左子树
rbtree_node *y = z->parent->parent->right; //y为z的叔父节点
if(y->color == RED){ //若z的叔父节点y为红色
z->parent->color = BLACK;
y->color = BLACK;
z->parent->parent->color = RED;
z = z->parent->parent;
}else{
if(z == z->parent->right){ //若z为右子树
z = z->parent;
rbtree_left_rotate(T,z); //以z的父节点进行左旋
}
if(z == z->parent->left){ //若z为左子树
z->parent->color = BLACK;
z->parent->parent->color = RED;
rbtree_right_rotate(T,z->parent->parent);//变色后进行右旋
}
}
}
}
}
void rbtree_insert(rbtree *T,rbtree_node *z){
rbtree_node *y = T->nil;
rbtree_node *x = T->root;
while (x != T->nil){
y = x;
if(z -> key < x->key){
x = x -> left;
}else if(z->key > x->key){
x = x->right;
}else{ //Exist
}
}
if(y == T->nil){
T->root = z;
}else{
if (y->key > z->key){
y->left = z;
}else{
y->right = z;
}
}
z->parent = y;
z->left = T->nil;
z->right = T->nil;
z->color = RED;
rbtree_insert_fixup(T,z);
}更多推荐
6
0- 0
已为社区贡献1条内容
所有评论(0)