当前位置：首页 > news >正文

数据结构之红黑树实现（全）

news 文章来源：https://blog.csdn.net/qq_74811378/article/details/142411372 2025/5/21 0:37:45

一、红黑树

红黑树是一种自平衡的二叉搜索树，它通过约束节点的颜色和结构来保持平衡。红黑树是由 Rudolf Bayer 在1972年发明的，被认为是一种优秀的平衡树结构，广泛应用于各种数据结构和算法中。

1.红黑树的性质

1. 每个结点是红的或者黑的

2. 根结点是黑的

3. 每个叶子结点是黑的（因为这条性质，一般用叶子结点在代码中被特殊表示）

4. 如果一个结点是红的，则它的两个儿子都是黑的（不存在相邻红色）

5. 从任一节点到叶子节点，所包含的黑色节点数目相同（即黑高度相同）

6. 最长路径长度不超过最短路径长度的2倍（2n-1，一条黑红黑红…一条全黑）

2.红黑树和AVL树

所以红黑树的查询效率略低与AVL的查询
红黑树和AVL插入的速度差不多
红黑树删除的速度比AVL快，因为AVL删除最多需要log(N)次旋转

3.红黑树的应用场景

c++ stl map,set（红黑树的封装）
进程调度cfs（用红黑树存储进程的集合，把调度的时间作为key，那么树的左下角时间就是最小的）
内存管理（每次使用malloc的时候都会分配一块小内存出来，那么这么块就是用红黑树来存，如何表述一段内存块呢，用开始地址+长度来表示，所以key->开始地址，val->大小）
epoll中使用红黑树管理socketfd
nginx中使用红黑树管理定时器，中序遍历第一个就是最小的定时器

二、代码实现

1.结构体定义

红黑树是一种特殊的二叉树，所以其实现和二叉树类似。但需要加上color用来标记颜色。实现如下：

#define RED 0
#define BlACK 1typedef int KEY_TYPE;typedef struct _rbtree_node {unsigned char color;//颜色struct _rbtree_node *left;//左子树struct _rbtree_node *right;//右子树struct _rbtree_node *parent;//父结点KEY_TYPE key;void *value;} rbtree_node;//红黑树结点typedef struct _rbtree {rbtree_node *root;//根结点rbtree_node *nil;//通用叶子结点
} rbtree;//红黑树

2.红黑树的左旋和右旋

左旋：动三个方向，改6个指针。

左旋如上图所示：

我们需要改的方向为：

1.between E and S和S

2.E和S

3.S和parents

右旋：和左旋原理一样，不做过多赘述。

代码实现如下：

//左旋leftRotate(T,x)---中右->左中
//降低X结点的高度，提高X结点右结点（即Y）的高度。
void _left_rotate(rbtree *T, rbtree_node *x) {rbtree_node *y = x->right;//1x->right = y->left;//x的右子树指向y的左子树if (y->left != T->nil) {y->left->parent = x;//y的左子树的父节点指向x}//2y->parent = x->parent;//y的父结点指向x的父结点if (x->parent == T->nil) {//如果x是根结点T->root = y;} else if (x == x->parent->left) {x->parent->left = y;//本来指向x结点的父指针，改成指向y} else {x->parent->right = y;}//3y->left = x;//y的左子树指向x结点x->parent = y;//x的父节点指向y
}//右旋
//copy左旋的代码
//left改成right，right改成left
//x改成y，y改成x
void _right_rotate(rbtree *T, rbtree_node *y) {rbtree_node *x = y->left;//1y->left = x->right;if (x->right != T->nil) {x->right->parent = y;}//2x->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;}//3x->right = y;y->parent = x;
}

3.红黑树插入结点与插入维护红黑树的三种情况

（1）插入结点

        插入这个结点之前，原来的红黑树是满足红黑树性质的==，插入就是不断的对比key，最终找到位置。

        那么，我们需要考虑一个问题：那就是插入的结点应该上什么色？

我们通过性质发现：

        如果新结点是黑色，违背了第5条性质

        如果新结点是红色，可能违背第4条性质

第四条性质，我们可以通过旋转与上色的方式修复，所以在我们插入结点的时候，我们始终认为新结点是红色。

代码实现如下：

//因为传入的key可能是字符，可能是整形，所以要提取出来
//这里可以看出，其实可以封装成一个模板
int key_compare(KEY_TYPE a, KEY_TYPE b) {//这里假设是intif (a > b) {return 1;} else if (a < b) {return -1;} else {return 0;}
}
void rbtree_insert(rbtree *T, rbtree_node *z) {//找位置rbtree_node *x = T->root;rbtree_node *y = T->nil;//y是x的父节点while (x != T->nil) {//二分找位置y = x;if (key_compare(z->key, x->key) < 0) {x = x->left;} else if (key_compare(z->key, x->key) > 0) {x = x->right;} else {//如果key相等，看自己的业务情景//重复插入可以不修改直接退出，可以修改valreturn;}}//插入z->parent = y;if (y == T->nil) {T->root = z;} else if (key_compare(z->key, y->key) < 0) {y->left = z;} else {y->right = z;}z->left = T->nil;z->right = T->nil;z->color = RED;//维护红黑树rbtree_insert_fixup(T, z);
}

