红黑树构建,插入,删除以及代码

晚枫歌F

471人浏览 · 2025-08-18 12:05:35

晚枫歌F · 2025-08-18 12:05:35 发布

红黑树

完整代码见文末
概念：

每个节点都有颜色，红色或者黑色
根节点是黑色
每个叶子节点是黑色
如果一个节点是红色，那么它的两个子节点都是黑色
对每个节点来说，从该节点到其子孙节点的所有路径上都有相同的黑色节点。

操作：

左旋与右旋
插入
删除
遍历
查询

注意:

红黑树在插入节点之前就已经是一颗红黑树了,就已经具备以上5个条件了

1.定义

根据上面的概念，可以有下面的定义代码：

#define RED 0
#define BLACK 1
typedef int KEY_TYPE; //可以修改key的类型

typedef struct _rbtree_node{
	KEY_TYPE key;	//节点的键值
	void *value;	//节点存储的值,void *类型可以指向任意类型的数据
	
	struct _rbtree_node *right;
	struct _rbtree_node *left;
	struct _rbtree_node	*parent;
	
	unsigned char color;
}rbtree_node;

typedef struct _rbtree{
	struct _rbtree_node *root;//根节点
	struct _rbtree_node *nil;//哨兵节点
	//红黑树中所有的叶子结点都要指向哨兵节点,它不是传统的NULL空指针,它具有节点的属性
}rbtree;

更近一步可以下面的代码,更具有拓展性和复用性

//定义
#define RED 0
#define BLACK 1
typedef int KEY_TYPE; //可以修改key的类型

//这个宏的作用是将红黑树节点的公共部分（即与具体数据类型无关的部分）抽象出来，便于复用。
//后面需要扩展功能或者将红黑树用于不同的数据类型，只需要修改
//KEY_TYPE和value部分，而不需要重复定义这些公共字段
#define RBTREE_ENTRY(name, type)		\
	struct name{						\
		struct _rbtree_node *right;		\
		struct _rbtree_node *left;		\
		struct _rbtree_node	*parent;	\
		unsigned char color;			\
	}

typedef struct _rbtree_node{
	KEY_TYPE key;	//节点的键值
	void *value;	//节点存储的值,void *类型可以指向任意类型的数据
#if 1	
	struct _rbtree_node *right;
	struct _rbtree_node *left;
	struct _rbtree_node	*parent;
	unsigned char color;
#else
	RBTREE_ENTRY(, rb_node) node;
#endif
	
}rbtree_node;

typedef struct _rbtree{
	struct _rbtree_node *root;//根节点
	struct _rbtree_node *nil;//哨兵节点
	//红黑树中所有的叶子结点都要指向哨兵节点,它不是传统的NULL空指针,它具有节点的属性
}rbtree;

2.左旋和右旋

通过旋转可以调整树的高度,达到平衡.

在这里插入图片描述

左旋:

x的右指向y的左
y左的父指向x
y的父指向x的父
x的父指向y
y的左指向x
x的父指向y

右旋:

与左旋相称,代码中把左旋的代码,x改为y,y改为x;left与right相互替换

3.插入

插入

找到应该插入的位置
进行插入
对树进行调整,保持红黑树的性质

调整情况罗列:

父节点是左子树,叔节点是红色
父节点是左子树,叔节点是黑色,当前节点是右孩子
父节点是左子树,叔节点是黑色,当前节点是左孩子
父节点是右子树,叔节点是红色
父节点是右子树,叔节点是黑色,当前节点是右孩子
父节点是右子树,叔节点是黑色,当前节点是左孩子

4.删除

删除情况罗列:

待删除节点的左右子树都为空
- 直接删除该节点
待删除节点左右子树,一个为空,一个不为空
- 直接删除该节点，并让该节点的父节点，指向其左子树or右子树
待删除节点的左右子树都不为空
- 找到该待删除的节点的可代替节点，左子树的最大值(肯定没有右孩子,可能都左孩子)or右子树的最小值(肯定没有左孩子,可能有右孩子)
- 删除该可代替节点
- 并用可代替节点，覆盖真正待删除的节点

根据上面三种情况,需要删除的节点都是最多有一个子树

调整情况罗列:

当前结点是左孩子,其兄弟节点是红色的
当前结点是左孩子,其兄弟节点是黑色的，而且兄弟结点的两个子结点也是黑色的
当前结点是左孩子,其兄弟节点是黑色的，而且兄弟结点的左子树是红色，右子树是黑色的
当前结点是左孩子,其兄弟节点是黑色的，而且兄弟结点的左子树任意颜色，右子树是红色
当前结点是右孩子,其兄弟节点是红色的
当前结点是右孩子,其兄弟节点是黑色的，而且兄弟结点的两个子结点也是黑色的
当前结点是右孩子,其兄弟节点是黑色的，而且兄弟结点的左子树是黑色，右子树是红色的
当前结点是右孩子,其兄弟节点是黑色的，而且兄弟结点的左子树红颜色，右子树任意颜色

