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

一、红黑树

红黑树是一种自平衡的二叉搜索树，它通过约束节点的颜色和结构来保持平衡。红黑树是由 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. 左右子树都有

对不同情况的处理：

  • 情况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");}
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/446281.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

Mac 备忘录妙用

Mac 备忘录妙用

之前使用 Windows 的过程中&#xff0c;最痛苦的事是没有一款可以满足我快速进行记录的应用 基本都得先打开该笔记软件&#xff0c;然后创建新笔记&#xff0c;最后才能输入&#xff0c;这么多步骤太麻烦了 在切换到 MacOS 之后&#xff0c;让我惊喜的就是自带的备忘录&#…
阅读更多...
android——自定义控件（不停变化的textview、开关switch、动画效果的打勾）

android——自定义控件（不停变化的textview、开关switch、动画效果的打勾）

一、从开始数字到结束数字&#xff0c;不断变化 import android.animation.TypeEvaluator; import android.animation.ValueAnimator; import android.content.Context; import android.util.AttributeSet; import android.view.animation.AccelerateDecelerateInterpolator;i…
阅读更多...
设计模式-原型模式（克隆、Clone、Prototype）

设计模式-原型模式（克隆、Clone、Prototype）

原型模式&#xff08;克隆、Clone、Prototype&#xff09;是一种创建型设计模式&#xff0c; 使你能够复制已有对象&#xff0c; 而又无需使代码依赖它们所属的类。 问题 譬如美国研制了一种特效药&#xff0c;而且还在专利保护器内&#xff0c;而印度制药公司看中了&#xff0…
阅读更多...
2024 第一次周赛

2024 第一次周赛

A: 题目大意 骑士每连续 i 天每天会得到 i 个金币&#xff0c;&#xff08;i 1&#xff0c; 2&#xff0c; 3 &#xff0c; …&#xff09;,那么展开看每一天可以得到的金币数&#xff1a;1 2 2 3 3 3 4 4 4 5 5 5 5 5 … 可以发现就是1个1 &#xff0c;2个2, 3个3…,那么我…
阅读更多...
Flutter 3.24 发布：GPU模块及多视图嵌入功能

Flutter 3.24 发布：GPU模块及多视图嵌入功能

Flutter 3.24 发布&#xff1a;GPU模块及多视图嵌入功能 Flutter 3.24 带来了许多新功能和改进&#xff0c;让开发应用程序变得更加容易和有趣。这个版本重点展示了 Flutter GPU 的预览功能&#xff0c;让应用程序可以直接使用高级图形和 3D 场景功能。 此外&#xff0c;网页…
阅读更多...
win软件 超强的本地视频 图片去水印 动态水印！

win软件 超强的本地视频 图片去水印 动态水印！

AI视频图片去水印 HitPaw Watermark Remover 电脑软件&#xff0c;内涵安装教程&#xff0c;以后看到有水印的视频不怕啦&#xff0c;用这个就行了&#xff0c;可以去除动态水印&#xff01; 【下载】 https://pan.quark.cn/s/1ba6f088f0b2 【应用名称】:HitPaw Watermark R…
阅读更多...
ARIMA 模型初体验 —— 预测股票数据

ARIMA 模型初体验 —— 预测股票数据

第 1 步&#xff0c;从 twelvedata 上获取苹果 11 号 15:30 到 16:00 的 OHLC、成交量 数据。 第 2 步&#xff0c;编写 Python 代码&#xff08;实际上可以用 R 语言&#xff0c;R 语言从语言的级别对分析预测提供了支持&#xff0c;而 Python 需要第三方库&#xff09;。 …
阅读更多...
C++ day04（友元 friend、运算符重载、String字符串）

C++ day04（友元 friend、运算符重载、String字符串）

目录 【1】友元 friend 1》概念 2》友元函数 3》友元类 4》友元成员函数 【2】运算符重载 1》概念 2》友元函数运算符重载 ​编辑 3》成员函数运算符重载 4》赋值运算符与类型转换运算符重载 5》注意事项 【3】String 字符串类 【1】友元 friend 1》概念 定义&#x…
阅读更多...
BUUCTF-greatescape1

BUUCTF-greatescape1

发现有ftp包和tcp包居多 下载解压是个流量包&#xff0c;使用wiresharh打开&#xff0c;CTRLF&#xff0c;按下图搜索ftp tcp18流发现ssc.key 传送&#xff0c;在19流发现key内容 复制保存为ssc.key, 加载key解密tls&#xff0c;再追踪tls流可得flag INS{OkThatWasWay2Easy} …
阅读更多...
多元线性回归：机器学习中的经典模型探讨

多元线性回归：机器学习中的经典模型探讨

引言 多元线性回归是统计学和机器学习中广泛应用的一种回归分析方法。它通过分析多个自变量与因变量之间的关系&#xff0c;帮助我们理解和预测数据的行为。本文将深入探讨多元线性回归的理论背景、数学原理、模型构建、技术细节及其实际应用。 一、多元线性回归的背景与发展…
阅读更多...
基于Java的旅游网站管理系统—计算机毕业设计源码39235