（2）插入结点后维护红黑树

我们知道新增结点是红色，如果新结点是父节点也是红色，那么就需要维护红黑树了。

此时有几种情况：

1.父结点是爷结点是左子树

（1）叔结点是红色的

（i）将叔结点和父结点变黑，爷结点变红

（ii）将当前结点变成爷结点（因为爷结点是红，爷结点的父节点也可能是红，所以要递归维护）

（2）叔结点是黑色的且新结点是左子树

                        （i）将父结点变成黑色，爷结点变成红色

（ii）以爷结点为中心右旋

（3）叔结点是黑色的且新结点是右子树

                        （i）以父结点为中心左旋

（ii）将父结点变黑色，爷结点变红色

  (iii) 以爷结点为中心右旋

2.父结点是爷结点是右子树

        （1）叔结点是红色的

                        （i）将叔结点和父结点变黑，爷结点变红

（ii）将当前结点变成爷结点（因为爷结点是红，爷结点的父节点也可能是红，所以要递归维护）

（2）叔结点是黑色的且新结点是左子树

                        （i）以父结点为中心右旋

（ii）将父结点变黑色，爷结点变红色

  (iii) 以爷结点为中心左旋

（3）叔结点是黑色的且新结点是右子树

                        （i）将父结点变成黑色，爷结点变成红色

（ii）以爷结点为中心左旋