5.查找

通过遍历,查找对应的节点

6.遍历

中序遍历,左根右,遍历的结果是有序的

7.测试

对红黑树进行初始化,然后进行插入删除操作

左子树是黑色，右子树是红色的
8. 当前结点是右孩子,其兄弟节点是黑色的，而且兄弟结点的左子树红颜色，右子树任意颜色

5.查找

通过遍历,查找对应的节点

6.遍历

中序遍历,左根右,遍历的结果是有序的

7.测试

对红黑树进行初始化,然后进行插入删除操作

#include <stdio.h>
#include <stdlib.h>

// 1. 定义
#define RED 0
#define BLACK 1
typedef int KEY_TYPE; //可以修改key的类型

// 1.1 宏定义
//这个宏的作用是将红黑树节点的公共部分（即与具体数据类型无关的部分）抽象出来，便于复用。
//后面需要扩展功能或者将红黑树用于不同的数据类型，只需要修改
//KEY_TYPE和value部分，而不需要重复定义这些公共字段
#define RBTREE_ENTRY(name, type)		\
	struct name{						\
		struct _rbtree_node *right;		\
		struct _rbtree_node *left;		\
		struct _rbtree_node	*parent;	\
		unsigned char color;			\
	}

// 1.2 节点定义
typedef struct _rbtree_node{
	KEY_TYPE key;	//节点的键值
	void *value;	//节点存储的值,void *类型可以指向任意类型的数据
#if 1	
	struct _rbtree_node *right;
	struct _rbtree_node *left;
	struct _rbtree_node	*parent;
	unsigned char color;
#else
	RBTREE_ENTRY(, rb_node) node;
#endif
	
}rbtree_node;

// 1.3 树定义
typedef struct _rbtree{
	struct _rbtree_node *root;//根节点
	struct _rbtree_node *nil;//哨兵节点
	//红黑树中所有的叶子结点都要指向哨兵节点,它不是传统的NULL空指针,它具有节点的属性
}rbtree;

//函数声明
void rbtree_left_rotate(rbtree* T, rbtree_node* x);//左旋
void rbtree_right_rotate(rbtree* T, rbtree_node* y);//右旋
int key_compare(KEY_TYPE a, KEY_TYPE b);//节点比较
void rbtree_insert(rbtree* T, rbtree_node* z);//插入
void rbtree_insert_fixup(rbtree* T, rbtree_node* z);//插入的调整
rbtree_node* rbtree_min(rbtree* T, rbtree_node* x);//找出节点的子树中最小值
rbtree_node* rbtree_max(rbtree* T, rbtree_node* x);//找出节点的子树中最大值
rbtree_node* rbtree_successor(rbtree* T, rbtree_node* x);//找出替代节点
rbtree_node* rbtree_delete(rbtree* T, rbtree_node* z);//删除节点
void rbtree_delete_fixup(rbtree* T, rbtree_node* x);//删除的调整
rbtree_node* rbtree_search(rbtree* T, KEY_TYPE key);//查找
void rbtree_traversal(rbtree* T, rbtree_node* node);//遍历


// 2.1 左旋
//左旋leftRotate(T,x)---中右->左中
//降低X结点的高度，提高X的右结点（即Y）的高度
void rbtree_left_rotate(rbtree* T, rbtree_node* x) {
	rbtree_node* y = x->right;
	// 2.1.1
	x->right = y->left;
	if(y->left != T->nil)	{
		y->left->parent = x;
	}
	// 2.1.2
	y->parent = x->parent;
	if(x->parent == T->nil)	{
		T->root = y;//x是根节点
	}
	else if(x == x->parent->left)	{
		x->parent->left = y;//x是左子树
	}
	else{//x是右子树
		x->parent->right = y;
	}
	// 2.1.3
	y->left = x;
	x->parent = y;	
}

// 2.2 右旋
//把左旋的代码,x改为y,y改为x;left与right相互替换
void rbtree_right_rotate(rbtree* T, rbtree_node* y) {
    rbtree_node* x = y->left;
    // 2.2.1
    y->left = x->right;
    if (x->right != T->nil) {
        x->right->parent = y;
    }
    // 2.2.2
    x->parent = y->parent;
    if (y->parent == T->nil) {
        T->root = x;
    }
    else if (y == y->parent->right) {
        y->parent->right = x;
    }
    else {
        y->parent->left = x;
    }
    // 2.2.3
    x->right = y;
    y->parent = x;
}

