四川省建设厅职业注册中心网站,昆明网络科技公司有哪些,江门网红打卡景点蓬江区,word 调用wordpress文章目录红黑树的概念红黑树的性质特征红黑树结点的定义红黑树的插入操作情况1情况2情况3特殊情况代码实现红黑树的验证红黑树的删除红黑树和AVL树的比较红黑树的应用红黑树的概念
红黑树#xff0c;是一种二叉搜索树#xff0c;但是每一个结点都增加一个存储位表示结点的颜…
文章目录红黑树的概念红黑树的性质特征红黑树结点的定义红黑树的插入操作情况1情况2情况3特殊情况代码实现红黑树的验证红黑树的删除红黑树和AVL树的比较红黑树的应用红黑树的概念
红黑树是一种二叉搜索树但是每一个结点都增加一个存储位表示结点的颜色可以是red或者black。通过任何一条从根到叶子结点的路径上各个结点着色方式的限制红黑树确保没有一条路径会比其他路径长出两倍因而是接近平衡的。
红黑树的性质特征
每个结点不是黑色就是红色根节点_root是黑色如果一个结点是红色的则它的两个孩子结点是黑色的即没有连续的红色结点注意可以有连续的黑色结点对于每个结点从该结点到其所有后代叶子的简单路径上均包含相同数目的黑色结点即每条路径上都包含相同数量黑色结点空节点即NIL结点可以认为是黑色的注意计算有几条路径时是要看是否走到空节点即图上的NIL空节点故如图的红黑树有5条路径 思考为什么满足上面的性质红黑树就能保证其最长路径中结点个数不会超过最短路径结点个数的两倍 红黑树是近似平衡不能保证每次都完全平衡。由性质3可知红色结点不能连续由性质4可得每条路径均包含相同数量的黑色结点。
若我们假设从根到叶子结点的路径中包含黑色结点的数量为N。 最短路径全黑长度为N,高度logN
最长路径一黑一红相间记住要保证每条路径包含的黑色结点个数是相同的那么长度为2N,高度2logN
最优情况 如果需要保证左右平衡那么有可能是全黑 或者 每条路径都是一黑一红相间的路径满二叉树。 最差情况 左子树全黑右子树一黑一红
可以发现最坏情况的时间复杂度和AVL树严格平衡一样都是O(logN)但是红黑树“非严格平衡”这种近似平衡的结构减少了大量旋转综合性能优于AVL树。
红黑树结点的定义
红黑树的实现类似AVL树我们采用KV模型实现红黑树并采用三叉链结构除此之外我们需要引入一个新的成员变量表示结点的颜色。这里我们采用枚举的方式定义结点颜色这样可以增加代码的可读性和可维护性便于后序操作。
//利用枚举定义颜色
enum colour
{RED,//0BLACK//1
};
//红黑树结点的定义
template class K,class V
struct RBTreeNode
{//key,valuepairK, V _kv;//三叉链结构RBTreeNodeK, V* _left;RBTreeNodeK, V* _right;RBTreeNodeK, V* _parent;//结点的颜色int _col;//构造函数RBTreeNodeK, V(const pairK, V kv): _kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr), _col(RED){ }
};为什么构造结点的时候结点的颜色默认设置成红色 我们先来回顾一下红黑树的性质3和性质4没有连续的红色结点每条路径上包含相同数量的黑色结点。
当我们向红黑树插入结点时若插入的是黑色结点那么所插入的那条路径上就比其他路径多了一个黑色结点这必然破换了性质4此时我们就需要对红黑树进行调整。
当我们向红黑树插入的是红色结点时如果此时插入结点的父节点也是红色结点那么就出现了连续的红色结点这就会破坏性质3此时我们需要对红黑树进行调整。如果父节点是黑色的我们就不需要对红黑树进行调整。
即插入黑色结点一定破坏红黑树的性质4必须对红黑树进行调整。插入红色结点可能会破坏红黑树的性质3可能需要对红黑树进行调整。综合看来插入红色结点更好。
红黑树的插入操作
红黑树一开始的插入操作跟AVL树一样关键在于第三步。
如果根节点为空先创建一个根节点注意红黑树根节点是黑色的找到插入结点插入的位置如果插入结点的父节点是红色的则需要对红黑树进行调整 红黑树在插入结点后如何对红黑树进行调整 如果插入结点的父节点是黑色的则不需要对红黑树进行调整。不破坏红黑树的性质。
如果插入结点的父节点是红色的则需要对红黑树进行调整因为我们默认插入的结点颜色是红色的这样就会出现连续的红色结点。
下面具体将红黑树的调整分成3种情况重点关注插入结点的父节点叔叔结点即父节点的兄弟结点祖父结点。
情况1 注意以下看到的树可能是一棵完整的树也可能是一棵子树以下是抽象图的展示。 插入结点的父节点是红色祖父结点是黑色叔叔存在且结点是红色。 调整方式我们先观察调整之前的图形这种情况下插入新的结点之后会出现连续的红色结点并且从g开始每条路径包含的黑色结点的数量为1。
那么为了避免出现连续的红色结点我们可以将父节点变黑但是为了保持每条路径黑色结点的数目不变因此我们还需要把祖父结点变红再将叔叔结点变黑这样就可以保持每条路径的黑色结点数目是相同的了也解决了红色结点连续的问题。 相信同学们还有疑问不是说根节点必须是黑色的吗为什么颜色调整之后根变成了红色呢 不要急因为调整还未结束。这种情况下祖父结点变成了红色如果祖父结点是根结点那么我们直接将祖父结点变成黑色即可。此时每条路径的保护的黑色结点又多了一个调整之前每条路径的黑色结点是1个现在每条路径包含的黑色结点是两个依然满足性质4.
但如果祖父结点不是根结点这棵树是一棵子树那么我们就需要将祖父结点当作新插入的结点再判断其父节点是否为红色若父节点也是红色那么需要根据叔叔的情况进行不同的调整。
注意插入结点的父节点为红叔叔结点存在且为红时cur结点无论是parent的左孩子还是右孩子调整方式都是一样的。
情况2 插入结点的叔叔不存在即插入结点的父节点的兄弟结点不存在。 若插入结点的叔叔不存在那么cur一定是新插入的结点而不是其它情况向上调整变化而来的因为叔叔不存在则p的孩子不可能存在黑色结点遵循性质4。
这种情况下祖孙三代的关系是一条直线我们需要先进行单旋操作再进行颜色调整颜色调整后这棵子树的根节点变成了黑色所以不需要再向上继续调整。
若p是g的左孩子cur是p的左孩子则这棵子树的左边较高我们以p为轴点进行右单旋再将parent父节点改为黑色祖父结点改为红色
若p是g的右孩子cur是p的左孩子则这棵子树的右边较高我们以p为轴点进行左单旋再将parent父节点改为黑色祖父结点改为红色。
情况3 插入结点的叔叔存在。且叔叔结点为黑色。 这种情况下一定是上次情况一调整之后出现的cur不可能是新插入的结点否则就不遵循性质4每条路径包含的黑色结点数量相同了。
这时单纯的变色无法直接解决问题情况三是由情况2变化而来的所以我们依然需要先进行单旋操作再进行颜色调整parent父节点改为黑色祖父结点u改成红色叔叔结点u依然保持黑色。颜色调整成功后这棵子树的根节点是黑色的所以无需继续向上进行调整。
同理 若p是g的左孩子cur是p的左孩子则这棵子树的左边较高我们以p为轴点进行右单旋再将parent父节点改为黑色祖父结点改为红色
若p是g的右孩子cur是p的左孩子则这棵子树的右边较高我们以p为轴点进行左单旋再将parent父节点改为黑色祖父结点改为红色。
注意情况二和情况三都是先进行旋转操作再进行颜色调整。并且调整成功后这棵子树的根节点已经变成黑色无需再进行向上调整。只有情况一祖父结点被改成红色才需要继续向上调整。
特殊情况
前面的情况123parentcurgrandparents,都是连成一条直线的。那么这个所谓的特殊情况就是parentcurgrandparents的路径从形状上看来是一条折线。
若形状呈一条折线那么有以下两种情况
parent在grandparents的左边cur在parent的右边 解决方法以parent为轴点先进行左单旋再以g为轴点进行右单旋即左右双旋最后调整结点颜色将cur变成黑色将grandparents变成红色
parent在grandparents的右边cur在parent的左边 解决方法先以p为轴点进行右单旋接着以g为轴点进行左单旋最后调整结点颜色将cur结点变成黑色将g结点变成红色。
注意除了情况一调整之后g结点会变成红色需要继续向上调整其它情况颜色调整完后g子树根节点都会被调整成黑色因此不需要继续向上调整。
代码实现 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;cur-_parent parent;}else{parent-_left cur;cur-_parent parent;}while (parent parent-_col RED){Node* grandfater parent-_parent;if (parent grandfater-_left){Node* uncle grandfater-_right;// 情况一 uncle存在且为红if (uncle uncle-_col RED){parent-_col uncle-_col BLACK;grandfater-_col RED;cur grandfater;parent cur-_parent;}else{if (cur parent-_left){// 情况二RotateR(grandfater);parent-_col BLACK;grandfater-_col RED;}else{// 情况三RotateL(parent);RotateR(grandfater);cur-_col BLACK;grandfater-_col RED;}break;}}else // (parent grandfater-_right){Node* uncle grandfater-_left;if (uncle uncle-_col RED){parent-_col uncle-_col BLACK;grandfater-_col RED;cur grandfater;parent cur-_parent;}else{// g // p// cif (cur parent-_right){RotateL(grandfater);parent-_col BLACK;grandfater-_col RED;}else{// g // p// cRotateR(parent);RotateL(grandfater);cur-_col BLACK;grandfater-_col RED;}break;}}}_root-_col BLACK;return true;}void RotateL(Node* parent){Node* subR parent-_right;Node* subRL subR-_left;parent-_right subRL;if (subRL)subRL-_parent parent;Node* ppNode parent-_parent;subR-_left parent;parent-_parent subR;if (ppNode nullptr){_root subR;_root-_parent nullptr;}else{if (ppNode-_left parent){ppNode-_left subR;}else{ppNode-_right subR;}subR-_parent ppNode;}}void RotateR(Node* parent){Node* subL parent-_left;Node* subLR subL-_right;parent-_left subLR;if (subLR){subLR-_parent parent;}Node* ppNode parent-_parent;subL-_right parent;parent-_parent subL;//if (_root parent)if (ppNode nullptr){_root subL;_root-_parent nullptr;}else{if (ppNode-_left parent){ppNode-_left subL;}else{ppNode-_right subL;}subL-_parent ppNode;}}红黑树的验证
1.验证其是否为二叉搜索树通过中序遍历 2.验证其是否满足红黑树的性质包括根节点为黑不能出现连续的红色结点每条路径包含的黑色结点的数量要相同。 //中序遍历判断是否为二叉搜索树void Inorder(){_Inorder(_root);}void _Inorder(Node* root){if (root nullptr)return;_Inorder(root-_left);cout root-_kv.first : root-_kv.second endl;_Inorder(root-_right);}bool Check(Node* root, int blackNum, const int ref){//root为空意味着走到了空节点if (root nullptr){//cout blackNum endl;if (blackNum ! ref){cout 违反规则本条路径的黑色节点的数量跟最左路径不相等 endl;return false;}return true;}//出现连续的红色结点则直接返回falseif (root-_col RED root-_parent-_col RED){cout 违反规则出现连续红色节点 endl;return false;}//统计路径中黑色结点的数量if (root-_col BLACK){blackNum;}return Check(root-_left, blackNum, ref) Check(root-_right, blackNum, ref);}bool IsBalance(){//空树也是平衡二叉树if (_root nullptr){return true;}//如果根节点不是黑色则直接返回falseif (_root-_col ! BLACK){return false;}//ref是reference的缩写翻译为参考//记录最左边黑色结点的数量int ref 0;//以最左边的路径包含的黑色结点数量为参考值进行各路径的比对Node* left _root;while (left){if (left-_col BLACK){ref;}left left-_left;}//利用check函数进行各条路径的比对return Check(_root, 0, ref);}红黑树的删除
红黑树的删除本节不做讲解有兴趣的同学可参考《算法导论》或者《STL源码剖析》 链接
红黑树和AVL树的比较
红黑树和AVL树都是高效的平衡二叉树增删改查的时间复杂度都是O(log2Nlog_2 Nlog2N)红黑树不追求绝对平衡其只需保证最长路径不超过最短路径的2倍相对而言降低了插入和旋转的次数所以在经常进行增删的结构中性能比AVL树更优而且红黑树实现比较简单所以实际运用中红黑树更多。
红黑树的应用
C STL库 – map/set、mutil_map/mutil_setJava 库linux内核其他一些库