//修复第4条性质
void rbtree_insert_fixup(rbtree *T, rbtree_node *z) {while (z->parent->color == RED) {//父结点是红色的，需要调整if (z->parent == z->parent->parent->left) {//如果父结点是爷结点是左子树rbtree_node *y = z->parent->parent->right;//叔结点if (y->color == RED) {//叔结点是红色的//先变色，叔,父变黑z->parent->color = BLACK;y->color = BLACK;//爷结点变红z->parent->parent->color = RED;//下面的调整完了，调整上面z = z->parent->parent;} else {//叔父结点是黑色if (z == z->parent->right) {//新节点是在右边z = z->parent;rbtree_left_rotate(T, z);}z->parent->color = BLACK;z->parent->parent->color = RED;rbtree_right_rotate(T, z->parent->parent);}} else {// 如果父结点是爷结点是右子树rbtree_node *y = z->parent->parent->left;//叔父结点if (y->color == RED) {//叔父结点是红色的//先变色，叔,父变黑z->parent->color = BLACK;y->color = BLACK;//爷结点变红z->parent->parent->color = RED;//下面的调整完了，调整上面z = z->parent->parent;} else {//叔父结点是黑色if (z == z->parent->left) {//新节点是在左边z = z->parent;rbtree_right_rotate(T, z);}z->parent->color = BLACK;z->parent->parent->color = RED;rbtree_left_rotate(T, z->parent->parent);}}}//最后别忘了根节点始终是黑色T->root->color = BLACK;
}

4.红黑树删除结点与删除维护红黑树的四种情况

(1)删除结点

我们定义：

覆盖结点：z（被指定删除的结点，实际上被覆盖）
删除结点：y（实际上被删除的结点，一般是后继结点）
轴心结点：x（维护红黑树的结点）

红黑树删除结点根据改结点的左右子树分为三种情况：

没有左右子树
有且仅有一个子树
左右子树都有

对不同情况的处理：

情况1：直接删除该结点
情况2：将该结点的唯一子树挂到父结点上，然后删除该结点

情况3：找一个删除结点y（后继结点）覆盖指定结点z，然后删除删除结点y，对于这个删除结点y来说，它的情况一定是情况1或情况2

rbtree_node *rbtree_mini(rbtree *T, rbtree_node *x) {while (x->left != T->nil) {x = x->left;}return x;
}//找后继结点
rbtree_node *rbtree_successor(rbtree *T, rbtree_node *x) {rbtree_node *y = x->parent;//右子树不为空，则找右子树中最左的元素if (x->right != T->nil) {return rbtree_mini(T, x->right);}//找到结点第一个父结点while ((y != T->nil) && (x == y->right)) {x = y;y = y->parent;}return y;
}//覆盖结点z
//删除结点y
//轴心结点x
rbtree_node *rbtree_delete(rbtree *T, rbtree_node *z) {rbtree_node *y = T->nil;rbtree_node *x = T->nil;if ((z->left == T->nil) || (z->right == T->nil)) {y = z;//如果没有孩子或只有一个} else {//如果有两个子树则找后继y = rbtree_successor(T, z);}//一般x是y的右子树，找到轴心结点if (y->left != T->nil) {x = y->left;} else if (y->right != T->nil) {x = y->right;}//将该结点的唯一子树挂到父结点上，然后删除该结点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;}//进行覆盖操作if (y != z) {z->key = y->key;z->value = y->value;}//黑色才需要调整if (y->color == BLACK) {rbtree_delete_fixup(T, x);}return y;
}

(2)维护红黑树

删除一个结点，该结点是什么颜色的时候才需要维护红黑树呢？

如果是红色，没有违反任何性质。所以如果是红色直接删除即可，无需维护
如果是黑色，黑色被删除，那么必定违反第5条性质，破坏了黑高，所以我们需要针对这一情况进行维护

如果当前结点是父结点的左子树的情况，可以归纳出来四种情况。

当前结点是父结点的左子树的情况

        1. 当前结点的兄弟结点是红色的

                （i）兄弟节点变成黑色

                （ii）父节点变成红色

                （iii）父节点做左旋

                （iiii）将兄弟结点调整为父节点的右子树

        2. 当前结点的兄弟结点是黑色的，而且兄弟结点的两个孩子结点都是黑色的

                （i）兄弟节点变成红色

                （ii）轴心结点变为父节点

        3. 当前结点的兄弟结点是黑色的，而且兄弟结点的左孩子是红色的，右孩子是黑色的

                （i）将左孩子涂黑

                （ii）将兄弟节点变红

                （iii）对兄弟节点右旋

                （iiii）将兄弟结点调整为父节点的右子树

（iiiii）现在情况3就会变成情况4，接着做情况4的步骤

        4. 当前结点的兄弟结点是黑色的，而且兄弟结点的左孩子是黑色的，右孩子是红色的

                （i）将兄弟节点换成父节点的颜色

                （ii）把父节点和兄弟节点的右孩子涂黑

                （iii）对父节点做左旋

                （iiii）设置x指针，指向根节点

当前结点是父结点的右子树的情况

        1. 当前结点的兄弟结点是红色的

                （i）兄弟节点变成黑色

                （ii）父节点变成红色

                （iii）父节点做右旋

                （iiii）将兄弟结点调整为父节点的左子树

        2. 当前结点的兄弟结点是黑色的，而且兄弟结点的两个孩子结点都是黑色的

                （i）兄弟节点变成红色

                （ii）轴心结点变为父节点

        3. 当前结点的兄弟结点是黑色的，而且兄弟结点的左孩子是黑色的，右孩子是红色的

                （i）将右孩子变黑

                （ii）将兄弟节点变红

                （iii）对兄弟结点左旋

                （iiii）将兄弟结点调整为父节点的左子树

(iiiii）现在情况3就会变成情况4，接着做情况4的步骤

        4. 当前结点的兄弟结点是黑色的，而且兄弟结点的左孩子是红色的，右孩子是黑色的

                （i）将兄弟节点换成父节点的颜色

                （ii）把父节点和兄弟节点的左孩子变黑

                （iii）对父节点做右旋

                （iiii）将轴心结点调整为根结点

void rbtree_delete_fixup(rbtree *T, rbtree_node *x) {//如果x是红色，变成黑色，如果x是黑色，需要调整while ((x != T->root) && (x->color == BLACK)) {//当前结点是父结点的左子树if (x == x->parent->left) {//兄弟节点rbtree_node *w = x->parent->right;// 情况1：兄弟节点为红色if (w->color == RED) {// 兄弟节点变成黑色w->color = BLACK;// 父节点变成红色x->parent->color = RED;// 父节点做左旋rbtree_left_rotate(T, x->parent);//将兄弟结点调整为父节点的右子树w = x->parent->right;}// 情况2：兄弟节点是黑色的，且兄弟的左孩子和右孩子都是黑色if ((w->left->color == BLACK) && (w->right->color == BLACK)) {// 兄弟节点变成红色w->color = RED;// 轴心结点变为父节点x = x->parent;} else {// 情况3：x的兄弟节点是黑色的，兄弟的左孩子是红色，右孩子是黑色if (w->right->color == BLACK) {// 将左孩子涂黑w->left->color = BLACK;// 将兄弟节点变红w->color = RED;// 对兄弟节点右旋rbtree_right_rotate(T, w);// 重新设置x的兄弟节点w = x->parent->right;}// 情况4：x的兄弟节点是黑色；x的兄弟节点的右孩子是红色的// 将兄弟节点换成父节点的颜色w->color = x->parent->color;// 把父节点和兄弟节点的右孩子涂黑x->parent->color = BLACK;w->right->color = BLACK;// 对父节点做左旋rbtree_left_rotate(T, x->parent);// 设置x指针，指向根节点x = T->root;}} else {//当前结点是父结点的右子树//兄弟节点rbtree_node *w = x->parent->left;//情况1：兄弟结点为红色if (w->color == RED) {// 兄弟节点变成黑色w->color = BLACK;// 父节点变成红色x->parent->color = RED;// 父节点做右旋rbtree_right_rotate(T, x->parent);//将兄弟结点调整为父节点的左子树w = x->parent->left;}// 情况2：兄弟节点是黑色的，且兄弟的左孩子和右孩子都是黑色if ((w->left->color == BLACK) && (w->right->color == BLACK)) {// 兄弟节点变成红色w->color = RED;// 轴心结点变为父节点x = x->parent;} else {// 情况3：x的兄弟结点是黑色的，兄弟的左孩子是黑色，右孩子是红色if (w->left->color == BLACK) {//将右孩子变黑w->right->color = BLACK;//将兄弟节点变红w->color = RED;//对兄弟结点左旋rbtree_left_rotate(T, w);//将兄弟结点调整为父节点的左子树w = x->parent->left;}// 情况4：x的兄弟结点是黑色的，兄弟的左孩子是红色，右孩子是黑色// 将兄弟节点换成父节点的颜色w->color = x->parent->color;// 把父节点和兄弟节点的左孩子变黑x->parent->color = BLACK;w->left->color = BLACK;// 对父节点做右旋rbtree_right_rotate(T, x->parent);//将轴心结点调整为根结点x = T->root;}}}// 继承节点变为黑色，为了弥补失去的黑高x->color = BLACK;
}

三、完整代码及测试用例

#include <stdio.h>
#include <stdlib.h>
#include <string.h>#define RED 0
#define BLACK 1typedef int KEY_TYPE;typedef struct _rbtree_node {unsigned char color;//颜色struct _rbtree_node* left;//左子树struct _rbtree_node* right;//右子树struct _rbtree_node* parent;//父结点KEY_TYPE key;void* value;} rbtree_node;//红黑树结点typedef struct _rbtree {rbtree_node* root;//根结点rbtree_node* nil;//通用叶子结点（null）
} rbtree;//红黑树//函数声明
void rbtree_delete_fixup(rbtree* T, rbtree_node* x);
void rbtree_insert_fixup(rbtree* T, rbtree_node* z);//左旋leftRotate(T,x)---中右->左中
//需要改变6根指针
//降低X结点的高度，提高X结点右结点（即Y）的高度。
void rbtree_left_rotate(rbtree* T, rbtree_node* x) {rbtree_node* y = x->right;//1x->right = y->left;//x的右子树指向y的左子树if (y->left != T->nil) {y->left->parent = x;//y的左子树的父节点指向x}//2y->parent = x->parent;//y的父结点指向x的父结点if (x->parent == T->nil) {//如果x是根结点T->root = y;}else if (x == x->parent->left) {x->parent->left = y;//本来指向x结点的父指针，改成指向y}else {x->parent->right = y;}//3y->left = x;//y的左子树指向x结点x->parent = y;//x的父节点指向y
}//右旋
//copy左旋的代码
//left改成right，right改成left
//x改成y，y改成x
void rbtree_right_rotate(rbtree* T, rbtree_node* y) {rbtree_node* x = y->left;//1y->left = x->right;if (x->right != T->nil) {x->right->parent = y;}//2x->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;}//3x->right = y;y->parent = x;
}//因为传入的key可能是字符，可能是整形，所以要提取出来
//这里可以看出，其实可以封装成一个模板
int key_compare(KEY_TYPE a, KEY_TYPE b) {//这里假设是intif (a > b) {return 1;}else if (a < b) {return -1;}else {return 0;}
}
//插入结点
void rbtree_insert(rbtree* T, rbtree_node* z) {//找位置rbtree_node* x = T->root;rbtree_node* y = T->nil;//y是x的父节点while (x != T->nil) {//二分找位置y = x;if (key_compare(z->key, x->key) < 0) {x = x->left;}else if (key_compare(z->key, x->key) > 0) {x = x->right;}else {//如果key相等，看自己的业务情景//重复插入可以不修改直接退出，可以修改valreturn;}}//插入z->parent = y;if (y == T->nil) {T->root = z;}else if (key_compare(z->key, y->key) < 0) {y->left = z;}else {y->right = z;}z->left = T->nil;z->right = T->nil;z->color = RED;//维护红黑树rbtree_insert_fixup(T, z);
}//修复第4条性质
//插入节点之后，如果破坏了红黑树的性质，需要修复
void rbtree_insert_fixup(rbtree* T, rbtree_node* z) {//父结点是红色的，需要调整while (z->parent->color == RED) {if (z->parent == z->parent->parent->left) {//如果父结点是爷结点是左子树rbtree_node* y = z->parent->parent->right;//叔结点if (y->color == RED) {//叔结点是红色的//先变色，叔,父变黑z->parent->color = BLACK;y->color = BLACK;//爷结点变红z->parent->parent->color = RED;//下面的调整完了，调整上面z = z->parent->parent;}else {//叔父结点是黑色if (z == z->parent->right) {//新节点是在右边z = z->parent;rbtree_left_rotate(T, z);}z->parent->color = BLACK;z->parent->parent->color = RED;rbtree_right_rotate(T, z->parent->parent);}}else {// 如果父结点是爷结点是右子树rbtree_node* y = z->parent->parent->left;//叔父结点if (y->color == RED) {//叔父结点是红色的//先变色，叔,父变黑z->parent->color = BLACK;y->color = BLACK;//爷结点变红z->parent->parent->color = RED;//下面的调整完了，调整上面z = z->parent->parent;}else {//叔父结点是黑色if (z == z->parent->left) {//新节点是在左边z = z->parent;rbtree_right_rotate(T, z);}z->parent->color = BLACK;z->parent->parent->color = RED;rbtree_left_rotate(T, z->parent->parent);}}}//最后别忘了根节点始终是黑色T->root->color = BLACK;
}rbtree_node* rbtree_mini(rbtree* T, rbtree_node* x) {while (x->left != T->nil) {x = x->left;}return x;
}//找后继结点
rbtree_node* rbtree_successor(rbtree* T, rbtree_node* x) {rbtree_node* y = x->parent;//右子树不为空，则找右子树中最左的元素if (x->right != T->nil) {return rbtree_mini(T, x->right);}//找到结点第一个父结点while ((y != T->nil) && (x == y->right)) {x = y;y = y->parent;}return y;
}//覆盖结点z
//删除结点y
//轴心结点x
rbtree_node* rbtree_delete(rbtree* T, rbtree_node* z) {rbtree_node* y = T->nil;rbtree_node* x = T->nil;if ((z->left == T->nil) || (z->right == T->nil)) {y = z;//如果没有孩子或只有一个}else {//如果有两个子树则找后继y = rbtree_successor(T, z);}//一般x是y的右子树，找到轴心结点if (y->left != T->nil) {x = y->left;}else if (y->right != T->nil) {x = y->right;}//将该结点的唯一子树挂到父结点上，然后删除该结点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;}//进行覆盖操作if (y != z) {z->key = y->key;z->value = y->value;}//黑色才需要调整if (y->color == BLACK) {rbtree_delete_fixup(T, x);}return y;
}void rbtree_delete_fixup(rbtree* T, rbtree_node* x) {//如果x是红色，变成黑色，如果x是黑色，需要调整while ((x != T->root) && (x->color == BLACK)) {//当前结点是父结点的左子树if (x == x->parent->left) {//兄弟节点rbtree_node* w = x->parent->right;// 情况1：兄弟节点为红色if (w->color == RED) {// 兄弟节点变成黑色w->color = BLACK;// 父节点变成红色x->parent->color = RED;// 父节点做左旋rbtree_left_rotate(T, x->parent);//将兄弟结点调整为父节点的右子树w = x->parent->right;}// 情况2：兄弟节点是黑色的，且兄弟的左孩子和右孩子都是黑色if ((w->left->color == BLACK) && (w->right->color == BLACK)) {// 兄弟节点变成红色w->color = RED;// 轴心结点变为父节点x = x->parent;}else {// 情况3：x的兄弟节点是黑色的，兄弟的左孩子是红色，右孩子是黑色if (w->right->color == BLACK) {// 将左孩子涂黑w->left->color = BLACK;// 将兄弟节点变红w->color = RED;// 对兄弟节点右旋rbtree_right_rotate(T, w);// 重新设置x的兄弟节点w = x->parent->right;}// 情况4：x的兄弟节点是黑色；x的兄弟节点的右孩子是红色的// 将兄弟节点换成父节点的颜色w->color = x->parent->color;// 把父节点和兄弟节点的右孩子涂黑x->parent->color = BLACK;w->right->color = BLACK;// 对父节点做左旋rbtree_left_rotate(T, x->parent);// 设置x指针，指向根节点x = T->root;}}else {//当前结点是父结点的右子树//兄弟节点rbtree_node* w = x->parent->left;//情况1：兄弟结点为红色if (w->color == RED) {// 兄弟节点变成黑色w->color = BLACK;// 父节点变成红色x->parent->color = RED;// 父节点做右旋rbtree_right_rotate(T, x->parent);//将兄弟结点调整为父节点的左子树w = x->parent->left;}// 情况2：兄弟节点是黑色的，且兄弟的左孩子和右孩子都是黑色if ((w->left->color == BLACK) && (w->right->color == BLACK)) {// 兄弟节点变成红色w->color = RED;// 轴心结点变为父节点x = x->parent;}else {// 情况3：x的兄弟结点是黑色的，兄弟的左孩子是黑色，右孩子是红色if (w->left->color == BLACK) {//将右孩子变黑w->right->color = BLACK;//将兄弟节点变红w->color = RED;//对兄弟结点左旋rbtree_left_rotate(T, w);//将兄弟结点调整为父节点的左子树w = x->parent->left;}// 情况4：x的兄弟结点是黑色的，兄弟的左孩子是红色，右孩子是黑色// 将兄弟节点换成父节点的颜色w->color = x->parent->color;// 把父节点和兄弟节点的左孩子变黑x->parent->color = BLACK;w->left->color = BLACK;// 对父节点做右旋rbtree_right_rotate(T, x->parent);//将轴心结点调整为根结点x = T->root;}}}// 继承节点变为黑色，为了弥补失去的黑高x->color = BLACK;
}rbtree_node* rbtree_search(rbtree* T, KEY_TYPE key) {rbtree_node* node = T->root;while (node != T->nil) {if (key < node->key) {node = node->left;}else if (key > node->key) {node = node->right;}else {return node;}}return T->nil;
}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);}
}int main() {int keyArray[20] = { 24, 25, 13, 35, 23, 26, 67, 47, 38, 98, 20, 19, 17, 49, 12, 21, 9, 18, 14, 15 };rbtree* T = (rbtree*)malloc(sizeof(rbtree));if (T == NULL) {printf("malloc failed\n");return -1;}T->nil = (rbtree_node*)malloc(sizeof(rbtree_node));T->nil->color = BLACK;T->root = T->nil;rbtree_node* node = T->nil;int i = 0;for (i = 0; i < 20; i++) {node = (rbtree_node*)malloc(sizeof(rbtree_node));node->key = keyArray[i];node->value = NULL;rbtree_insert(T, node);}rbtree_traversal(T, T->root);printf("****************************************\n");for (i = 0; i < 20; i++) {rbtree_node* node = rbtree_search(T, keyArray[i]);rbtree_node* cur = rbtree_delete(T, node);free(cur);rbtree_traversal(T, T->root);printf("----------------------------------------\n");}
}