// 3 插入
// 3.1 插入-比较节点的大小
int key_compare(KEY_TYPE a,KEY_TYPE b){
	if(a>b){
		return 1;
	}else if(a<b){
		return -1;
	}else{
		return 0;
	}
}

// 3.2 插入节点,先找位置,再调整颜色
void rbtree_insert(rbtree* T,rbtree_node* z){
	rbtree_node* x = T->root;
	rbtree_node* y = T->nil;
	// 3.2.1 通过遍历找到z应该插入的位置
	while(x!=T->nil){
		y = x;
		if(key_compare(z->key,x->key) < 0){
			//x的值更大,就找左子树
			x = x->left;
		}else if(key_compare(z->key,x->key) > 0){
			//x的值更小,就找右子树
			x = x->right;		
		}else{
			//两者相等,根据项目的业务处理
			//可能丢弃,可能通过加减后再重新排序
			return ;
		}	
	}
	// 3.2.2 进行插入
	z->parent = y;
	if(y == T->nil){
		//T树为空
		T->root = z;
	}else if(key_compare(z->key,y->key)<0){
		//y更大,插入到左子树
		y->left = z;
	}else{
		//y更小,插入到右子树
		y->right = z;
	}

	z->left = T->nil;
	z->right = T->nil;
	z->color = RED;
	// 3.2.3 维护红黑树的性质
	//"如果一个节点是红色，那么它的两个子节点都是黑色"
	rbtree_insert_fixup(T,z);
}

// 3.3 插入维护红黑树的性质
//"如果一个节点是红色，那么它的两个子节点都是黑色"
//六种情况
// 1. 父节点是左子树,叔节点是红色
// 2. 父节点是左子树,叔节点是黑色,当前节点是右孩子
// 3. 父节点是左子树,叔节点是黑色,当前节点是左孩子
// 4. 父节点是右子树,叔节点是红色
// 5. 父节点是右子树,叔节点是黑色,当前节点是右孩子
// 6. 父节点是右子树,叔节点是黑色,当前节点是左孩子
void rbtree_insert_fixup(rbtree* T,rbtree_node* z){
	while(z->parent->color == RED){
		//如果父节点是红色就需要调整
		if(z->parent == z->parent->parent->left){
			//如果父节点是左子树
			//y是叔父节点
			rbtree_node* y =z->parent->parent->right;
			if(y->color == RED){
				//如果叔父节点是红色 情况1
				z->parent->color = BLACK;
				y->color = BLACK;
				z->parent->parent->color = RED;
				z =z->parent->parent;
			}else{
				//如果叔节点是黑色
				if(z == z->parent->right){
					//当前节点是右孩子 情况2
					z= z->parent;
					rbtree_left_rotate(T,z);
				}
				//当前节点是左孩子,情况3
				z->parent->color = BLACK;
				z->parent->parent->color = RED;
				rbtree_right_rotate(T,z->parent->parent);
			}
		}else{
			//父节点是右子树
			//y是叔节点
			rbtree_node* y = z->parent->parent->left;
			if(y->color == RED){
				//叔节点是红色,情况4
				z->parent->color = BLACK;
				y->color = BLACK;
				z->parent->parent->color = RED;
				z = z->parent->parent;
			}else{
				//叔节点是黑色
				if(z == z->parent->left){
					//当前节点是左孩子,情况6
					z = z->parent;
					rbtree_right_rotate(T,z);
				}
				//当前节点是右孩子,情况5
				z->parent->color = BLACK;
				z->parent->parent->color= RED;
				rbtree_left_rotate(T,z->parent->parent);
			}
		}
	}
	//根节点永远是黑色
	T->root->color = BLACK;
}

// 4 删除
// 4.1 删除-寻找从某节点开始的最小节点
rbtree_node * rbtree_min(rbtree* T,rbtree_node* node){
	//如果为哨兵节点
	if(node == T->nil ) return T->nil;

	while(node->left != T->nil){
		node = node->left;
	}
	return node;
}

// 4.2 删除-寻找从某节点开始的最大节点
rbtree_node * rbtree_max(rbtree* T,rbtree_node* node){
	//如果为哨兵节点
	if(node == T->nil ) return T->nil;

	while(node->right != T->nil){
		node = node->right;
	}
	return node;
}

