威海有名的做网站,常熟有哪些网站建设公司,国内重大新闻事件2021年10月,装修风格大全2023新款文章目录 一、红黑树简介二、 红黑树特性三、红黑树插入3.1 红黑树为空3.2 父节点为黑色3.3 父节点为红色3.3.1 父亲和叔叔都是红色3.3.2 父节点为红色#xff0c;叔叔节点为黑色3.3.2.1 父节点在左节点#xff0c;插入节点在父亲左节点3.3.2.2 父节点在左节点#xff0c;插… 文章目录 一、红黑树简介二、 红黑树特性三、红黑树插入3.1 红黑树为空3.2 父节点为黑色3.3 父节点为红色3.3.1 父亲和叔叔都是红色3.3.2 父节点为红色叔叔节点为黑色3.3.2.1 父节点在左节点插入节点在父亲左节点3.3.2.2 父节点在左节点插入节点在父亲右节点3.3.2.3 父节点在右节点插入节点在父亲右节点3.3.2.4 父节点在右节点插入节点在父亲左节点 四、红黑树删除4.1 删除既有左子树又有右子树节点4.2 删除有左子树或者右子树节点4.2.1 不存在情况4.2.2 存在情况4.2.3 删除节点 4.3 删除叶子节点4.3.1 叶子节点是红色4.3.2 叶子节点是黑色4.3.2.1 叶子节点是左节点兄弟节点红色4.3.2.2 叶子节点是左节点兄弟节点黑色4.3.2.2.1 兄弟节点右孩子为红色左孩子任意颜色4.3.2.2.2 兄弟节点左孩子为红色右孩子为黑色4.3.2.2.3 兄弟节点左右孩子为黑色父亲节点红色父亲节点黑色 4.3.2.3 叶子节点是右节点兄弟节点红色4.3.2.4 叶子节点是右节点兄弟节点黑色4.3.2.4.1 兄弟节点左孩子为红色右孩子任意颜色4.3.2.4.2 兄弟节点右孩子为红色左孩子黑色4.3.2.4.3 兄弟节点左右孩子为黑色父亲节点红色父亲节点黑色 五、红黑树查询六、红黑树中序遍历 一、红黑树简介
以前只是在考研学408的时候接触到红黑树但是当时并没有做深入的了解。最近在做一个KV存储的项目Key-Value的存储需要一个比数组更佳高效进行插入和删除的数据结构。红黑树hash都是不错的用来存储的数据结构。
红黑树也是一种自平衡二叉查找树它与AVL树类似都在添加和删除的时候通过旋转操作保持二叉树的平衡以求更高效的查询性能。
与AVL树相比红黑树牺牲了部分平衡性以换取插入/删除操作时较少的旋转操作整体来说性能要优于AVL树。
二、 红黑树特性
红黑树是实际应用中最常用的平衡二叉查找树它不严格的具有平衡属性但平均的使用性能非常良好。
在红黑树中节点被标记为红色和黑色两种颜色。
红黑树原则有以下几点 1根节点和叶节点一定是黑色(根叶黑) 2从叶子到根的两个连续节点不能都是红色节点(不红红) 3父节点的值大于左节点的值小于右节点的值(左根右) 4从任一节点到其他每个叶子的所有路径包含相同数目的黑色节点(黑路同)
三、红黑树插入
红黑树节点和树的结构体定义
typedef struct _rbtree_node {unsigned char color;struct _rbtree_node *right;struct _rbtree_node *left;struct _rbtree_node *parent;KEY_TYPE key;void *value;
} rbtree_node;typedef struct _rbtree {rbtree_node *root;rbtree_node *nil;
} rbtree;因为父节点为黑色的概率较大插入新节点为红色可以避免颜色冲突所以默认插入节点的颜色为红色
3.1 红黑树为空
直接插入节点根据根叶黑的特性设置为黑色
3.2 父节点为黑色
由于插入的是红色不影响红黑树平衡
3.3 父节点为红色
因为父节点是红色所以父节点不可能是根节点 父节点为红色时会出现两种情况1叔叔为红色2叔叔为黑色
3.3.1 父亲和叔叔都是红色
处理方式 1将M和N变黑P变红; 2将P设置为当前节点; 如果P的父节点是黑色则无需处理如果P的父节点是红色违反了不红红特性继续调整
3.3.2 父节点为红色叔叔节点为黑色
3.3.2.1 父节点在左节点插入节点在父亲左节点
这是一种插入后的LL型失衡 处理方式 1对P和M变色 2对P右旋
3.3.2.2 父节点在左节点插入节点在父亲右节点
这是一种插入后的LR型失衡 处理方式 1对M进行左旋; 2将M设置为当前节点; 3转换为 父节点在左节点插入节点在父亲左节点 情况
3.3.2.3 父节点在右节点插入节点在父亲右节点
这是一种插入后的RR型失衡 处理方式 1将M和P变色 2对P左旋
3.3.2.4 父节点在右节点插入节点在父亲左节点
这是一种插入后的RL型失衡 处理方式 1对M点右旋 2将M设置为当前节点 3转换为 父节点在右节点插入节点在父亲左节点 情况 下面的代码是关于红黑树插入的实现 //x为需要左旋的节点
void rbtree_left_rotate(rbtree *T, rbtree_node *x) {//支点rbtree_node *y x-right; // x -- y , y -- x, right -- left, left -- right//支点左节点赋给x右节点x-right y-left; if (y-left ! T-nil) { //更改支点左节点的父节点y-left-parent x;}y-parent x-parent; //1 3if (x-parent T-nil) { //x是root节点情况T-root y;} else if (x x-parent-left) {//x父节点的左孩子x-parent-left y;} else {x-parent-right y;}y-left x; //1 5x-parent y; //1 6
}//y为需要右旋的节点
void rbtree_right_rotate(rbtree *T, rbtree_node *y) {//支点pivotrbtree_node *x y-left;y-left x-right;if (x-right ! T-nil) {x-right-parent y;}x-parent y-parent;if (y-parent T-nil) {//y是root情况T-root x;} else if (y y-parent-right) {//y是右孩子y-parent-right x;} else {//y是左孩子y-parent-left x;}x-right y;y-parent x;
}void rbtree_insert_fixup(rbtree *T, rbtree_node *z) {//父亲节点如果是黑色插入红色节点可以不变化while (z-parent-color RED) { //z --- RED//判断是爷爷节点的左边的L型还是右边的R型if (z-parent z-parent-parent-left) {//L型//指向叔叔节点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; //z -- RED} else {//叔叔节点为黑//将LR型转为LL型处理if (z z-parent-right) {z z-parent; //这行代码用于当是LR型时将z-parent设置为当前节点//对插入节点的父节点左旋rbtree_left_rotate(T, z);}//LL型z-parent-color BLACK;z-parent-parent-color RED;//将当前节点的爷爷节点右旋rbtree_right_rotate(T, z-parent-parent);}}else {//R型//指向叔叔节点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; //z -- RED} else {//叔叔节点为黑色if (z z-parent-left) {//RL型//设置 z-parent为当前节点z z-parent;//z-parent右转rbtree_right_rotate(T, z);}//RR型z-parent-color BLACK;z-parent-parent-color RED;//当前节点的爷爷节点左旋rbtree_left_rotate(T, z-parent-parent);}}}T-root-color BLACK;
}void rbtree_insert(rbtree *T, rbtree_node *z) {//指向叶节点rbtree_node* y T-nil;//指向根节点rbtree_node* x T-root;//y指向将要插入节点的父节点while (x ! T-nil) {y x;if (z-key x-key) {x x-left;} else if (z-key x-key) {x x-right;} else { //Existreturn ;}}z-parent y;if (y T-nil) { //是否为空树T-root z;} else if (z-key y-key) { //插入左子树y-left z;} else { //插入右子树y-right z;}z-left T-nil;z-right T-nil;//将插入节点设置为红色z-color RED;rbtree_insert_fixup(T, z);
}四、红黑树删除
根据红黑树的性质我们要删除的节点类型大致分为三种
1叶子节点 2有左子树或者右子树节点 3既有左子树又有右子树节点
4.1 删除既有左子树又有右子树节点
对于一棵普通二叉树来说要删除既有左子树又有右子树的节点我们首先要找到该节点的直接后继节点然后用后继节点替换该节点最后按1或2中的方法删除后继节点即可。所以情况3可以转换为情况1或2。
对于红黑树来说我们实际上删除的节点情况只有1和2。
4.2 删除有左子树或者右子树节点
4.2.1 不存在情况
情况二中有很多情况其实是不存在的这些情况都违背了红黑树的性质(P代表需要删除的节点) 上面四种情况违背了黑路同的性质(P代表需要删除的节点) 上面两种情况违背了不红红的性质(P代表需要删除的节点)
4.2.2 存在情况
结合上面的分析我们能发现对于只有左子树或者右子树的类型其实只有下面的组合类型(P代表需要删除的节点)
4.2.3 删除节点
这两种情况的处理方法都是一样的使用P的孩子M替换P并且将M的颜色改为黑色即可。
4.3 删除叶子节点
4.3.1 叶子节点是红色 上面这两种情况都是一样的直接删除P节点
4.3.2 叶子节点是黑色
4.3.2.1 叶子节点是左节点兄弟节点红色
处理过程 1将父节点P和兄弟节点M交换颜色(D是要删除节点是当前节点) 2对P左旋 这个结果演变成后面讨论的兄弟节点是黑色情况(D是要删除节点)
4.3.2.2 叶子节点是左节点兄弟节点黑色
4.3.2.2.1 兄弟节点右孩子为红色左孩子任意颜色
白色表示红色或者黑色都可以 处理过程(D是要删除节点是当前节点) 1P和M颜色对调 2P进行左旋 3删除D 4MR设置为黑色
4.3.2.2.2 兄弟节点左孩子为红色右孩子为黑色
白色表示红色或者黑色都可以 处理过程(D是要删除节点是当前节点) 1ML和M颜色对调 2M进行左旋 3情况转换为 兄弟节点右孩子为红色左孩子任意颜色
4.3.2.2.3 兄弟节点左右孩子为黑色
父亲节点红色
处理过程(D是要删除节点是当前节点) 1P和M颜色对调 2删除D
父亲节点黑色
处理过程(D是要删除节点是当前节点) 1M颜色设置为红色 2删除D
4.3.2.3 叶子节点是右节点兄弟节点红色
处理过程(D是要删除节点是当前节点) 1P和M颜色对调 2P进行左旋 这个结果演变成后面讨论的兄弟节点是黑色情况(D是要删除节点)
4.3.2.4 叶子节点是右节点兄弟节点黑色
4.3.2.4.1 兄弟节点左孩子为红色右孩子任意颜色
处理过程(D是要删除节点是当前节点) 1P和M颜色对调 2P进行左旋 3删除D 4ML设置为黑色
4.3.2.4.2 兄弟节点右孩子为红色左孩子黑色
白色表示红色或者黑色都可以 处理过程(D是要删除节点是当前节点) 1MR和M颜色对调 2M进行左旋 3情况转换为 兄弟节点左孩子为红色右孩子任意颜色
4.3.2.4.3 兄弟节点左右孩子为黑色
父亲节点红色
处理过程(D是要删除节点是当前节点) 1P和M颜色对调 2删除D
父亲节点黑色
处理过程(D是要删除节点是当前节点) 1M颜色设置为红色 2删除D
下面是实现红黑树删除的代码
void rbtree_delete_fixup(rbtree *T, rbtree_node *x) {//对于有左子树或者右子树情况因为只有黑红模式所以传进来的x只能是红色//对于有左右子树情况可以转换为叶子结点或者只有左子树或者又子树情况//下面的循环主要用于处理叶子结点是黑色的情况且叶子节点的空节点不为根节点(代表树为空)while ((x ! T-root) (x-color BLACK)) {//删除节点是左孩子if (x x-parent-left) {//删除节点的兄弟节点rbtree_node *w x-parent-right;if (w-color RED) {//如果兄弟节点为红色//父节点和兄弟节点颜色互换w-color BLACK;x-parent-color RED;//父节点左旋rbtree_left_rotate(T, x-parent);//更新被删除节点的兄弟节点w x-parent-right;}//兄弟节点为黑色兄弟节点左右孩子都是黑色if ((w-left-color BLACK) (w-right-color BLACK)) {//兄弟节点设置为红w-color RED;//重新设置起始点点x x-parent;} else {//兄弟节点为黑色右孩子是黑色左孩子红色---》右孩子变为红色if (w-right-color BLACK) {//w和w的w-left-color BLACK;w-color RED;//兄弟节点右旋rbtree_right_rotate(T, w);//更新删除节点的兄弟节点w x-parent-right;}//兄弟节点为黑色右孩子为红色情况//兄弟节点和父节点颜色互换w-color x-parent-color;x-parent-color BLACK;//变换兄弟节点右孩子颜色w-right-color BLACK;//对父节点做左旋rbtree_left_rotate(T, x-parent);//结束x T-root;}//删除节点是右孩子} else {//删除节点的兄弟节点rbtree_node *w x-parent-left;if (w-color RED) {//如果兄弟节点为红色//父节点和兄弟节点颜色互换w-color BLACK;x-parent-color RED;//父节点右旋rbtree_right_rotate(T, x-parent);//更新被删除节点的兄弟节点w x-parent-left;}//兄弟节点为黑色兄弟节点左右孩子都是黑色if ((w-left-color BLACK) (w-right-color BLACK)) {//兄弟节点设为红色w-color RED;//重新设置起始点点x x-parent;} else {//兄弟节点为黑色左孩子是黑色右孩子红色---》左孩子变为红色if (w-left-color BLACK) {w-right-color BLACK;w-color RED;rbtree_left_rotate(T, w);w x-parent-left;}//兄弟节点为黑色左孩子为红色情况//兄弟节点和父节点颜色互换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_delete(rbtree *T, rbtree_node *z) {//z指向想删除节点y指向当前节点x指向当前节点的孩子rbtree_node *y T-nil;rbtree_node *x T-nil;//z节点至多有一个孩子节点if ((z-left T-nil) || (z-right T-nil)) {y z;//当前节点设置为要删除节点} else {//z节点有两个孩子节点y rbtree_successor(T, z);//当前节点设置为后继节点}//双孩子改变后的当前点左右两个节点都是空节点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;
}五、红黑树查询
因为红黑树的性质中有左跟右所以每次只需要和父节点比较大小即可下面是查询实现代码
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);}
}