数据结构之红黑树实现（全）

一、红黑树红黑树是一种自平衡的二叉搜索树，它通过约束节点的颜色和结构来保持平衡。红黑树是由 Rudolf Bayer 在1972年发明的，被认为是一种优秀的平衡树结构，广泛应用于各种数据结构和算法中。 1.红黑树的性质 1. 每个结点是红的或者黑的…...

编程日记 2024/10/10 10:05:24

冷热数据分离

优质博文：IT-BLOG-CN 一、背景随着机票业务的快速发展，订单量持续增长对业务性能带来影响，需要进行冷热数据分离。目前机票订单模块主要使用Mysql(InnoDB)作为数据库存储，历史订单信息状态修改频率低并占用大量数据库存储空间&…...

编程日记 2024/10/10 10:03:21

朝花夕拾：多模态图文预训练的前世今生

Diffusion Models专栏文章汇总：入门与实战前言：时间来到2024年，多模态大模型炙手可热。在上一个时代的【多模态图文预训练】宛若时代的遗珠，本文的时间线从2019年到2022年，从BERT横空出世讲到ViT大杀四方，…...

编程日记 2024/10/10 10:02:20

亳州自闭症寄宿制学校，关注孩子的学习和生活

在特殊教育领域，自闭症儿童的教育与成长一直是社会各界关注的焦点。近年来，随着对自闭症认识的加深，越来越多的寄宿制学校应运而生，致力于为这些特殊的孩子提供全面、个性化的教育服务。在安徽亳州，这样的学校正努力为…...

