C++中的数据结构与算法

ops/2024/11/14 20:05:58/

在这里插入图片描述

随处可见的红黑树

一般会用到[key,value]。
例如github中这个例子，第一个是访问网站，第二个是访问次数，但是这个不是静态的，这有个动态排序，并且当我们需要让相应的访问次数加1的时候，我们用红黑树查找的时候会比较快，所以用红黑树表示这个结构比较号。
在这里插入图片描述
所以红黑树普遍用于强查找过程。对于这种强查找的过程：我们普遍用rbtree，hash，b/b+ tree，或者跳表。

红黑树的性质和定义

红黑树的性质：
1.每个结点是红的或者黑的2.根结点是黑的
3.每个叶子结点是黑的
4.如果一个结点是红的，则它的两个儿子都是黑的(红红不相邻)
5.对每个结点，从该结点到其子孙结点的所有路径上的包含相同数目的黑结点
在这里插入图片描述

在这里插入图片描述在这里插入图片描述
对于一个红黑树的定义：注意这个nil指的是叶子节点，也就是那个隐藏的那个黑节点。

typedef int KEY_TYPE;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;

红黑树的左右旋

对于红黑树的旋转：
在这里插入图片描述
这里我们需要改变6根指针：
code:
这里主要需要判断的是x的parent是不是根节点。如果是的话，那么之间让根节点root指向y就行。
在这里插入图片描述

void rbtree_left_rotate(rbtree *T, rbtree_node *x) {rbtree_node *y = x->right;  // x  --> y  ,  y --> x,   right --> left,  left --> rightx->right = y->left; //1 1if (y->left != T->nil) { //1 2y->left->parent = x;}y->parent = x->parent; //1 3if (x->parent == T->nil) { //1 4T->root = y;} else if (x == x->parent->left) {x->parent->left = y;} else {x->parent->right = y;}y->left = x; //1 5x->parent = y; //1 6
}

右旋：
也就是上面的代码x改成y,right改成left。

void rbtree_right_rotate(rbtree *T, rbtree_node *y) {rbtree_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) {T->root = x;} else if (y == y->parent->right) {y->parent->right = x;} else {y->parent->left = x;}x->right = y;y->parent = x;
}

在这里插入图片描述

红黑树的插入

对于插入的时候我们都是一插到底，一直插到根节点。并且插入的节点定义为红色，然后再进行颜色的调整。而且它的父节点也是红色，因为原本的节点他的两个根是黑色，所以，这个父节点应该是红色。
因为红黑树在插入节点之前他已经是一个红黑树了。所以插入红色，不改变黑高的性质。
插入code:

void rbtree_insert(rbtree *T, rbtree_node *z) {rbtree_node *y = T->nil;rbtree_node *x = T->root;while (x != T->nil) {y = x;//y就是x的parentif (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，5.所以我们要让其先满足5在满足4。
还没调整前的情况：假设插入的节点是z，z的父节点是y

z是红色
z的父节点y也是红色
z的祖父节点是黑色
z的叔父节点是不确定

那么就两种情况：

  1. z的叔父节点是红色
    在这里插入图片描述
z->parent->color = BLACK;
y->color = BLACK;
z->parent->parent->color = RED;
z = z->parent->parent; //z --> RED,需要回溯
  1. z的叔父节点是黑色
    这两种情况是调整出来的，因为你调整完之后需要回溯，因为你调整完之后它的祖父可能不满足所以z = z->parent->parent。然后这种情况是要旋转的。然后旋转之后的图是中间状态的图，然后旋转完之后就是改色。
    在这里插入图片描述
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);

然后叔父节点是黑色的完整代码就是这个：

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);

然后父节点是祖父节点的左子树的情况代码就是这样的：

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; //z --> RED,需要回溯} 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);}
}

然后父节点是祖父节点的右子树的情况和上面差不多
完整代码就是：

void rbtree_insert_fixup(rbtree *T, rbtree_node *z) {while (z->parent->color == RED) { //z ---> REDif (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; //z --> RED,需要回溯} 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; //z --> RED} 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;
}

红黑树的删除

这个比较难，不需要掌握
完整代码：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>#define RED				1
#define BLACK 			2typedef int KEY_TYPE;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;rbtree_node *rbtree_mini(rbtree *T, rbtree_node *x) {while (x->left != T->nil) {x = x->left;}return x;
}rbtree_node *rbtree_maxi(rbtree *T, rbtree_node *x) {while (x->right != T->nil) {x = x->right;}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;
}void rbtree_left_rotate(rbtree *T, rbtree_node *x) {rbtree_node *y = x->right;  // x  --> y  ,  y --> x,   right --> left,  left --> rightx->right = y->left; //1 1if (y->left != T->nil) { //1 2y->left->parent = x;}y->parent = x->parent; //1 3if (x->parent == T->nil) { //1 4T->root = y;} else if (x == x->parent->left) {x->parent->left = y;} else {x->parent->right = y;}y->left = x; //1 5x->parent = y; //1 6
}void rbtree_right_rotate(rbtree *T, rbtree_node *y) {rbtree_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) {T->root = x;} else if (y == y->parent->right) {y->parent->right = x;} else {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 ---> REDif (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; //z --> RED,需要回溯} 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; //z --> RED} 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;
}void rbtree_insert(rbtree *T, rbtree_node *z) {rbtree_node *y = T->nil;rbtree_node *x = T->root;while (x != T->nil) {y = x;//y就是x的parentif (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);
}void rbtree_delete_fixup(rbtree *T, rbtree_node *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->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) {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);}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);}
}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");}}

