做优惠券网站,小视频广告,网站及其建设的心得,湖北中英双语网站建设目录
1. 初识红黑树
1.1 红黑树的概念 1.2 红⿊树的规则
1.3 红黑树如何确保最长路径不超过最短路径的2倍
1.4 红黑树的效率:O(logN)
2. 红黑树的实现
2.1 红黑树的基础结构框架
2.2 红黑树的插⼊
2.2.1 情况1#xff1a;变色
2.2.2 情况2#xff1a;单旋变色
2.2…目录
1. 初识红黑树
1.1 红黑树的概念 1.2 红⿊树的规则
1.3 红黑树如何确保最长路径不超过最短路径的2倍
1.4 红黑树的效率:O(logN)
2. 红黑树的实现
2.1 红黑树的基础结构框架
2.2 红黑树的插⼊
2.2.1 情况1变色
2.2.2 情况2单旋变色
2.2.3 情况3双旋变色
2.3 验证一棵树是否为红黑树
2.4 代码汇总 1. 初识红黑树 1.1 红黑树的概念 红⿊树是⼀棵⼆叉搜索树他的每个结点增加⼀个存储位来表⽰结点的颜⾊可以是红⾊或者⿊⾊。通过对任何⼀条从根到叶⼦的路径上各个结点的颜⾊进⾏约束红⿊树确保没有⼀条路径会⽐其他路径⻓出2倍因⽽是接近平衡的 1.2 红⿊树的规则 1. 每个结点不是红⾊就是⿊⾊ 2. 根结点是⿊⾊的 3. 如果⼀个结点是红⾊的则它的两个孩⼦结点必须是⿊⾊的也就是说任意⼀条路径不会有连续的红⾊结点 4. 对于任意⼀个结点从该结点到其所有NULL结点的简单路径上均包含相同数量的⿊⾊结点 1.3 红黑树如何确保最长路径不超过最短路径的2倍 1. 由规则4可知从根到NULL结点的每条路径都有相同数量的⿊⾊结点所以极端场景下最短路径就就是全是⿊⾊结点的路径假设最短路径⻓度为bh黑色节点的数量 2. 由规则2和规则3可知任意⼀条路径不会有连续的红⾊结点所以极端场景下最⻓的路径就是⼀⿊⼀红间隔组成那么最⻓路径的⻓度为2*bh 3. 综合红⿊树的4点规则⽽⾔理论上的全⿊最短路径和⼀⿊⼀红的最⻓路径并不是在每棵红⿊树都存在的。假设任意⼀条从根到NULL结点路径的⻓度为x那么bh h 2*bh 1.4 红黑树的效率:O(logN) 红⿊树的表达相对AVL树要抽象⼀些AVL树通过⾼度差直观的控制了平衡。红⿊树通过4条规则的颜 ⾊约束间接的实现了近似平衡他们效率都是同⼀档次但是相对⽽⾔插⼊相同数量的结点红⿊树的旋转次数是更少的因为他对平衡的控制没那么严格 2. 红黑树的实现 2.1 红黑树的基础结构框架
#pragma once
//定义一个枚举
enum Colour
{//枚举里面定义颜色RED,BLACK
};//默认按key/value结构实现
templateclass K, class V
struct RBTreeNode
{//这⾥更新控制平衡也要加⼊parent指针pairK, V _kv;//也要实现成三叉链RBTreeNodeK, V* _left;RBTreeNodeK, V* _right;RBTreeNodeK, V* _parent;Colour _col;RBTreeNode(const pairK, V kv) :_kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr){}
};templateclass K, class V
class RBTree
{typedef RBTreeNodeK, V Node;
public:
private:Node* _root nullptr;
}; 2.2 红黑树的插⼊ 1. 插⼊⼀个值按⼆叉搜索树规则进⾏插⼊插⼊后我们只需要观察是否符合红⿊树的4条规则 2. 如果是空树插⼊新增结点是⿊⾊结点。如果是⾮空树插⼊新增结点必须是红⾊结点因为⾮空树插⼊新增⿊⾊结点就破坏了规则4规则4是很难维护的 3. ⾮空树插⼊后新增结点必须红⾊结点如果⽗亲结点是⿊⾊的则没有违反任何规则插⼊结束 4. ⾮空树插⼊后新增结点必须红⾊结点如果⽗亲结点是红⾊的则违反规则3。进⼀步分析c是红⾊p为红g必为⿊这三个颜⾊都固定了关键的变化看u的情况需要根据u分为以下⼏种 情况分别处理 说明下图中假设我们把新增结点标识为c(cur)c的⽗亲标识为p(parent)p的⽗亲标识为 g(grandfather)p的兄弟标识为uuncle) 2.2.1 情况1变色 新增结点标识为c(cur)c的⽗亲标识为p(parent)p的⽗亲标识为 g(grandfather)p的兄弟标识为uuncle) c为红p为红g为⿊u存在且为红则将p和u变⿊g变红再在把g当做新的c继续往上更新 分析因为p和u都是红⾊g是⿊⾊把p和u变⿊左边⼦树路径各增加⼀个⿊⾊结点g再变红相当于保持g所在⼦树的⿊⾊结点的数量不变同时解决了c和p连续红⾊结点的问题需要继续往上更新因为g是红⾊ 如果g的⽗亲还是红⾊那么就还需要继续处理如果g的⽗亲是⿊⾊则处理结束了如果g就是整棵树的根再把g变回⿊⾊ 情况1只变⾊不旋转。所以⽆论c是p的左还是右p是g的左还是右都是上⾯的变⾊处理⽅式 2.2.2 情况2单旋变色 c为红p为红g为⿊u不存在或者u存在且为⿊u不存在则c⼀定是新增结点 u存在且为⿊则c⼀定不是新增c之前是⿊⾊的是在c的⼦树中插⼊符合情况1变⾊将c从⿊⾊变成红⾊更新上来的 分析p必须变⿊才能解决连续红⾊结点的问题u不存在或者是⿊⾊的这⾥单纯的变⾊⽆法解决问题需要旋转变⾊ 如果p是g的左c是p的左那么以g为旋转点进⾏右单旋再把p变⿊g变红即可。p变成课这颗树新的根这样⼦树⿊⾊结点的数量不变没有连续的红⾊结点了且不需要往上更新因为p的⽗亲是⿊⾊还是红⾊或者空都不违反规则 如果p是g的右c是p的右那么以g为旋转点进⾏左单旋再把p变⿊g变红即可。p变成课这颗树新的根这样⼦树⿊⾊结点的数量不变没有连续的红⾊结点了且不需要往上更新因为p的⽗亲是⿊⾊还是红⾊或者空都不违反规则 2.2.3 情况3双旋变色 c为红p为红g为⿊u不存在或者u存在且为⿊u不存在则c⼀定是新增结点 u存在且为⿊则c⼀定不是新增c之前是⿊⾊的是在c的⼦树中插⼊符合情况1变⾊将c从⿊⾊变成红⾊更新上来的 分析p必须变⿊才能解决连续红⾊结点的问题u不存在或者是⿊⾊的这⾥单纯的变⾊⽆法解决问题需要旋转变⾊ 如果p是g的左c是p的右那么先以p为旋转点进⾏左单旋再以g为旋转点进⾏右单旋再把c变⿊g变红即可。c变成课这颗树新的根这样⼦树⿊⾊结点的数量不变没有连续的红⾊结点了且不需要往上更新因为c的⽗亲是⿊⾊还是红⾊或者空都不违反规则 如果p是g的右c是p的左那么先以p为旋转点进⾏右单旋再以g为旋转点进⾏左单旋再把c变⿊g变红即可。c变成课这颗树新的根这样⼦树⿊⾊结点的数量不变没有连续的红⾊结点了且不需要往上更新因为c的⽗亲是⿊⾊还是红⾊或者空都不违反规则 2.3 验证一棵树是否为红黑树 规则1枚举颜⾊类型天然实现保证了颜⾊不是⿊⾊就是红⾊ 规则2直接检查根即可 规则3前序遍历检查遇到红⾊结点查孩⼦不太⽅便因为孩⼦有两个且不⼀定存在反过来检 查⽗亲的颜⾊就⽅便多了 规则4前序遍历遍历过程中⽤形参记录跟到当前结点的blackNum(⿊⾊结点数量)前序遍历遇到 ⿊⾊结点就blackNum⾛到空就计算出了⼀条路径的⿊⾊结点数量。再任意⼀条路径⿊⾊结点数量作为参考值依次⽐较即可 bool Check(Node* root, int blacknum, const int retnum)
{if (root nullptr){if (blacknum ! retnum){cout 有路径的黑色节点个数与其他路径不相同 endl;return false;}return true;}if (root-_col RED root-_parent-_col RED){cout 存在连续的红色节点 endl;return false;}if (root-_col BLACK){blacknum;}return Check(root-_left, blacknum, retnum) Check(root-_right, blacknum, retnum);
}
bool IsBalance()
{if (_root nullptr){return true;}if (_root-_col BLACK){return false;}int retnum 0;Node* cur _root;while (cur){if (cur-_col BLACK){retnum;}cur cur-_left;}return Check(_root, 0, retnum);
} 2.4 代码汇总
#pragma once
#pragma once
//定义一个枚举
enum Colour
{//枚举里面定义颜色RED,BLACK
};//默认按key/value结构实现
templateclass K, class V
struct RBTreeNode
{//这⾥更新控制平衡也要加⼊parent指针pairK, V _kv;//也要实现成三叉链RBTreeNodeK, V* _left;RBTreeNodeK, V* _right;RBTreeNodeK, V* _parent;Colour _col;//颜色RBTreeNode(const pairK, V kv) :_kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr){}
};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 (cur-_kv.first kv.first){parent cur;cur cur-_right;}else if (cur-_kv.first kv.first){parent cur;cur cur-_left;}else{return false;}}//如果非空的树插入一个节点那么插入红色cur new Node(kv);cur-_col RED;if (parent-_kv.first kv.first){parent-_right cur;}else{parent-_left cur;}// 链接父亲cur-_parent parent;// 父亲存在并且也是红色当出现连续的红色节点时while (parent parent-_col RED){//找到爷爷节点Node* grandfather parent-_parent;//再根据叔叔节点来判断父亲节点的情况if (parent grandfather-_left){// g//p u// //说明u在g的右边Node* uncle grandfather-_right;//如果u存在并且u的颜色为红色if (uncle uncle-_col RED){//将u和p的颜色改为黑色g的颜色改为红色uncle-_col parent-_col BLACK;grandfather-_col RED;// 继续往上处理cur grandfather;parent cur-_parent;//p寻找g的p节点}else{if (cur parent-_left){// g// p u// cRotateR(grandfather);parent-_col BLACK;grandfather-_col RED;}else{// g// p u// cRotateL(parent);RotateR(grandfather);cur-_col BLACK;grandfather-_col RED;}break;}}else{// g// u pNode* uncle grandfather-_left;// 叔叔存在且为红-》变色即可if (uncle uncle-_col RED){parent-_col uncle-_col BLACK;grandfather-_col RED;// 继续往上处理cur grandfather;parent cur-_parent;}else // 叔叔不存在或者存在且为黑{// 情况二叔叔不存在或者存在且为黑// 旋转变色// g// u p// cif (cur parent-_right){RotateL(grandfather);parent-_col BLACK;grandfather-_col RED;}else{RotateR(parent);RotateL(grandfather);cur-_col BLACK;grandfather-_col RED;}break;}}}//保证根节点一定是黑色的_root-_col BLACK;return true;}//右单旋void RotateR(Node* parent){Node* subL parent-_left;Node* subLR subL-_right;parent-_left subLR;if (subLR)subLR-_parent parent;Node* pParent parent-_parent;subL-_right parent;parent-_parent subL;if (parent _root){_root subL;subL-_parent nullptr;}else{if (pParent-_left parent){pParent-_left subL;}else{pParent-_right subL;}subL-_parent pParent;}}//左单旋void RotateL(Node* parent){Node* subR parent-_right;Node* subRL subR-_left;parent-_right subRL;if (subRL)subRL-_parent parent;Node* parentParent parent-_parent;subR-_left parent;parent-_parent subR;if (parentParent nullptr){_root subR;subR-_parent nullptr;}else{if (parent parentParent-_left){parentParent-_left subR;}else{parentParent-_right subR;}subR-_parent parentParent;}}private:Node* _root nullptr;
}; 完结撒花~