编程日记 2024/10/10 10:00:17

Root me CTF all the day靶场ssrf+redis漏洞

Rootme CTF all the day靶场ssrfredis漏洞一、环境介绍1、漏洞地址2、漏洞介绍二、搭建环境三、测试过程3.1 读取系统文件3.2 探测开放的服务器端口(dict协议)3.3 redis未授权访问3.3.1 利用redis来写ssh密钥（gopher协议写入）3.3.2 利用redis写定时任…...

编程日记 2024/10/10 9:59:16

C#中Json序列化的进阶用法

本文所有json序列化，都使用的Newtonsoft.Json包 1 JsonIgnore 在 Newtonsoft.Json 中，如果你不想将某些属性转换为 JSON 字符串，可以使用多种方法来实现。以下是几种常见的方法： 1.1 使用 [JsonIgnore] 特性 [JsonIgnore] 特性…...

编程日记 2024/10/10 9:56:12

IO相关的常用工具包

常用工具包Commons-io Commons-io是apache开源基金组织提供的一组有关IO操作的开源工具包。作用:提高IO流的开发效率。使用步骤: 1、在项目中创建一个文件夹：lib 2、将jar包复制粘贴到lib文件夹 3、右键点击jar包，选择Add as Library--->点击OK …...

编程日记 2024/10/10 9:55:11

