C++之红黑树
红黑树的概念
红黑树是一种二叉搜索树，在每个节点上增加一个储存位代表节点的颜色，可以是黑色或者是红色。通过对任何一条从根节点到叶子节点的路径上节点颜色的限制，红黑树可以保证没有一条路径会比其他路径长两倍，由此接近平衡。
红黑树的性质
1.每个节点不是红色就是黑色
2.根节点是黑色的
3.如果一个节点是红色，那么它的孩子节点是黑色
4.对于每个节点，从该节点到其所有后代节点的简单路径上，均包含相同数目的黑色节点
5.每个叶子节点都是黑色的(在这里叶子节点指根节点)
红黑树节点的定义
包含左孩子，右孩子，双亲，值域，节点
红黑树的结构
在红黑树钟增加一个头节点，将头节点给成黑色，让头节点的pParent指向红黑树的根节点，pLeft指向红黑树的最小节点，pRight指向红黑树的最大节点
红黑树的插入操作
红黑树实在二叉搜索树的基础上加上限制平衡的条件，所以可以分为两步
1.按照二叉搜索树的规则插入新的节点
2.检测新节点插入后，红黑树的性质是否被破坏
1）新节点默认颜色为红色，如果双亲的颜色是黑色，就没有违反红黑树的规则，不需要进行调整
2）新节点插入节点的双亲为红色时，就违反了红色节点的孩子节点只能为黑色的规则
这个时候，就要分三种情况进行讨论
->第一种情况，cur为红，p为红，g为黑，u存在且为红
解决方式是将p，u改为黑色，g改为红色，然后把g当作cur，继续向上调整
->cur为红，p为红，g为黑，u不存在或者u存在且为黑
u的情况有两种
【1】u节点不存在，cur一定是新插入节点
【2】u节点存在，它一定是黑色的，cur节点原来的颜色一定是黑色的
解决方式
p为g的左孩子，cur为p的左孩子，则进行右单旋；
p为g的右孩子，cur为p的右孩子，则进行左单旋；
p变黑，g变红
->cur为红，p为红，g为黑，u不存在或者u存在且为黑
p为g的左孩子，cur为p的右孩子，则对p进行左单旋；
p为g的右孩子，cur为p的左孩子，则对p进行右单旋；
操作以后就转化为了情况二
红黑树的验证
验证分为两个部分
1.是否满足搜索二叉树性质
2.是否满足红黑树的性质
红黑树的删除
。。。
红黑树与AVL树的比较
红黑树与AVL的增删查改的时间复杂度都是O(log(N)),红黑树不追求绝对的平衡，所以性能更优
红黑树的应用
1.C++的STL（比如map/set，multiset/multimap）
2.。。。
红黑树的迭代器
1.begin()与end()
begin可以是红黑树的最小节点，end是红黑树最大节点的下一个位置
由于end不能为空（因为进行--操作要找点最大节点），所以让end为红黑树的头节点
2.operator++与operator--
->关于operator++，分两种情况，若右子树存在，找右子树的最左节点。若右子树不存在，继续向上查找，直到该节点不为双亲节点的右节点
->关于operator--，分三种情况
pNode在head节点的位置，那么--操作后，指向树中的最大节点；
pNode的左子树存在，--操作后为左子树的最右节点
pNode的左子树不存在，就一直向上找
改造红黑树
1.valuetype：如果是map，就是pair<k,v>类型，如果是set，就是k类型
2.keyOfvalue：通过value来获取key的一个仿函数类
map的模拟实现
在map中封装红黑树
set的模拟实现
在set中封装红黑树
原文地址：https://blog.csdn.net/ly1611240037/article/details/143019297
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！