b/b+树


http://www.ppmy.cn/ops/22718.html

相关文章

理解原型和原型链

理解原型和原型链

当你理解JavaScript中的原型和原型链&#xff0c;你就能理解为什么JavaScript中一切皆对象&#xff0c;以及为什么函数也是对象。让我帮你梳理一下。 原型 (Prototype) 在JavaScript中&#xff0c;每个对象都有一个原型对象&#xff08;prototype&#xff09;。当你创建一个对…
阅读更多...
Matlab实现CNN-LSTM模型，对一维时序信号进行分类

Matlab实现CNN-LSTM模型，对一维时序信号进行分类

1、利用Matlab2021b训练CNN-LSTM模型&#xff0c;对采集的一维时序信号进行分类二分类或多分类 2、CNN-LSTM时序信号多分类执行结果截图 训练进度&#xff1a; 网络分析&#xff1a; 指标变化趋势&#xff1a; 代码下载方式&#xff08;代码含数据集与模型构建&#xff0c;附…
阅读更多...
Quarto Dashboards 教程 3：Dashboard Data Display

Quarto Dashboards 教程 3：Dashboard Data Display

「写在前面」 学习一个软件最好的方法就是啃它的官方文档。本着自己学习、分享他人的态度&#xff0c;分享官方文档的中文教程。软件可能随时更新&#xff0c;建议配合官方文档一起阅读。推荐先按顺序阅读往期内容&#xff1a; 1.quarto 教程 1&#xff1a;Hello, Quarto 2.qu…
阅读更多...
18.Nacos配置管理-微服务读取Nacos中的配置

18.Nacos配置管理-微服务读取Nacos中的配置

需要解决的问题 1.实现配置更改热更新&#xff0c;而不是改动了配置文件还要去重启服务才能生效。 2.对多个微服务的配置文件统一集中管理。而不是需要对每个微服务逐一去修改配置文件&#xff0c;特别是公共通用的配置。 配置管理服务中的配置发生改变后&#xff0c;回去立…
阅读更多...
找不到mfc140.dll如何解决？mfc140.dll丢失的几种解决方法分享

找不到mfc140.dll如何解决？mfc140.dll丢失的几种解决方法分享

在我们启动并开始利用电脑进行日常工作的过程中&#xff0c;如果遭遇了操作系统提示“mfc140.dll文件丢失”的错误信息&#xff0c;导致某些应用程序无法正常运行&#xff0c;这究竟是何种情况呢&#xff1f;小编将介绍计算机缺失mfc140.dll文件的5种解决方法&#xff0c;帮助大…
阅读更多...
OpenHarmony 实战开发——分布式购物车案例展示~

OpenHarmony 实战开发——分布式购物车案例展示~

简介 分布式购物车demo 模拟的是我们购物时参加满减活动&#xff0c;进行拼单的场景&#xff1b;实现两人拼单时&#xff0c;其他一人添加商品到购物车&#xff0c;另外一人购物车列表能同步更新&#xff0c;且在购物车列表页面结算时&#xff0c;某一人结算对方也能实时知道结…
阅读更多...
七、OSPF特殊区域及其特性

七、OSPF特殊区域及其特性

目录 OSPF区域分类 hello报文中option字段 1.末节区域&#xff08;Stub区域&#xff09; 2.完全末节区域&#xff08;Toally Stub区域&#xff09; 3.七类LSA 4.非完全末节区域&#xff08;NSSA区域&#xff09; 5.完全非完全末节区域&#xff08;Toally NSSA区域&#…
阅读更多...
Linux基础命令[24]-su

Linux基础命令[24]-su

文章目录 1. su 命令说明2. su 命令语法3. su 命令示例3.1 不加参数3.2 -&#xff08;登录&#xff09;3.3 -c&#xff08;执行命令&#xff09; 4. 总结 1. su 命令说明 su&#xff1a;以用户身份执行命令&#xff0c;基本信息如下&#xff1a; Usage:su [options] [-] [USE…
阅读更多...
最新文章

Copyright @ 2022~2023