Spring Boot集成RBloomFilter快速入门Demo

在大数据处理和缓存优化的场景中，布隆过滤器（Bloom Filter）因其高效的空间利用和快速的查询性能而被广泛应用。RBloomFilter是布隆过滤器的一种实现，通常用于判断一个元素是否存在于一个集合中，尽管它存在一定的误判率…...

编程日记 2024/10/10 9:51:03

布局性能优化

布局使用不当回导致卡顿、掉帧、响应慢等问题一、布局流程 1、应用侧会根据前端UI描述创建后端的页面节点树，其中包含了处理UI组件属性更新、布局测算、事件处理等逻辑 2、页面节点树创建完成后，UI线程会对每个元素进行测算（Measure&#…...

编程日记 2024/10/10 9:48:00

智云人才推荐与管理系统

1.产品介绍产品名称：智云人才推荐与管理系统主要功能： 智能人才匹配引擎功能描述：利用先进的人工智能算法，根据企业岗位需求（如技能要求、工作经验、教育背景等）自动从海量人才库中筛选并推荐最合适的…...

编程日记 2024/10/10 9:45:56

git在远程分支上新建分支

需求： 在远程分支release/test的基础上创建一个新的分支test_20241009 确保本地仓库的信息是最新的 git fetch origin执行了 git fetch，本地仓库已经包含了 origin/release/test 的最新信息。当基于这个远程跟踪分支创建新分支时，会得到一个包…...

