安徽省住房建设部官方网站,迁西网站定制,做平台网站一般有php还是js,佛山大型网站设计公司文章目录前言一、红黑树的概念二、红黑树的节点结构三、红黑树的插入四、红黑树的调整1、叔叔存在且为红2、叔叔不存在或存在且为黑3、插入完整代码4、总结五、红黑树的验证六、红黑树的删除七、红黑树与 AVL 树的比较八、红黑树的代码实现前言
在网络上流传着这样一张图片
这张图片表达的侧面意思是红黑树非常难但如果认真阅读了这篇的博客并且你有 AVL 树的基础的话 (重点是 AVL 树的旋转)其实你会发现红黑树难只是指红黑树比较抽象但它的逻辑其实是比 AVL 树要简单的并且红黑树的代码也不难写。 一、红黑树的概念
什么是红黑树
红黑树是一种平衡二叉搜索树但和 AVL 树使用高度来控制平衡不同红黑树在每个结点上增加一个存储位来表示结点的颜色可以是Red或Black然后通过对任何一条从根到叶子的路径上各个结点着色方式的限制来达到接近平衡
红黑树通过对每个节点颜色的限制从而使得整棵树的最长路径不超过最短路径的两倍 (注意是整棵树对子树没有要求)这样红黑树就可以达到接近平衡。 注意因为红黑树只要求整棵树中最长路径是最短路径的两倍所以红黑树是近似平衡的即子树中某一路径可能比另一条路径长两倍不止但 AVL 是通过高度控制平衡的且 AVL 能达到的平衡已经是二叉树中能够达到的最好平衡了所以 AVL 树是绝对平衡的。 红黑树的性质
红黑树有如下性质
每个结点不是红色就是黑色根节点是黑色的如果一个节点是红色的则它的两个孩子结点是黑色的 – 不允许出现连续的红色节点对于每个结点从该结点到其所有后代叶结点的简单路径上均包含相同数目的黑色结点 – 每条路径都包含相同数量的黑色节点每个叶子结点都是黑色的 (此处的叶子结点指的是空结点) 特别注意第五点中的叶子节点并不是指我们平时说的叶子节点而是指的空节点 (图中的NIL节点)它之所以要加这么一条规则是为了更好的标识每条路径 (比如认为图中的13 8 1 NIL 也是一条路径)但是我认为我们完全可以不用管第五点而且这样也不会造成什么影响因为如果不计算 NIL 节点那么树中所有路径的黑色节点数量都会减一并不会违反规则4所以可以看到第五点我是用删除线进行修饰的。 思考为什么满足上面的性质红黑树就能保证其最长路径中节点个数不会超过最短路径节点个数的两倍
我们可以在极端场景下来思考这个问题 – 极端场景下当一条路径中的全部节点都为黑色时该路径为最短路径当一条路径中黑色节点与红色节点交替时该路径为最长路径此时最长路径刚好为最短路径的两倍如下 二、红黑树的节点结构
红黑树的节点结构和 AVL 树整体上类似三个节点指针分别指向左孩子、右孩子和父亲然后还包含一个 pair 键值对和 AVL 树不同的时红黑树不再需要 bf 变量来作为树的平衡因子而是需要一个 col 变量来标识节点的颜色
//节点颜色
enum Color {RED,BLACK
};templateclass K, class V
struct RBTreeNode {RBTreeNodeK, V* _left;RBTreeNodeK, V* _right;RBTreeNodeK, V* _parent;std::pairK, V _kv;Color _col; //节点颜色RBTreeNode(const std::pairK, V kv): _kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr), _col(RED) //默认给成红色{}
};可以看到在构造函数的初始化列表中我们将节点的颜色默认初始化为 RED这是因为新增节点的颜色默认给成红色更合适原因如下
如果新增节点的颜色为红色那么这里存在三种情况一是新增节点为根节点此时我们需要将节点颜色改为黑色二是新增节点的父节点颜色为红色由于红黑树中不能出现连续的红色节点所以我们需要进行调整三是新增节点的父节点颜色为黑色此时我们不需要做任何事因为新增节点没有违反红黑树的性质。而如果新增节点的颜色为黑色那我们一定需要对该节点进行调整因为新增节点会导致这条路径的黑色节点数量比其他所有路径的黑色节点数量多一违反了红黑树的性质4。综合考量上面两种情况我们认为将新增节点颜色默认设置为红色更合适 (黑色必调整且很难调整红色可能调整且调整较易)。 三、红黑树的插入
红黑树插入的前面部分很简单就是一般二叉搜索树的插入逻辑需要注意的是如果插入的节点是根节点则我们需要将节点的颜色改为黑色因为新增节点默认是被初始化为红色的
红黑树插入的难点在于检测插入后红黑树的性质是否被破坏其一共可以分为两种情况
父节点的颜色为黑色此时没有违反红黑树任何性质不需要调整父节点的颜色为红色此时出现了连续红色节点需要进行调整。
bool insert(const std::pairK, V kv) {//判断根节点是否为空if (_root nullptr) {_root new Node(kv);_root-_col BLACK; //根节点的颜色一定为黑return true;}//寻找插入位置Node* parent nullptr;Node* cur _root;while (cur) {if (kv.first cur-_kv.first) {parent cur;cur cur-_left;}else if (kv.first cur-_kv.first) {parent cur;cur cur-_right;}else {return false; //不允许重复节点}}//走到空开始插入注意这里还需要修改父节点的指向//新增节点的颜色为默认被初始化为红色所以这里不需要再显式赋值Node* newNode new Node(kv);if (kv.first parent-_kv.first)parent-_left newNode;elseparent-_right newNode;newNode-_parent parent; //修改父节点指向//如果父节点颜色为红色则需要进行调整//红黑树的调整
}而红黑树的调整又分为两种情况(约定cur为当前节点p为父节点g为祖父节点u为叔叔节点)
叔叔存在且为红此时我们只需要进行变色叔叔不存在或者叔叔存在且为黑此时我们需要进行旋转变色。
下面我们来具体探讨这两种情况。 四、红黑树的调整
1、叔叔存在且为红
如果cur为红p为红g为黑u存在且为红此时我们只需要将p和u变黑再将g变红即可 (约定cur为当前节点p为父节点g为祖父节点u为叔叔节点)
可以看到当p为红时由于g是p的父亲所以g一定为黑如果此时叔叔存在且为红那么我们只需要将p和u变黑再将g变红即可这样做不会改变g这棵子树黑色节点的数量所以不会影响到其他路径同时g的子树中每条路径的黑色节点数量也是相同的符合红黑树的性质。
节点颜色修改完毕之后这里又分为两种情况
g是根节点由于根节点必须为黑所以我们需要将g的颜色置为黑g不是根节点由于我们将g变成了红色而我们并不知道g的父亲是不是红色所以我们需要将g作为新增节点 继续向上调整然后再下一层循环中再进行判断与调整。
另外和 AVL 树中旋转的图一样这里给出的也是抽象图其中 a/b/c/d/e 代表的是高度为 h 的红黑树子树h 可以取任何非负整数所以这张图代表的是一类情况我们以 h 1 为例 (图中给出的组合数并不一定是准确的) 注意上面我们是以左左为例子进行讨论的但其实上面的处理方式也适用于 右右、左右、右左 的情况 (注意这里的左左、右右、左右、右左和上一节 AVL 树里面的其实是差不多的只是红黑树不通过平衡因子来控制平衡所以进行 if 条件需要进行相应的调整而已) 也就是说只要叔叔存在且为红那么无论是插入节点的父亲在祖父节点的左边还是右边插入节点在父亲的左边还是右边都没有关系统一将父节点和叔叔节点变黑将祖父节点变红。 2、叔叔不存在或存在且为黑
之所以将叔叔不存在与叔叔存在且为黑分为一类情况是因为它们的处理方式是相同的 (约定cur为当前节点p为父节点g为祖父节点u为叔叔节点) 当u不存在时cur一定是新插入节点因为如果cur不是新插入节点则cur和p中一定有一个节点的颜色是黑色否则不满足性质4 – 每条路径黑色节点个数相同此时我们的操作是旋转 变色其中旋转会根据父节点位置和插入节点位置的不同分为四种情况而变色是统一将旋转后子树的根节点变为黑色将根的左右节点变为红色。 如果u存在且为黑那么cur节点原来的颜色一定是黑色的现在看到其是红色是因为cur的子树之前为情况1然后情况1调整后将祖父节点也就是cur节点变成了红色否则g左子树的黑色节点数量会比右子树黑色节点数量少1违反性质4此时我们的操作和u不存在时一模一样 – 旋转 变色旋转分为四种情况变色统一将旋转后子树的根节点变为黑色将根的左右节点变为红色所以说我们可以将u不存在和u存在且为黑分同一类 (本质是我们不会改变u及其子树的颜色)。
红黑树的旋转 – 和 AVL 树一样红黑树会根据父节点位置的不同和插入节点位置的不同选择不同的旋转方式来进行调整旋转一共分为四类
右单旋 – 父节点在祖父节点的左侧cur 在父节点的左侧左单旋 – 父节点在祖父节点的右侧cur 在父节点的右侧左右双旋 – 父节点在祖父节点的左侧cur 在父节点的右侧右左双旋 – 父节点在祖父节点的右侧cur 在父节点的左侧。
可以看到红黑树的旋转其实就是 AVL 树中的四种旋转只不过红黑树中不再需要更新平衡因子而是需要更新节点颜色而已不过红黑树中叔叔不存在或存在且为黑情况下节点颜色的更新十分简单 – 统一将旋转后子树的根节点变为黑色将根的左右节点变为红色即可。
需要注意的是和情况1 – 叔叔存在且为红不同由于这里我们将祖父节点的颜色改为黑色 (旋转后子树的根节点为祖父节点)所以不用考虑祖父的父节点为红色从而违反性质4的问题即 这里我们不需要继续向上调整。
最后由于左单旋、右单旋、左右双旋和右左双旋这四种旋转我们在上一节 AVL 树中已经讲解的十分清楚所以这里我们不再重复讲解而仅仅是给出左右双旋和右左双旋两种情况的例图 (由于右单旋的例图在上面我们已经给出所以下面只给出双旋的例图)如果看不懂例图或对旋转的细节有疑问的同学可以再回顾一下上一节
左右双旋的情况如下
右左双旋的情况如下
3、插入完整代码
旋转的代码如下
bool insert(const std::pairK, V kv) {//判断根节点是否为空if (_root nullptr) {_root new Node(kv);_root-_col BLACK; //根节点的颜色一定为黑return true;}//寻找插入位置Node* parent nullptr;Node* cur _root;while (cur) {if (kv.first cur-_kv.first) {parent cur;cur cur-_left;}else if (kv.first cur-_kv.first) {parent cur;cur cur-_right;}else {return false; //不允许重复节点}}//走到空开始插入注意这里还需要修改父节点的指向//新增节点的颜色为默认被初始化为红色所以这里不需要再显式赋值Node* newNode new Node(kv);if (kv.first parent-_kv.first)parent-_left newNode;elseparent-_right newNode;newNode-_parent parent; //修改父节点指向cur newNode;//如果父节点颜色为红色则需要进行调整且最多调整到根while (parent parent-_col RED) {Node* grandfater parent-_parent; //祖父节点if (grandfater nullptr)break;//如果父节点在祖父节点的左边if (parent grandfater-_left) {Node* uncle grandfater-_right; //叔叔节点//情况一叔叔存在且为红--父和叔叔变黑爷爷变红继续向上调整if (uncle uncle-_col RED) {parent-_col BLACK;uncle-_col BLACK;grandfater-_col RED;//继续向上调整cur grandfater;parent cur-_parent;}//情况二叔叔不存在或叔叔存在且为黑else {//如果cur在parent的左边则右单旋--注意走到这里p已经是g的左边了if (cur parent-_left) {rotateR(grandfater);//更新节点颜色parent-_col BLACK;cur-_col grandfater-_col RED;}else { //左右双旋//先以parent为轴进行左单旋rotateL(parent);//再以grandfather进行右单旋rotateR(grandfater);//更新节点颜色--此时cur为子树的根节点cur-_col BLACK;parent-_col grandfater-_col RED;}//最后需要跳出循环因为此时不会再影响上层break;}}//如果父节点在祖父节点的右边else {Node* uncle grandfater-_left; //叔叔节点//情况一叔叔存在且为红--父和叔叔变黑爷爷变红继续向上调整if (uncle uncle-_col RED) {parent-_col BLACK;uncle-_col BLACK;grandfater-_col RED;//继续向上调整cur grandfater;parent cur-_parent;}//情况二叔叔不存在或叔叔存在且为黑else {//如果cur在parent的右边则左单旋--注意走到这里p已经是g的右边了if (cur parent-_right) {rotateL(grandfater);//更新节点颜色parent-_col BLACK;cur-_col grandfater-_col RED;}else { //右左双旋//先以parent为轴进行右单旋rotateR(parent);//再以grandfather进行左单旋rotateL(grandfater);//更新节点颜色--此时cur为子树的根节点cur-_col BLACK;parent-_col grandfater-_col RED;}//最后需要跳出循环因为此时不会再影响上层break;}}}//在循环外面将_root的颜色重新置黑避免循环内部将根节点的颜色变红了_root-_col BLACK;return true;
}4、总结
红黑树节点的调整其实很简单一共就两种情况(注意新增节点一定要初始化为红色)
父节点的颜色为黑色此时没有违反红黑树任何性质不需要调整父节点的颜色为红色此时出现了连续红色节点需要进行调整调整又分为两种情况 若叔叔存在且为红则将父亲和叔叔置黑、祖父置红然后继续往上调整叔叔不存在或者叔叔存在且为黑此时我们需要进行旋转变色 – 旋转根据父节点和cur节点位置的不同分为左单旋、右单旋、左右双旋和右左双旋变色统一将旋转后的子树的根节点置黑、根节点的左右节点置红即可调整完成后不需要继续往上调整。
简单来说红黑树如何调整取决于叔叔节点。 五、红黑树的验证
红黑树的验证和 AVL 树一样验证一共分为两部分
验证是否为二叉搜索树验证其是否满足红黑树的性质
验证二叉搜索树很简单我们向树中插入数据然后实现一个 InOrder 函数看遍历得到的数据是否有序即可。
//中序遍历
void InOrder() {return _inOrder(_root);
}void _inOrder(Node* root) {if (root nullptr)return;_inOrder(root-_left);std::cout root-_kv.first root-_kv.second std::endl;_inOrder(root-_right);
}验证平衡则比较麻烦因为我们需要分别验证红黑树的几个性质 – 根节点为黑色不允许出现连续的红色每条路径黑色节点的数量是红色节点数量的两倍同时在验证的过程中我们可以顺便将不符合要求的地方的节点的key值打印出来方便发生错误时进行调试
bool Check(Node* root, int blackCount, int baseCount) {//如果走到空说明这条路径结束了此时看count与baseCount是否相等if (root nullptr) {if (blackCount ! baseCount) {std::cout 此路径黑色节点数量有误节点key值 root-_kv.first std::endl;return false;}return true;}//检查是否出现连续红色节点if (root-_col RED) {if (root-_parent-_col RED) { //红色节点一定有父亲因为根节点为黑色std::cout 出现连续红色节点节点key值 root-_kv.first std::endl;}}if (root-_col BLACK)blackCount;return Check(root-_left, blackCount, baseCount) Check(root-_right, blackCount, baseCount);
}//验证红黑树的性质
bool IsBanlance() {if (_root nullptr)return true;//检查根节点if (_root-_col RED) {std::cout 根节点为红 std::endl;return false;}//以最左路径黑色节点数量为基准同其他路径的黑色节点数量相比较看是否相等int baseCount 0;Node* cur _root;while (cur) {if (cur-_col BLACK)baseCount;cur cur-_left;}//检查红黑树的其他性质return Check(_root, 0, baseCount);
}如果我们用几千上万甚至几十上百万个随机数测试出来的结果都是真那么我们的 红黑树 就基本上没问题了当然前提是你的 IsBanlance 函数没写错。 六、红黑树的删除
和 AVL 树一样红黑树的删除我们作为了解内容即可如果对其特别感兴趣的同学可以参考一下《算法导论》或者《STL源码剖析》也可以看看下面这位大佬的博客红黑树 - Never - 博客园 (cnblogs.com) 七、红黑树与 AVL 树的比较
红黑树和 AVL 树都是高效的平衡二叉树增删改查的时间复杂度都是 O(logN)但由于红黑树不追求绝对平衡只需要保证最长路径不超过最短路径的2倍所以在某些极端情况下红黑树的查询效率相较于 AVL 树要低一点点例如当树左子树全部为黑色节点右子树全部为一黑一红交替时红黑树的高度差不多是 AVL 树的两倍但是此时红黑树的查询效率仍然属于 O(logN) 这个量级
不过也正是由于红黑树不要求左右子树绝对平衡所以红黑树相较于 AVL 树在插入和删除时的旋转次数要少一些所以在经常进行增删的结构中红黑树的性能比 AVL 树更优而且红黑树实现比较简单所以在实际业务中一般都使用红黑树而不使用 AVL 树。 八、红黑树的代码实现
RBTree.h
#pragma once//节点颜色
enum Color {RED,BLACK
};templateclass K, class V
struct RBTreeNode {RBTreeNodeK, V* _left;RBTreeNodeK, V* _right;RBTreeNodeK, V* _parent;std::pairK, V _kv;Color _col; //节点颜色RBTreeNode(const std::pairK, V kv): _kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr), _col(RED) //默认给成红色{}
};templateclass K, class V
class RBTree {typedef RBTreeNodeK, V Node;
public:bool insert(const std::pairK, V kv) {//判断根节点是否为空if (_root nullptr) {_root new Node(kv);_root-_col BLACK; //根节点的颜色一定为黑return true;}//寻找插入位置Node* parent nullptr;Node* cur _root;while (cur) {if (kv.first cur-_kv.first) {parent cur;cur cur-_left;}else if (kv.first cur-_kv.first) {parent cur;cur cur-_right;}else {return false; //不允许重复节点}}//走到空开始插入注意这里还需要修改父节点的指向//新增节点的颜色为默认被初始化为红色所以这里不需要再显式赋值Node* newNode new Node(kv);if (kv.first parent-_kv.first)parent-_left newNode;elseparent-_right newNode;newNode-_parent parent; //修改父节点指向cur newNode;//如果父节点颜色为红色则需要进行调整且最多调整到根while (parent parent-_col RED) {Node* grandfater parent-_parent; //祖父节点if (grandfater nullptr)break;//如果父节点在祖父节点的左边if (parent grandfater-_left) {Node* uncle grandfater-_right; //叔叔节点//情况一叔叔存在且为红--父和叔叔变黑爷爷变红继续向上调整if (uncle uncle-_col RED) {parent-_col BLACK;uncle-_col BLACK;grandfater-_col RED;//继续向上调整cur grandfater;parent cur-_parent;}//情况二叔叔不存在或叔叔存在且为黑else {//如果cur在parent的左边则右单旋--注意走到这里p已经是g的左边了if (cur parent-_left) {rotateR(grandfater);//更新节点颜色parent-_col BLACK;cur-_col grandfater-_col RED;}else { //左右双旋//先以parent为轴进行左单旋rotateL(parent);//再以grandfather进行右单旋rotateR(grandfater);//更新节点颜色--此时cur为子树的根节点cur-_col BLACK;parent-_col grandfater-_col RED;}//最后需要跳出循环因为此时不会再影响上层break;}}//如果父节点在祖父节点的右边else {Node* uncle grandfater-_left; //叔叔节点//情况一叔叔存在且为红--父和叔叔变黑爷爷变红继续向上调整if (uncle uncle-_col RED) {parent-_col BLACK;uncle-_col BLACK;grandfater-_col RED;//继续向上调整cur grandfater;parent cur-_parent;}//情况二叔叔不存在或叔叔存在且为黑else {//如果cur在parent的右边则左单旋--注意走到这里p已经是g的右边了if (cur parent-_right) {rotateL(grandfater);//更新节点颜色parent-_col BLACK;cur-_col grandfater-_col RED;}else { //右左双旋//先以parent为轴进行右单旋rotateR(parent);//再以grandfather进行左单旋rotateL(grandfater);//更新节点颜色--此时cur为子树的根节点cur-_col BLACK;parent-_col grandfater-_col RED;}//最后需要跳出循环因为此时不会再影响上层break;}}}//在循环外面将_root的颜色重新置黑避免循环内部将根节点的颜色变红了_root-_col BLACK;return true;}//左单旋--右右void rotateL(Node* parent) {Node* subR parent-_right; //右子树Node* subRL subR-_left; //右子树的左子树//右子树的左子树链接到parent的右边parent-_right subRL;if (subRL) //subR可能为空(h0)subRL-_parent parent;//parent链接到右子树的左边subR-_left parent;Node* pparent parent-_parent; //保存parent的父节点parent-_parent subR;//让subR成为子树的根if (pparent) {if (pparent-_left parent) {pparent-_left subR;subR-_parent pparent;}else {pparent-_right subR;subR-_parent pparent;}}else { //如果parent的parent为空说明parent是整棵树根节点此时subR成为新的根节点subR-_parent nullptr;_root subR;}}//右单旋--左左void rotateR(Node* parent) {Node* subL parent-_left; //左子树Node* subLR subL-_right; //左子树的右子树//将左子树的右子树链接到根的左边parent-_left subLR;if (subLR) //应对h0的情况subLR-_parent parent;//将根链接到左子树的右边subL-_right parent;Node* pparent parent-_parent; //记录父节点的父节点parent-_parent subL;//让subL成为子树的根if (pparent) {if (pparent-_left parent) {pparent-_left subL;subL-_parent pparent;}else {pparent-_right subL;subL-_parent pparent;}}else { //如果parent的parent为空说明parent是整棵树的根节点此时subL成为新的根节点subL-_parent nullptr;_root subL;}}//中序遍历void InOrder() {return _inOrder(_root);}bool Check(Node* root, int blackCount, int baseCount) {//如果走到空说明这条路径结束了此时看count与baseCount是否相等if (root nullptr) {if (blackCount ! baseCount) {std::cout 此路径黑色节点数量有误节点key值 root-_kv.first std::endl;return false;}return true;}//检查是否出现连续红色节点if (root-_col RED) {if (root-_parent-_col RED) { //红色节点一定有父亲因为根节点为黑色std::cout 出现连续红色节点节点key值 root-_kv.first std::endl;}}if (root-_col BLACK)blackCount;return Check(root-_left, blackCount, baseCount) Check(root-_right, blackCount, baseCount);}//验证红黑树的性质bool IsBanlance() {if (_root nullptr)return true;//检查根节点if (_root-_col RED) {std::cout 根节点为红 std::endl;return false;}//以最左路径黑色节点数量为基准同其他路径的黑色节点数量相比较看是否相等int baseCount 0;Node* cur _root;while (cur) {if (cur-_col BLACK)baseCount;cur cur-_left;}//检查红黑树的其他性质return Check(_root, 0, baseCount);}private:void _inOrder(Node* root) {if (root nullptr)return;_inOrder(root-_left);std::cout root-_kv.first : root-_kv.second std::endl;_inOrder(root-_right);}private:Node* _root nullptr;
};test.cpp
#define _CRT_SECURE_NO_WARNINGS 1#include iostream
using namespace std;
#include RBTree.h//验证搜索树
void RBTree_test1() {int a[] { 16, 3, 7, 11, 9, 26, 18, 14, 15 };RBTreeint, int rb;for (auto e : a)rb.insert(std::make_pair(e, e));rb.InOrder();
}//验证红黑树的性质
void RBTree_test2() {//int a[] { 16, 3, 7, 11, 9, 26, 18, 14, 15 };int a[] { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };RBTreeint, int rb;for (auto e : a)rb.insert(std::make_pair(e, e));rb.InOrder();cout rb.IsBanlance() endl;
}//增大测试用例--采用N个随机数来验证
void RBTree_test3() {srand((size_t)time(0));const int N 10000;RBTreeint, int rb;for (int i 0; i N; i) {int x rand();rb.insert(make_pair(x, x));}cout rb.IsBanlance() endl;
}int main() {//RBTree_test1();//RBTree_test2();RBTree_test3();return 0;
}
