河北pc端网站建设,网站运营外包协议,手表东莞网站建设技术支持,十大暴利行业加盟目录
基本概念
插入结点的颜色
判断性质是否破坏
调整方式 u为g的右孩子
u存在且为红
u存在且为黑
u不存在
结论
红黑树结点定义
代码实现 基本概念
1、红黑树是一种特殊的二叉搜索树#xff0c;每个结点会增加一个存储位表示结点的颜色#xff08;红或黑#x…目录
基本概念
插入结点的颜色
判断性质是否破坏
调整方式 u为g的右孩子
u存在且为红
u存在且为黑
u不存在
结论
红黑树结点定义
代码实现 基本概念
1、红黑树是一种特殊的二叉搜索树每个结点会增加一个存储位表示结点的颜色红或黑
2、红黑树通过对所有从根到叶子的路径上的各个结点的着色方式的限制确保红黑树中没有一条路径会比其它路径长出两倍从而使二叉搜索树接近平衡
3、AVL树是一个严格平衡平衡因子二叉树能做到的最好的平衡而红黑树是一个近似平衡插入100万个数据AVL树会进行大量的旋转形成的树可能是30层但是红黑树的旋转会少一些形成的树可能是60层但是对于CPU而言其实二者差别也不大
4、红黑树有五个性质紫色是重点
每个结点不是红色就是黑色根结点是黑色的如果一个结点是红色则它的两个孩子结点都是黑色一个黑结点的孩子可以是红也可以是黑的不可以不存在连续的红红、可以存在连续黑红、红黑和黑黑的结点对于每个结点该结点到其所有后代叶子结点的简单路径上均包含相同数目的黑色结点一个结点向下的每条路径中的黑色结点相同空结点也是黑色结点最难维护的规则每个叶子结点都是黑色的红黑树中所指的叶子结点是空结点 5、满足以上五条性质就能保证红黑树的最长路径 最短路径 * 2
最短路径极端情况全黑由性质4可得其它路径中也有相同数目的黑色结点以及红色结点但是全黑的路径中没有红色结点最长路径极端情况一黑一红不算空结点一个红黑树肯定有最长或最短路径只不过不一定有以上的理想情况下的最短和最长路径正常情况下最长路径小于最短路径的2倍极端情况下最长路径可能还会等于最短路径的2倍没有极端情况就矮子里挑将军了 插入结点的颜色 问题插入结点时还可以依据二叉搜索树的插入规则吗插入结点应该都是什么颜色 解释可以且新插入的结点应该都是红色因为插入结点的颜色是红色那么你只是可能违反性质3如果一个结点是红色则它的两个孩子结点都是黑色 但是如果插入结点的颜色是黑色则一定违法性质4对于每个结点该结点到其所有后代叶子结点的简单路径上均包含相同数目的黑色结点 判断性质是否破坏 规定cur表示新插入结点p表示父结点parent、g表示爷爷结点grandfather、u表示叔叔结点uncle 问题如何确认在插入新结点后红黑树的性质是否被破坏 解释新结点的颜色为红色如果新结点的父结点颜色为红色则违法性质3需要进行调整 补充p一定为红g一定为黑因为新插入结点的颜色是红色插入该结点导致需要调整只可能是因为该结点的插入导致性质3遭到了破坏那么p结点一定为红而g也肯定为黑因为在新插入结点前整颗红黑树应该是没有错误的跟AVL树旋转是一个道理 调整方式 问题发现红黑树性质被破坏后如何进行调整后面还有更准确的划分 ①由上述内容可知在性质被破坏时cur一定为红、p一定为红、g一定为黑那么关键点就在于p的兄弟结点u对u的关注点应该在于它的“位置 存在情况” ②u的位置p为g的左孩子u就是g的右孩子p为g的右孩子u就是g的左孩子 ③u的存在情况u存在且为黑色u存在且为红色、u不存在 u为g的右孩子 u存在且为红 解决办法将p和u变为黑g变为红p和u替代了g保证路径上黑色结点数量不变 遗留问题 如果g是根结点那么在g变红后为了满足性质2仅需要将g重新变为黑色即可如果g不是根结点那么在g变红且g的父结点的颜色是黑色时不需要继续向上调整如果g不是根结点那么在g变红且g的父结点的颜色是红色时就需要继续向上调整 注意事项 1、不能在发现新插入结点导致违法性质3后将cur再变为黑因为那样还不如规定插入结点的颜色为黑色但是那样又一定会违法性质4 2、p和u改变后不能让g仍然为黑因为如果g不是根结点那么也会违法性质4 关于cur无论cur是p的左孩子还是右孩子当u存在且为红时调整时只需要调色即可 u存在且为黑 补充下图演示的是u存在且为红在调整后向上调节时遇到的u存在且为黑的情况用一个例子将u存在且为红 向上调整 u存在且为黑的情况都总结了 解决办法先旋转以g为旋转点进行LL右单旋后变色p变为黑g变为红 关于cur ①上面的cur是p左孩子则以g为旋转点进行LL右单旋p变黑g变红 ②若cur是p的右孩子先以p为旋转点进行左单旋后以g为旋转点进行右单旋cur变黑g变红 颜色改变没有先后顺序只要发生改变即可先旋转后变色只是为了理解变色原因 u不存在 解决办法先变色p变为黑g变为红后旋转以g为旋转点进行LL右单旋 关于cur ①上面的cur是p左孩子则以g为旋转点进行LL右单旋p变黑g变红 ②若cur是p的右孩子先以p为旋转点进行左单旋后以g为旋转点进行右单旋cur变黑g变红 颜色改变没有先后顺序只要发生改变即可先旋转后变色只是为了理解变色原因 u为g的右孩子的情况不再分析通过最终代码自己画图感受主要区别在于旋转方式的不同 结论 每一次的调整都可能导致另一次红黑树性质的被破坏cur和parent均为红色是由“新增”或“向上调整”两种原因导致的因此无论是这两种的哪一种只有当cur和parent均不为红时才不需要继续调整循环红黑树是否调整取决于cur和parent是否均为红怎么调整取决于叔叔u的情况 cur是p的哪个孩子 红黑树结点定义
// 结点颜色
enum Color
{ RED, BLACK
};// 红黑树节点的定义
templateclass ValueType
struct RBTreeNode
{RBTreeNode(const ValueType data ValueType()Color color RED): _pLeft(nullptr), _pRight(nullptr), _pParent(nullptr), _data(data), _color(color){}RBTreeNodeValueType* _pLeft; // 节点的左孩子RBTreeNodeValueType* _pRight; // 节点的右孩子RBTreeNodeValueType* _pParent; // 节点的双亲ValueType _data; // 节点的值域 Color _color; // 节点的颜色
};
演示的内容与最终代码中变量的名字存在区别
代码实现
#pragma once#include iostream
#includevectorusing namespace std;enum Colour
{RED,BLACK
};templateclass K, class V
struct RBTreeNode
{RBTreeNodeK, V* _left;RBTreeNodeK, V* _right;RBTreeNodeK, V* _parent;pairK, V _kv;Colour _col;RBTreeNode(const pairK, V kv):_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _col(RED){}
};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;// 当parent指向的结点不为空且parent指向的结点的颜色不为黑色就继续向上调整因为cur和parent均为红可能是由新增和向上调整导致的因此无论是这两种情况的哪一种// 只有当cur和parent均不为红时才结束循环while (parent parent-_col RED){Node* grandfather parent-_parent;//通过父亲找到爷爷父亲的父亲信息是爷爷//红黑树的关键点在于判断叔叔的情况if (parent grandfather-_left)//如果父亲是爷爷的左孩子那么叔叔就只能是爷爷的右孩子//这里if中的叔叔一直都是爷爷的右孩子不过还会存在为红、为黑、不存在的三种情况{Node* uncle grandfather-_right;// 如果叔叔存在且叔叔的颜色是红色则直接将叔叔和父亲的颜色都变为黑色将爷爷的颜色变为红色if (uncle uncle-_col RED){parent-_col uncle-_col BLACK;grandfather-_col RED;// 防止修改颜色导致上方出现新的两个连续的红色结点需要移动指针继续向上处理cur grandfather;//cur指向爷爷结点parent cur-_parent;//parent指向的是cur的父结点cur向上走parent也要向上走}else // 叔叔不存在或者存在且为黑{if (cur parent-_left)//如果cur是父亲的左孩子进行LL右单旋转后将父亲的颜色变为黑将爷爷的颜色变为红{// g // p u// c RotateR(grandfather);parent-_col BLACK;grandfather-_col RED;}else{// g // p u// c RotateL(parent);RotateR(grandfather);cur-_col BLACK;grandfather-_col RED;}break;}}else//如果父亲结点是爷爷结点的右孩子那么叔叔结点就是爷爷结点的左孩子{Node* 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{// g// u p// cRotateR(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;subL-_right parent;Node* ppNode parent-_parent;parent-_parent subL;if (parent _root){_root subL;_root-_parent nullptr;}else{if (ppNode-_left parent){ppNode-_left subL;}else{ppNode-_right subL;}subL-_parent ppNode;}}void RotateL(Node* parent){Node* subR parent-_right;Node* subRL subR-_left;parent-_right subRL;if (subRL)subRL-_parent parent;subR-_left parent;Node* ppNode parent-_parent;parent-_parent subR;if (parent _root){_root subR;_root-_parent nullptr;}else{if (ppNode-_right parent){ppNode-_right subR;}else{ppNode-_left subR;}subR-_parent ppNode;}}//对用户暴露的中序遍历红黑树接口void InOrder(){_InOrder(_root);cout endl;}//判断红黑树是否平衡bool IsBalance(){//首先根结点颜色得为黑if (_root-_col RED){return false;}int refNum 0;Node* cur _root;while (cur){if (cur-_col BLACK){refNum;}cur cur-_left;}return Check(_root, 0, refNum);}private:bool Check(Node* root, int blackNum, const int refNum){if (root nullptr){//cout blackNum endl;if (refNum ! blackNum){cout 存在黑色节点的数量不相等的路径 endl;return false;}return true;}if (root-_col RED root-_parent-_col RED){cout root-_kv.first 存在连续的红色节点 endl;return false;}if (root-_col BLACK){blackNum;}return Check(root-_left, blackNum, refNum) Check(root-_right, blackNum, refNum);}void _InOrder(Node* root){if (root nullptr){return;}_InOrder(root-_left);cout root-_kv.first : root-_kv.second endl;_InOrder(root-_right);}private:Node* _root nullptr;
};//测试红黑树能否正常使用
void TestRBTree1()
{int a[] { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14,8, 3, 1, 10, 6, 4, 7, 14, 13 };RBTreeint, int t1;for (auto e : a){if (e 10){int i 0;}// 1、先看是插入谁导致出现的问题// 2、打条件断点画出插入前的树// 3、单步跟踪对比图一一分析细节原因t1.Insert({e,e});std::cout Insert: e - t1.IsBalance() std::endl;}t1.InOrder();std::cout t1.IsBalance() std::endl;
}//测试红黑树对百万数据处理所需时间
void TestRBTree2()
{const int N 1000000;vectorint v;v.reserve(N);srand(time(0));for (size_t i 0; i N; i){v.push_back(rand() i);//cout v.back() endl;}size_t begin2 clock();RBTreeint, int t;for (auto e : v){t.Insert(make_pair(e, e));//cout Insert: e - t.IsBalance() endl;}size_t end2 clock();std::cout t.IsBalance() std::endl;
} ~over~