编程日记 2024/10/10 9:44:55

用Python实现的高校教师资格考试题库程序

最近朋友参加了高校教师资格考试，在考试前需要刷题来保证通过。但是教资网站上的题库只有接近考试才更新，并且官方题库的刷题效率还是有点低。 👆官方题库的样子于是想到了是否能够将官方题库内容记录下来，然后自己创建一个高效…...

编程日记 2024/10/10 9:42:52

OpenVINO基本操作流程

环境配置： conda env list:可以查看有哪些环境 conda activate intel:启动某个环境 pip list：可以查看此环境下都下载了哪些软件包 from openvino.inference_engine import IEcore#从OpenVINO推理引擎中导入IECore类 import numpy as np import cv2 1&…...

编程日记 2024/10/10 9:40:49

Spring MVC 注解详解：@RequestBody，@RequestParam 和 @PathVariable

Spring MVC 提供了一系列注解，用于简化请求数据的获取和处理。了解并掌握这些注解的使用，对于开发RESTful API和处理HTTP请求至关重要。本文将详细介绍 RequestBody，RequestParam 和 PathVariable 注解，并附带具体的代码示例&…...

编程日记 2024/10/10 9:38:46

MySQL 8 中的 sql_mode

MySQL 8 中的 sql_mode 设置：提升数据库安全性与性能在现代数据库管理中，MySQL 是一个广泛使用的开源关系型数据库。随着数据的增长和复杂性增加，良好的数据库配置显得尤为重要。sql_mode 是 MySQL 提供的一个强大功能，它可以帮…...

编程日记 2024/10/10 9:36:44

13种pod的状态

13种pod的状态生命周期 Pending：Pod被创建后进入调度阶段，k8s调度器依据pod声明的资源请求量和调度规则，为pod挑选一个适合运行的节点。当集群节点不满足pod调度需求时，pod将会处于pending状态。Running：Pod被调度到节点上，k8s将pod调度到节点上后，进入running状态。S…...

编程日记 2024/10/10 9:34:41

2025考研今天开始预报名！攻略请查收

2025年全国硕士研究生招生考试今天起开始预报名有什么流程？需要准备哪些信息？ 这份考研报名攻略速查收 ↓↓↓ 全国硕士研究生招生考试报名包括网上报名和网上确认两个阶段： 网上预报名时间为10月9日至10月12日（每日9&#xff1…...

编程日记 2024/10/10 9:33:40

