泰州市住房和城乡建设局网站,相册网站开发,微梦网站建设,网店代运营协议目录 前言
一、相关概念
二、性质介绍
红黑树平衡说明
三、红黑树模拟#xff08;kv结构#xff09;
1、红黑树节点
2、红黑树插入
2、特殊处理情况
声明#xff1a;
情况一#xff1a;cur为红#xff0c;p为红#xff0c;g为黑#xff0c;u存在#xff0c;且…目录 前言
一、相关概念
二、性质介绍
红黑树平衡说明
三、红黑树模拟kv结构
1、红黑树节点
2、红黑树插入
2、特殊处理情况
声明
情况一cur为红p为红g为黑u存在且uncle为红色
情况二cur为红p为红g为黑u不存在
情况三cur为红p为红g为黑u存在且为黑
总结
四、红黑树的验证
1、检查中序
2、检测红黑树性质
3、调试
五、红黑树的性能
1、测试函数
2、随机值测试
3、AVL红黑树对比测试
管理随机数据
管理有序数据
总结
结束语
附录1红黑树模拟代码
附录2红黑树测试代码 前言 本篇博客介绍红黑树结构,通过模拟红黑树的插入来深入理解红黑树的结构以及调整规则。
一、相关概念 红黑树也是一种二叉搜索树但在每个结点上增加一个存储位表示结点的颜色可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制红黑树确保没有一条路径会比其他路径长出两倍因而是接近平衡的特别注意不是和AVL一样的绝对平衡。 二、性质介绍
1. 每个结点不是红色就是黑色只有两种颜色的节点
2. 根节点是黑色的
3. 如果一个节点是红色的则它的两个孩子结点是黑色的无连续红色节点
4. 对于每个结点从该结点到其所有后代叶结点的简单路径上均 包含相同数目的黑色结点核心
5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点) 满足上面的性质红黑树就能保证其最长路径中节点个数不会超过最短路径节点个数的两倍。路径是指从根节点走到空节点的路程
红黑树平衡说明 我们可以通过分析极端情况不一定存在下的现象来得到上述结论即最短路径为全是黑色黑色节点最长路径为一黑一红节点排列此时我们可以发现最长路径是最短路径的两倍长度但最长路径与最短路径的极端情况不一定会出现极端情况都满足则说明所有情况都是满足其最长路径中节点个数不会超过最短路径节点个数的两倍。 三、红黑树模拟kv结构
1、红黑树节点 包含节点的父节点指针方便对于红黑树进行符合其性质的调整左孩子指针右孩子指针颜色属性节点数据。 注意对于新初始化的节点默认颜色为红色。本来这个树的每条路径黑色节点数是相同的假设你选定黑色节点的话无论黑色节点添加在哪里新增节点的路径上的黑色节点会加一红黑树要求每个路径黑色节点数相同树中所有路径都会受到影响大面积的影响处理起来非常困难。假设你选择的是一个红色节点如果添加在黑色节点下面则整棵树仍然满足性质不需要改变添加在红色节点下面才需要处理不能连续出现红色节点直解决当前路径下出现的问题大大化简了对红黑树的调整过程。
2、红黑树插入 由于红黑树仍然是一颗搜索二叉树所以按照二叉搜索的树规则插入新节点具体的插入规则之前文章有详解本篇文章主要讲述红黑树结构及其节点调整原理对于之前的只是就不在赘述。 假定插入节点前树满足红黑树性质插入节点完成后要保证其最长路径中节点个数不会超过最短路径节点个数的两倍我们就要使这棵树仍然保持有红黑树的性质要对红黑树性质遭到波坏的插入情况进行相应的调整。
2、特殊处理情况 插入位置的父亲节点是黑色节点父亲节点为黑色插入红色节点后红黑树的性质仍然存在不需要处理。 插入位置的父亲节点是红色节点有连续红色节点需要特殊处理维护整棵树以及每一颗子树的红黑树性质。 由于插入节点前树是满足红黑树性质的那么根节点不可能是红色的此时一定存在爷爷节点且原来没有连续红色节点所以爷爷节点一定为黑色。由于处理可能会一直向上更新到根节点所以采用循环处理先知道后面会解释。而对于这种问题的处理有着不同的情况与处理方法关键在uncle节点。
声明 在此之前我们先统一几个变量以及相关声明
1、cur为当前节点
2、父节点parent,简称p
3、祖父节点grandfather,简称g
4、叔叔节点uncle,简称u 声明我们无法列举出所有的树形结构以为树的结构具有多样性对于子树衍生情况非常多无法针对每一种树形结构定制处理办法。但是我们可以总结某一大类树形结构的解决办法在这种大类下不破坏红黑树性质而衍生出来的各种树形结构都可以使用这种方法处理。所以以下情况均是树形结构的大类在其基础上可以有树的衍生但必须是不破坏红黑树性质的合理衍生。
情况一cur为红p为红g为黑u存在且uncle为红色 我们不能将cur变黑这样的话就相当于是插入一个黑色节点其弊端在上文中已阐述。 解决办法将parentuncle变黑色grandfather变红色如下图 当前大类所代表的树当作一颗完整的树或是一颗子树g可能是根节点也可能不是。 如果g节点是根节点那么调整完成后将g改成黑色节点如果是子树g仍然有父节点那么调整完成后将g改成黑色节点。并且继续向上处理把grandfather节点当作cur节点继续向上更新。因为g原来是黑色的根据红黑树性质推得如果它有父节点那么他的父节点一定是红色的当我们最终将g节点变为红色那么又会出现连续得红色的节点与性质相冲突。需要我们继续把g节点当作cur节点来继续更新颜色解决这颗树出现的问题。 在极端情况下可能出现一直更新到根节点的情况这也是我们为什么我们把由采用循环条件处理的原因后面还会详细解释。 连续向上更新举例 补充
循环条件的解释 1、只有cur的p节点为红色时才需要特殊处理维护红黑树性质。在不断向上更新的时候如果cur的节点为黑色就相当于在当前节点下添加了一个黑色节点这正是我们不需要特殊处理的情况此时便退出循环。 2、当更新到根节点时候parent节点不存在也要退出循环。
特别注意 这种情况下不关心curparent的相对位置 无论parent的左孩子还是右孩子cur是左孩子还是右孩子处理方法都一样 情况二cur为红p为红g为黑u不存在 当u不存在时cur一定是新插入的节点 如果cur不是新插入的节点而是经过一次处理更新上来的红色节点根据情况一的更新方法判断cur为节点的子树一定有黑色节点这样的话无uncle的那条路径上的黑色节点数就会小于cur所在的路径上的黑色节点数不满足性质4所以可以确定cur就是新增节点。
在这种情况下个根据p节点与cur节点所处相对位置的不同又划分为四种子情况 (1)、p为g的左孩子cur为p的左孩子
右旋gg变红p变黑
(2)、p为g的左孩子cur为p的右孩子
左旋p右旋gcur变黑g变红
(3)、p为g的右孩子cur为p的左孩子
右旋p左旋gcur变黑g变红
(4)、p为g的右孩子cur为p的右孩子
左旋gg变红p变黑
对于左右旋的具体方法参考本人博客《AVL树模拟》有很详细的介绍
经过上述处理以上情况对应变化为下图 情况三cur为红p为红g为黑u存在且为黑 如果cur是新插节点那么在插入之前这棵树就已经违反了性质4如上图增加cur之前p节点所在的路径与u节点所在的路径黑色节点数并不相同所以这种猜想是错误的。我们可以断定这种情况不是插入节点得到的树的结构p节点所在路径的黑色节点等于u节点所在路径的黑色节点数那么可以知道cur的子树中的路径应该是有1个黑色节点即分别在ab的衍生中有且只有一个黑色节点推测为是其他结构下插入新节点后向上更新产生的一种情况简单来说就是cur节点在插入之前是黑色的被更新成了红色产生的新情况。如下是一种该情况产生的举例当然还有其他情况左图的up节点的子节点位置插入新节点 当curp所处的相对位置不同对应的处理方式又会不同这里分化为四种子情况 (1)、p为g的左孩子cur为p的左孩子
右旋gg变红p变黑
(2)、p为g的左孩子cur为p的右孩子
左旋p右旋gcur变黑g变红
(3)、p为g的右孩子cur为p的左孩子
右旋p左旋gcur变黑g变红
(4)、p为g的右孩子cur为p的右孩子
左旋gg变红p变黑 在这里我们模拟第一种和第二种子情况的变换第三种第四种变换和第一种第二种变换呈对称变换可以尝试自己画一下。
第一种子类型 第二种子类型 总结 结合情况二与情况三我们可以发现连续红色节点出现时pcur节点相对位置相同即子情况相同无论是大条件是uncle不存在还是uncle为黑色他们对应相同子情况的解决办法都是相同的对于节点的变色方法也相同于是我们将二者合二为一。即cur为红p为红g为黑u存在且为黑或者uncle不存在为一种情况。当curp所处的相对位置不同产生的不同的子情况方法也对应合并
(1)、p为g的左孩子cur为p的左孩子
右旋gg变红p变黑
(2)、p为g的左孩子cur为p的右孩子
左旋p右旋gcur变黑g变红 (3)、p为g的右孩子cur为p的左孩子
右旋p左旋gcur变黑g变红
(4)、p为g的右孩子cur为p的右孩子
左旋gg变红p变黑 注意: 在情况二和情况三合并的情况处理之后我们可以发现以子树的根节点开始的路径插入前后路径上的黑色节点保持不变而且处理之后这颗子树的根是黑色的并不破环整棵树的红黑树性质于是到这里我们就不需要继续向上更新了在这里就直接退出这颗树的特殊处理退出循环 四、红黑树的验证
1、检查中序 判断是否为有序排列红黑树本身就是一颗搜索二叉树所以必须要满足中序为有序排列。但仅此并不能说明它是一颗红黑树我们必须要验证其红黑树的性质 2、检测红黑树性质
1、检查根节点是不是黑色
2、检查是否存在连红遍历检查每个红色节点的parent节点如果存在parent为红那么就存在连续红色节点
3、检查每条路径的黑色节点数:
1求最左路径黑色节点数作为基准值
2递归记录当前节点下路径的黑色节点数
3走到空节点的时候判断与基准值比较,看黑色节点数是否相同 细节 1、如果根为红色提前返回错误 2、以根节点开始向下不断递归展开展开得到树中的每一条路径并且记录着每条路径的黑色节点数在展开的过程中会遍历到每一个节点所以对连续红色节点的检测也结合在递归过程中不需要额外遍历一次去检查连续红色节点的问题。 3、递归子函数中增加对黑色节点记录的参数这是从根节点到当前节点的黑色节点数如果节点为黑色则要对其1带到更下一层的递归。特别注意这里不能使用引用参数否则下一层黑色节点的更新会影响到上一层的计数那么上一层再向其他子树递归展开时计数就会错误。在这里我们希望的是下一层的黑色节点数增加不会影响到上一层。
3、调试 和AVL树调试相同插入一个值后就判断一次平衡找到最先不平衡的插入点。之后再设置对应断点逐步调试去查找问题。 五、红黑树的性能
1、测试函数 为了对红黑树的性能有直观体现我们又增加了一些函数来反映出他的效率如树的高度节点个数查找效率旋转调整次数等等。
树的高度 节点个数 查找函数 旋转次数 2、随机值测试 对于千万级数据插入效率与比较效率还不错
3、AVL红黑树对比测试 向AVL分别插入一千万个数据对比效率随机值有序值
管理随机数据 1、红黑树高度略高与AVL
2、AVL插入效率略高于红黑树但两者效率在一个层次都是log_2 N
3、查找红黑树肯定吃亏因为AVL对于平衡的要求更加严格
4、红黑树的优势主要在大大减少了旋转次数
管理有序数据 如果插入的是有序值AVL更好一点但实际中很少插入有序数列参考意义不大
总结 红黑树和AVL树都是高效的平衡二叉树增删改查的时间复杂度都是O(log_2 N)红黑树不追求绝对平衡其只需保证最长路径不超过最短路径的2倍相对而言降低了插入和旋转的次数所以在经常进行增删的结构中性能比AVL树更优而且红黑树实现比较简单所以实际运用中红黑树更多更多应用的是红黑树 结束语 本篇文章的内容就到此结束了希望通过这篇博客大家能有所收获有什么内容不明白的大家可以在评论去向我提问我会一一回答当然有什么错误或者有什么不足的地方希望大家可以包容并指出后续还会更新对于红黑树的具体应用红黑树迭代器模拟封装map与set在博客《红黑树大能量——mapset模拟》中希望大家可以持续关注向每一位读者送上真诚的小花。 附录1红黑树模拟代码
#pragma once
enum Color { RED, BLACK };template class K, class V
struct RBTreeNode {typedef RBTreeNodeK, V Node;Node* _parent;Node* _left;Node* _right;Color _col;pairK, V _kv;RBTreeNode(const pairK, V kv):_parent(nullptr),_left(nullptr),_right(nullptr),_col(RED),//新插入节点为红色初始化节点时直接给红色//如果给黑色会影响到所有路径_kv(kv){}
};templateclass K, class V
class RBTree {typedef RBTreeNodeK, V Node;
public:bool Insert(const 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-_right;}else if (kv.first cur-_kv.first){parent cur;cur cur-_left;}elsereturn false;}//插入新节点并且与parent进行链接cur new Node(kv);if (kv.first parent-_kv.first){parent-_left cur;}else{parent-_right cur;}cur-_parent parent;//父亲节点为黑色插入成功不需要处理(不进入循环)//if (parent-_col BLACK)// return true;//父亲节点为红色有连续红色需要特殊处理此时一定存在爷爷节点Node* grandfather nullptr; Node* uncle nullptr;while (parent parent-_col RED){//父亲节点为红色有连续红色需要特殊处理此时一定存在爷爷节点grandfather parent-_parent;//一、parent在grandfather的左边说明uncle在右边if (parent grandfather-_left){uncle grandfather-_right;//1、uncle存在且uncle为红色//parentuncle变黑色grandfather变红色并且继续向上处理//********* 不关心uncle的方向 *******if (uncle uncle-_col RED){parent-_col uncle-_col BLACK;grandfather-_col RED;//需要继续向上处理直到退出循环cur grandfather;parent cur-_parent;}//2、uncle不存在或者uncle存在且为黑色, 利用旋转的方式处理//********** uncle左右位置不同处理方式不同else{//(1)cur是parent的左边右旋grandfather// 变色p变黑g变红// g// p u// cif (cur parent-_left){RotateR(grandfather);grandfather-_col RED;parent-_col BLACK;}//(2)cur是parent的有右边左旋parent右旋grandfather//变色 c变黑g变红// g// p u// celse{RotateL(parent);RotateR(grandfather);grandfather-_col RED;cur-_col BLACK;}//旋转后以grandfather为根的子树每条路径的黑色节点数与没插入之前相同不影响其他路径不继续向上处理退出循环//处理完根是黑的直接退出break;}}//二、parent在grandfather的右边说明uncle在左边else{uncle grandfather-_left;//1、uncle存在且uncle为红色//parentuncle变黑色grandfather变红色并且继续向上处理//********* 不关心uncle的方向 *******if (uncle uncle-_col RED){parent-_col uncle-_col BLACK;grandfather-_col RED;//需要继续向上处理直到退出循环cur grandfather;parent cur-_parent;}//2、uncle不存在或者uncle存在且为黑色 利用旋转的方式处理//********** uncle左右位置不同处理方式不同else{//(1)cur是parent的右边左旋grandfather// 变色p变黑g变红// g// u p// cif (cur parent-_right){RotateL(grandfather);grandfather-_col RED;parent-_col BLACK;}//(2)cur是parent的左边右旋parent左旋grandfather//变色 c变黑g变红// g// u p// celse{RotateR(parent);RotateL(grandfather);grandfather-_col RED;cur-_col BLACK;}//旋转后以grandfather为根的子树每条路径的黑色节点数与没插入之前相同不影响其他路径不继续向上处理退出循环//处理完根是黑的直接退出break;}}}//最后让根节点的颜色一定为黑色不在循环里面单独判断是否为根节点_root-_col BLACK;return true;}void RotateL(Node * parent){Node* subR parent-_right;Node* subRL subR-_left;//处理parent与subRL新关系的链接parent-_right subRL;//subRL不为空其父节点指向parentif (subRL)subRL-_parent parent;//处理parent与subR新关系的链接subR-_left parent;Node* ppnode parent-_parent;//保存旧parent的父亲节点与subR节点链接parent-_parent subR;//处理parent的父亲节点与subR节点链接//parent可能是根节点if (_root parent){_root subR;subR-_parent nullptr;}else{if (parent ppnode-_left)ppnode-_left subR;elseppnode-_right subR;subR-_parent ppnode;}Rotatesize;}//右旋void RotateR(Node * parent){Node* subL parent-_left;Node* subLR subL-_right;parent-_left subLR;if (subLR)subLR-_parent parent;subL-_right parent;Node* ppnode parent-_parent;parent-_parent subL;if (parent _root){_root subL;subL-_parent nullptr;}else{if (ppnode-_left parent){ppnode-_left subL;}else{ppnode-_right subL;}subL-_parent ppnode;}Rotatesize;}//中序遍历void Inorder(){_inorder(_root);cout end endl;}void _inorder(Node* root){if (root nullptr)return;_inorder(root-_left);cout root-_kv.first : root-_kv.second endl;_inorder(root-_right);}//红黑树规则测试//1、检查根节点是不是黑色//2、检查是否存在连红遍历检查每个红色节点的parent节点如果存在parent为红那么就存在连红//3、检查每条路径的黑色节点数//1求最左路径黑色节点数作为基准值//2递归记录当前节点路径黑色节点数//3走到空节点的时候判断与基准值比较bool isBalance(){if (_root_root-_col RED)return false;Node* cur _root;int refblacknum 0;while (cur){if (cur-_col BLACK){refblacknum;}cur cur-_left;}return check(_root, refblacknum, 0);}bool check(Node* root,int refblacknum,int blacknum) //采用按值传参下一层不影响上一层{if (root nullptr){if (blacknum refblacknum){return true;}cout 黑色节点数不相等 endl;return false;}if (root-_col RED root-_parent-_col RED){cout root-_kv.first有连续的红色节点 endl;return false;}if (root-_col BLACK)blacknum;return check(root-_left, refblacknum,blacknum) check(root-_right, refblacknum, blacknum);}//求当前树的高度int Height(){return height(_root);}//求高度子函数int height(Node* root){if (root nullptr)return 0;int lefth height(root-_left);int righth height(root-_right);return lefth righth ? lefth 1 : righth 1;}//树的节点个数size_t Size(){return _Size(_root);}size_t _Size(Node* root){if (root NULL)return 0;return _Size(root-_left) _Size(root-_right) 1;}//查找节点Node* Find(const K key){Node* cur _root;while (cur){if (cur-_kv.first key){cur cur-_right;}else if (cur-_kv.first key){cur cur-_left;}else{return cur;}}return NULL;}int GetRotatesize(){return Rotatesize;}private:Node* _root nullptr;int Rotatesize 0;};
附录2红黑树测试代码
#includeiostream
using namespace std;#includevector
#includeRBTree.h
#includeAVLtree.hvoid test1()
{//int a[] { 16, 3, 7, 11, 9, 26, 18, 14, 15 };int a[] { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14,16, 3, 7, 11, 9, 26, 18, 14, 15 };RBTreeint, int t;for (auto e : a){if (e 14){int x 0;}t.Insert(make_pair(e, e));//cout e- t.isBalance() endl;}t.Inorder();cout t.isBalance() endl;}void test2()
{const int N 10000000;vectorint v;v.reserve(N);srand((size_t)time(0));for (size_t i 0; i N; i){v.push_back(rand() i);}size_t begin2 clock();RBTreeint, int t;for (auto e : v){t.Insert(make_pair(e, e));}size_t end2 clock();cout Insert: end2 - begin2 endl;cout t.isBalance() endl;cout Height: t.Height() endl;cout Size: t.Size() endl;size_t begin1 clock();// 确定在的值for (auto e : v){t.Find(e);}// 随机值for (size_t i 0; i N; i){t.Find((rand() i));}size_t end1 clock();cout Find: end1 - begin1 endl;
}void test3()
{//调试出来的错误为退出循环写错了位置导致uncle为红色结束后直接退出了const int N 20;vectorint v;v.reserve(N);//srand(time(0));for (size_t i 0; i N; i){v.push_back(rand()%100);}RBTreeint, int t;for (auto e : v){if (e 64){int x 0;}t.Insert(make_pair(e, e));cout e- t.isBalance() endl;}cout t.isBalance() endl;
}//1、红黑树高度略高与AVL
//2、AVL插入效率略高于红黑树但两者效率再一个层次
//3、如果插入的是有序值AVL更好一点
//4、红黑树的优势主要在大大减少了旋转次数
//5、查找红黑树肯定吃亏
//*************************更多应用是红黑树
void RBTree_AVL_Compare()
{const int N 10000000;vectorint v;v.reserve(N);srand(time(0));for (size_t i 0; i N; i){//v.push_back(rand() i);//随机值v.push_back(i); //有序值}RBTreeint, int t1;AVLTreeint, int t2;size_t begin1 clock();for (auto e : v){t1.Insert(make_pair(e, e));}size_t end1 clock();size_t begin2 clock();for (auto e : v){t2.Insert(make_pair(e, e));}size_t end2 clock();size_t begin3 clock();// 确定在的值for (auto e : v){t1.Find(e);}// 随机值/*for (size_t i 0; i N; i){t1.Find((rand() i));}*/size_t end3 clock();size_t begin4 clock();// 确定在的值for (auto e : v){t2.Find(e);}// 随机值/*for (size_t i 0; i N; i){t2.Find((rand() i));}*/size_t end4 clock();cout RBTree RoateSize: t1.GetRotatesize() endl;cout AVLTree RoateSize: t2.GetRotatesize() endl endl;cout RBTree Insert: end1 - begin1 endl;cout AVLTree Insert: end2 - begin2 endl endl;cout RBTree IsBalance: t1.isBalance() endl;cout AVLTree IsBalance: t2.isBalance() endl endl;cout RBTree Height: t1.Height() endl;cout AVLTree Height: t2.Height() endl endl;cout AVLTree Size: t2.Size() endl ;cout RBTree Size: t1.Size() endl endl;cout RBTree Find: end3 - begin3 endl;cout AVLTree Find: end4 - begin4 endlendl;}
int main()
{//test1();//test2();//test3();//调试出来了很隐蔽的错误RBTree_AVL_Compare();return 0;
}