// 4.3 删除-找到node节点的可代替节点，右子树的最小值or左子树的最大值，默认为右子树的最小值
rbtree_node* rbtree_successor(rbtree* T, rbtree_node* node) {
	if(node -> right != T->nil){
		return rbtree_min(T,node->right);
	}else if( node->left != T->nil){
		return rbtree_max(T,node->left);
	}
	return node;
}

// 4.4 删除-调整情况罗列:
// 1. 当前结点是左孩子,其兄弟节点是红色的
// 2. 当前结点是左孩子,其兄弟节点是黑色的，而且兄弟结点的两个子结点也是黑色的
// 3. 当前结点是左孩子,其兄弟节点是黑色的，而且兄弟结点的左子树是红色，右子树是黑色的
// 4. 当前结点是左孩子,其兄弟节点是黑色的，而且兄弟结点的左子树任意颜色，右子树是红色
// 5. 当前结点是右孩子,其兄弟节点是红色的
// 6. 当前结点是右孩子,其兄弟节点是黑色的，而且兄弟结点的两个子结点也是黑色的
// 7. 当前结点是右孩子,其兄弟节点是黑色的，而且兄弟结点的左子树是黑色，右子树是红色的
// 8. 当前结点是右孩子,其兄弟节点是黑色的，而且兄弟结点的左子树红颜色，右子树任意颜色
//如果删除的节点是黑色则需要调整
void rbtree_delete_fixup(rbtree* T,rbtree_node* node){
	//节点不为根节点并且节点是黑色
	while((node != T->root)&&(node->color == BLACK)){
		// 1. 要删除的节点是左子树
		if(node == node->parent->left){
			//兄弟节点bro_node
			rbtree_node* bro_node = node->parent->right;
			
			// 1.1 兄弟节点是红色,情况1
			if(bro_node->color == RED){
				bro_node->color = BLACK;
				bro_node->parent->color = RED;

				rbtree_left_rotate(T,node->parent);
				bro_node = node->parent->right;
			}

			// 1.2 兄弟节点是黑色
			// 1.2.1 兄弟节点的左子树:黑  右子树:黑 情况2
			if((bro_node->left->color == BLACK)&&(bro_node->right->color == BLACK)){
				bro_node->color = RED;
				node = node->parent;
			}else{
				// 1.2.2 兄弟节点的左子树:红色 右子树:黑色 情况3
                if ((bro_node->left->color == RED) && (bro_node->right->color == BLACK)) {
                    bro_node->left->color = BLACK;
                    bro_node->color = RED;
					
                    rbtree_right_rotate(T, bro_node);
                    bro_node = node->parent->right;
                }

                // 1.2.3 兄弟节点的左子树: 任意，右子树为：红色 情况4
                bro_node->color = node->parent->color;
                node->parent->color = BLACK;
                bro_node->right->color = BLACK;
                rbtree_left_rotate(T, node->parent);

                node = T->root;
			}

        // 2. 要删除节点为右子树
        } else if (node == node->parent->right) {
            rbtree_node* bro_node = node->parent->left;

            // 2.1 兄弟节点为：红色 情况5
            if (bro_node->color == RED) {
                bro_node->color = BLACK;
                bro_node->parent->color = RED;

                rbtree_right_rotate(T, node->parent);
                bro_node = node->parent->left;
            }

            // 2.2 兄弟节点为：黑色
            // 2.2.1 兄弟节点的左子树为：黑色，右子树为：黑色 情况6
            if ((bro_node->left->color == BLACK) && (bro_node->right->color == BLACK)) {
                bro_node->color = RED;
                node = node->parent;
            } else {
                // 2.2.2兄弟节点的左子树为：黑色，右子树为：红色 情况7
                if ((bro_node->left->color == BLACK) && (bro_node->right->color == RED)) {
                    bro_node->right->color = BLACK;
                    bro_node->color = RED;

                    rbtree_left_rotate(T, bro_node);
                    bro_node = node->parent->left;
                }

                // 2.2.3 兄弟节点的左子树为：红色，右子树为：任意 情况8
                bro_node->color = node->parent->color;
                node->parent->color = BLACK;
                bro_node->left->color = BLACK;
                rbtree_right_rotate(T, node->parent);

                node = T->root;
            }
        }
    }

    node->color = BLACK;
}