基于Java的旅游网站管理系统—计算机毕业设计源码39235

摘 要 信息化社会内需要与之针对性的信息获取途径&#xff0c;但是途径的扩展基本上为人们所努力的方向&#xff0c;由于站在的角度存在偏差&#xff0c;人们经常能够获得不同类型信息&#xff0c;这也是技术最为难以攻克的课题。针对旅游网站等问题&#xff0c;对旅游网站进行…
阅读更多...
一区大黄蜂！人工蜂群算法优化！ABC-CNN-LSTM-MATT多特征分类预测

一区大黄蜂！人工蜂群算法优化！ABC-CNN-LSTM-MATT多特征分类预测

一区大黄蜂&#xff01;人工蜂群算法优化&#xff01;ABC-CNN-LSTM-MATT多特征分类预测 目录 一区大黄蜂&#xff01;人工蜂群算法优化&#xff01;ABC-CNN-LSTM-MATT多特征分类预测分类效果基本介绍程序设计参考资料 分类效果 基本介绍 1.Matlab实现ABC-CNN-LSTM-MATT人工蜂群…
阅读更多...
PDF转JPG神器！一键转换，轻松搞定文档分享

PDF转JPG神器！一键转换，轻松搞定文档分享

各位亲爱的小伙伴们&#xff0c;有没有遇到过需要把PDF文件转换成JPG图片的情况呢&#xff1f;今天我就来给大家推荐几款好用的PDF转JPG工具&#xff0c;让我们一起来看看这些工具的详细介绍和使用感受吧&#xff01; 一、福昕转换器 直通车&#xff08;粘贴到浏览器打开&…
阅读更多...
获取时隔半个钟的三天与el-time-select

获取时隔半个钟的三天与el-time-select

摘要&#xff1a; 今天遇到需求是配送时间&#xff0c;时隔半个钟的排线&#xff01;所以需要拼接时间&#xff01;例如2024-10-08 14&#xff1a;30&#xff0c;2024-10-08 15&#xff1a;00&#xff0c;2024-10-08 15&#xff1a;30 <el-form-item label"配送时间&a…
阅读更多...
优先算法1--双指针

优先算法1--双指针

“一念既出&#xff0c;万山无阻。”加油陌生人&#xff01; 目录 1.双指针--移动零 2.双指针-复写零 ok&#xff0c;首先在学习之前&#xff0c;为了方便大家后面的学习&#xff0c;我们这里需要补充一个知识点&#xff0c;我这里所谓的指针&#xff0c;不是之前学习的带有…
阅读更多...
如何构建高效的公路工程资料管理系统？

如何构建高效的公路工程资料管理系统？

本文介绍了构建高效的公路工程资料管理系统的方法&#xff0c;涵盖了系统需求分析、功能设计、开发平台选择、开发过程、系统上线与培训、持续改进与维护等关键环节。通过合理规划和科学管理&#xff0c;可以确保系统满足用户需求&#xff0c;提高工作效率&#xff0c;保障公路…
阅读更多...
react18+react-transition-group实现路由切换过度

react18+react-transition-group实现路由切换过度

效果如下 官网安装对应的插件 创建对应的样式 .fade-enter {opacity: 0; } .fade-exit {opacity: 1; } .fade-enter-active {opacity: 1; } .fade-exit-active {opacity: 0; } .fade-enter-active, .fade-exit-active {transition: opacity 500ms; }const location useLoca…
阅读更多...
STM32 | STM32F4OTA_ESP8266_Bootloader为引导程序远程更新的代码（APP）

STM32 | STM32F4OTA_ESP8266_Bootloader为引导程序远程更新的代码（APP）

更新。点击上方"蓝字"关注我们 01、思路 >>> STM32F4OTA_ESP8266_Bootloader为引导程序 远程更新的代码&#xff08;APP&#xff09;:远程更新的APP Ymoden_server&#xff1a;为运行在Linux的TCP服务器 备注&#xff1a;STM32 OTA远程更新需要连接热点 电…
阅读更多...
【实战项目】——Boost搜索引擎(五万字)

【实战项目】——Boost搜索引擎(五万字)

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 目录 前言 一、项目的相关背景 1.1、什么是Boost库&#xff1f; 1.2、什么是搜索引擎&#xff1f; 1.3、为什么要做Boost库搜索引擎&#xff1f; 二、搜索引擎的宏观原…
阅读更多...
【优选算法篇】双指针的优雅舞步：C++ 算法世界的浪漫探索

【优选算法篇】双指针的优雅舞步：C++ 算法世界的浪漫探索

文章目录 C 双指针详解&#xff1a;基础题解与思维分析前言第一章&#xff1a;对撞指针1.1 移动零解题思路图解分析C代码实现易错点提示代码解读 1.2 复写零解题思路算法步骤C代码实现易错点提示代码复杂度 1.3 盛最多水的容器1. 题目链接2. 题目描述解法一&#xff08;暴力求解…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023