这段代码很有代表性，涵盖了多个 JavaScript 知识点，特别是不同异步操作的执行优先级。 async function async1() {console.log(async1 start);await async2();console.log(async1 end); }async function async2() {console.log(async2); }console.log(s…...

编程日记 2024/10/10 9:32:39

【机器学习】金融预测 —— 风险管理与股市预测

我的主页：2的n次方_ 在金融领域，机器学习（ML）已经成为了不可或缺的工具。金融预测，尤其是风险管理和股市预测，涉及海量数据和复杂模式的分析，而这些正是机器学习擅长处理的领域。通过分析历…...

编程日记 2024/10/10 9:31:38

Bootstrap 5 分页组件使用教程

Bootstrap 5 分页组件使用教程引言 Bootstrap 5 是一个流行的前端框架，它提供了一套丰富的组件和工具，用于快速开发响应式和移动优先的网页。分页组件是 Bootstrap 5 中用于分割长列表或数据集的重要部分，它可以帮助用户更容易地浏览内容。本文将详细介绍如何在您的项目中…...

编程日记 2024/10/10 9:30:36

Linux 安装 NVM 并配置 npm 加速，开发 node 项目不再愁

由于需要在 linux 机器上完成 node 项目的构建，需要安装 nodejs, 想着不同项目需要使用不同的版本，索性安装一下 nvm 吧，因为之前在 windows 上已经安装过 nvm-windows, 应该很容易上手，我尝试了官网提供的几种方式，最…...

编程日记 2024/10/10 9:27:33

MySQL 多条件查询

在 MySQL 中，多条件查询通常使用 WHERE 子句来指定多个条件。这些条件可以通过逻辑运算符（如 AND、OR、NOT）进行组合，以实现复杂的查询需求。以下是一些常见的多条件查询示例： 使用 AND 运算符 AND 运算符用于组合多…...

编程日记 2024/10/10 9:26:31

深度学习模型

1. 引言在过去的十年间，深度学习的崛起引发了人工智能领域的革命，深刻影响了多个行业。深度学习是一种模仿人脑神经元的工作方式，通过多层神经网络进行数据处理与特征学习。其应用范围从简单的图像识别到复杂的自然语言处理、自动驾驶和医疗…...

编程日记 2024/10/10 9:23:27

Nexpose 6.6.271 发布下载，新增功能概览

Nexpose 6.6.271 for Linux & Windows - 漏洞扫描 Rapid7 Vulnerability Management, release Sep 26, 2024 请访问原文链接：https://sysin.org/blog/nexpose-6/，查看最新版。原创作品，转载请保留出处。作者主页：sysin.or…...

编程日记 2024/10/10 9:21:24

SimpleRAG-v1.0.3：增加文件对话功能

Kimi上有一个功能，就是增加文件之后对话，比如我有如下一个私有文档： 会议主题：《如何使用C#提升工作效率》参会人员：张三、李四、王五时间：2024.9.26 14:00-16:00 会议内容： 1. 自动化日常任…...

编程日记 2024/10/10 9:19:21

数学建模算法与应用第7章数理统计与方法

目录 7.1 参数估计与假设检验 Matlab代码示例：均值的假设检验 7.2 Bootstrap方法 Matlab代码示例：Bootstrap估计均值的置信区间 7.3 方差分析 Matlab代码示例：单因素方差分析 7.4 回归分析 Matlab代码示例：线性回归 7.5 基…...

编程日记 2024/10/10 9:15:08

【网络】洪水攻击防御指南

洪水攻击防御指南摘要： 本文深入探讨了洪水攻击的概念、危害以及防御策略。通过Java技术实现，我们将学习如何通过编程手段来增强服务器的安全性。文章不仅提供了详细的技术解读，还包含了实用的代码示例和流程图，帮助读者构建一个…...

编程日记 2024/10/10 9:14:07

应对Redis大Key挑战：从原理到实现

在使用Redis作为缓存或数据存储时，开发者可能会遇到大Key（Big Key）问题。大Key是指在Redis中存储的单个键值对，其值的大小非常大，可能包含大量数据或占用大量内存。大Key问题会导致性能下降、内存消耗过多以及其他潜在…...

编程日记 2024/10/10 9:12:05

网络安全的全面指南

目录网络安全的全面指南1. 引言2. 网络安全的基本概念3. 网络安全框架4. 常见网络安全攻击及案例4.1 病毒与恶意软件攻击案例4.2 钓鱼攻击案例4.3 DDoS 攻击案例 5. 网络安全最佳实践5.1 强密码策略5.2 定期更新和补丁管理5.3 数据备份与恢复策略 6. 企业网络安全策略6.1 安全…...

编程日记 2024/10/10 9:11:03

前端性能优化全面指南

前端性能优化是提升用户体验的关键，页面加载速度、响应时间和交互流畅度直接影响用户的留存率和满意度。以下是常用的前端性能优化方法，从网络层、资源加载、JavaScript 执行、渲染性能等方面进行全方位优化。减少 HTTP 请求合并文件：将多…...

编程日记 2024/10/10 9:09:01