// 4.5 删除
rbtree_node* rbtree_delete(rbtree* T, rbtree_node* node) {
    rbtree_node* del_node = T->nil;    // 真正待删除的节点
    rbtree_node* son_node = T->nil;    // 待删除的节点的子树

    // 4.5.1 找到需要删除的节点 del_node
    if ((node->left == T->nil) || (node->right == T->nil)) {
        del_node = node;
    } else {
		//待删除节点的左右子树都不为空
		//找到该待删除的节点的可代替节点，左子树的最大值or右子树的最小值
		//删除该可代替节点
		//并用可代替节点，覆盖真正待删除的节点
        del_node = rbtree_successor(T, node);
    }

    // 4.5.2 删除 del_node 节点
    if (del_node->left != T->nil) {
        son_node = del_node->left;
    } else if (del_node->right != T->nil) {
        son_node = del_node->right;
    }

    //if (son_node != T->nil) son_node->parent = del_node->parent;
    //让删除节点的子树指向删除节点的父节点
	son_node->parent = del_node->parent;

    if (del_node->parent == T->nil) {
        T->root = son_node;
    } else if (del_node == del_node->parent->left) {
        del_node->parent->left = son_node;
    } else if (del_node == del_node->parent->right) {
        del_node->parent->right = son_node;
    }

    // 4.5.3 用 del_node 节点，覆盖真正待删除的node节点
    if (del_node != node) {
		//对应del_node = rbtree_successor(T, node);
        node->key = del_node->key;
        node->value = del_node->value;
    }

    // 4.5.4 如果正真删除的y节点为红色，则不需要进行调整；如果为黑色，则需要进行调整，以满足红黑树的性质
    if (del_node->color == BLACK) {
        rbtree_delete_fixup(T, son_node);
    }

    // 4.5.5 返回真正删除的节点
    return del_node;
}

// 5. 红黑树的查找
rbtree_node* rbtree_search(rbtree* T, KEY_TYPE key) {
    rbtree_node* node = T->root;

    while (node != T->nil) {
        if (key == node->key) return node;
        else if (key > node->key) node = node->right;
        else if (key < node->key) node = node->left;
    }

    return T->nil;
}

// 6. 红黑树的遍历  中序遍历 左根右 
void rbtree_traversal(rbtree* T, rbtree_node* node) {
    if (node != T->nil) {
        rbtree_traversal(T, node->left);
        printf("key: %d, color: %d\n", node->key, node->color);
        rbtree_traversal(T, node->right);
    }
}

// 7. main测试
int main() {
    int keys[20] = {24,25,13,35,23, 26,67,47,38,98, 20,19,17,49,12, 21,9,18,14,15};

    // 7.1 初始化 T
    rbtree* T = (rbtree*)malloc(sizeof(rbtree));
    if (T == NULL) {
        printf("malloc fail\n");
        return 1;
    }

    T->nil = (rbtree_node*)malloc(sizeof(rbtree_node));
    T->nil->color = BLACK;
    T->root = T->nil;

    // 7.2 插入 node
    for (int i = 0; i < 20; ++i) {
        rbtree_node* node = (rbtree_node*)malloc(sizeof(rbtree_node));
        node->key = keys[i];
        node->value = NULL;

        rbtree_insert(T, node);
    }

    rbtree_traversal(T, T->root);

    printf("----------------------------------------\n");

	// 7.3 删除node
	for (int i = 0; i < 20; ++i) {

		rbtree_node* node = rbtree_search(T, keys[i]);
		rbtree_node* cur = rbtree_delete(T, node);
		free(cur);

		rbtree_traversal(T, T->root);
		printf("----------------------------------------\n");
	}
    // 释放哨兵节点
    free(T->nil);

    // 释放红黑树结构体
    free(T);

    return 0;
}

乐奇 Rokid 开放社区

更多推荐

AI 日报（2026年9月24日）

2026年9月24日，AI技术与应用呈现多元化演进态势。硬件与端侧方面，Meta在Connect大会发布首款轻量化VR眼镜与无摄像头智能眼镜，全面接入Muse智能体；谷歌上线Gemini 3.8 Flash TTS可定制语音模型，并在DeepMind推动私密计算与服务端内存融合。行业与前沿科研领域，Anthropic湿实验实验室利用Claude发现CRISPR样新型酶系统，并推出一站式Claude

乐奇 Rokid 开放社区

面向逻辑思维的程序设计方法——人形机器人最佳训练场景

乐奇 Rokid 开放社区

AI行业日报｜2026-09-25：5个热点事件

本期行业动态聚焦于端侧算力重构、自主智能体工作流、开发工具经济模型、网络隔离架构设计与公共部门合规审查。以下结合一线技术场景进行结构化梳理，供 AI 研究员与软件工程团队参考。 PrismML 正将其轻量级语言模型适配至搭载高通处理器的智能眼镜终端 1 。该平台的核心战略指向开源权重模型的本地化运行，旨在最大化挖掘穿戴设备现有算力的利用效率 1 。对于嵌入式与边缘计算开发者而言，此类微型模型向低功