c++红黑树
1. 红黑树的概念
红黑树,是一种二叉搜索树,但在每个结点上增加一个存储位表示结点的颜色,可以是Red或Black。通过对任何一条从根到叶子的路径上各个结点着色方式的限制,红黑树确保没有一条路径会比其他路径长出俩倍,因而是接近平衡的。
2. 红黑树的性质
-
每个结点不是红色就是黑色
-
根节点是黑色的
-
如果一个节点是红色的,则它的两个孩子结点是黑色的
-
对于每个结点,从该结点到其所有后代叶结点的简单路径上,均包含相同数目的黑色结点
极端情况:
最短路径:全黑
最长路径:一黑一红到底
-
每个叶子结点都是黑色的(叶子结点是NULL结点)
-
红黑树的高度接近2logN
AVL树的高度接近logN,所以红黑树的搜索效率比AVL树要差一点,但是几乎可以忽略不计。但是AVL的相对低高度,是通过频繁的旋转得到的。
3. 红黑树的定义
在定义红黑树的代码时,为了增加代码的可读性,可以用枚举类型把黑色和红色从数字转换成字母。在插入结点的时候,如果直接插入黑色结点会使红黑树的结构变得不可控,所以在插入结点的时候是默认插入红色结点,所以在初始化结点的时候,直接把结点的颜色设定成红色。
//颜色
enum color
{RED,BLACK
};//红黑树节点的定义
template<class K, class V>
struct RBTreeNode
{RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _right;RBTreeNode<K, V>* _parent;pair<K, V> _kv;color _col;//构造函数RBTreeNode(const pair<K, V>& kv):_left(nullptr),_right(nullptr),_parent(nullptr),_kv(kv),_col(RED){}
};
4. 红黑树的插入
红黑树在插入的时候会涉及到结点的变色和旋转,是红黑树结构最核心的内容。
红黑树的插入可以分两种情况讨论,为了方便描述,以插入的结点的视角:
p:表示父结点
g:表示爷结点
u:表示叔结点
cur:表示当前的操作结点(因为会涉及变色的向上更新)
4.1 u存在,且p、u为红
cur为插入的结点,此时cur、p、u均为红色结点,因为规则规定不能有两个相连的红色结点,所以需要对p结点和u进行变色,同时g结点也需要变成红色。
g结点变色后,还需要分两种情况
1. g结点还有父结点:
如果g结点还有父结点,那么需要把cur结点变成g结点,重复变色的操作,直到满足不变色的条件
2. g结点就是根结点:
如果g结点就是根结点,那么需要把g结点从红色变回黑色
4.2 p为红,u为黑或不存在
4.2.1 叔结点存在且为黑
具体操作为:
(p在g的左子树,cur是p的左孩子)
1.将p结点右旋(我的右变成你的左,你变成我的右)
2.p变黑,g变红
相反,如果p在g的右子树,cur是p的右孩子。那么对p进行左旋,变色操作相同。因为,整个变色和旋转的操作都没有对u进行操作,所以u存不存在都不会影响。
出现p、u异色或p存在、u不存在的情况分析:
注意:如果u存在,cur不一定是插入的结点,cur可以是插入后向上更新的结点。对于情况一,cur可能是插入的结点也可能不是。但对于第二种情况,cur只有可能是向上更新的结点,也就是说,树的情况应该是这样:
注意,这种情况不但违反了不能有连续两个红色结点的规则,还违反了最短路径不能超过最长路径的规则。所以这种情况需要进行旋转操作,因为旋转的目的就是为了降低整个树的高度。
而当u不存在时,cur则一定是插入的结点:
注意,这里不仅违反了不能有两个连续红色结点的规则,因为如果只对p变色,整颗树就违反了最长路径和最短路径的黑色结点数量相等的规则(g没有右子树,可以看作最短路径只有g一个结点),所以需要进行旋转操作让整棵树的高度降低。
4.3 需要双旋的情况二
第三种情况和第二种情况基本相同,但g、p、cur形成了一个<
或>
的形状
举形状为<
的为例:
1.先对cur进行左旋
2.再对cur进行右旋
3.g变红,cur变黑
如果是>
形状的情况,那么需要反过来对cur先右旋再左旋,变色操作相同,g变红,cur变黑。
因为整个过程没有对u进行操作,所以u存在和不存在都没有影响
注意情况三和情况二的不同:
情况三需要双旋
结点最终位置不同
变色操作的对象不同
5. 红黑树的删除
红黑树删除结点可以分为两个步骤:
1.按二叉搜索树删除
2.调整为红黑树结构
5.1 二叉搜索树的删除
二叉搜索树删除可以分为三种情况
1.删除的是叶子结点:
叶子结点直接删,删除叶子结点对二叉搜索树的结构没有影响
2.删除的结点有一个孩子:
有一个孩子的结点的删除,只需要让被删除的结点的孩子代替它的位置即可
3.删除的结点有两个孩子:
中序遍历的下一个结点代替被删除结点的位置
5.2 调整红黑树
5.2.1 被删除的是红色结点
删除红色结点不会破会红黑树的结构,所以对红色结点的删除不需要调整结构
如果是叶子结点,可以直接删除,无需调整操作
如果被删除的不是叶子节点,那么这个结点的前驱与它的父结点向上更新值,直到找到本来要删除的结点,然后再把前驱结点删除
5.2.2 被删除的是黑色结点
黑色结点大体可以分成三种情况讨论,被删除结点为D,它的右孩子是subR,它的右孩子的右孩子是subRR
1.D是黑色,subR是红色,subRR是黑色 :
因为没有对subRR进行操作,所以subRR在这种情况下也可以是空
操作:
1.按二叉搜索树删除
2.把subR改成黑色
2. D是黑色,subR是黑色,subRR是红色:
操作:
- 按二叉搜索树删除
- 把subR改成红色
3.D是黑色,subR是黑色,SubRR是黑色:
先看删除D结点会造成的情况:
删除D结点发现,无法通过简单的变色来调整红黑树的结构
那么此时就需要到subR的层面旋转结点,可以将情况分为四种:其中两种互为镜像,所以这里分析非镜像的两种情况:
此处原本的subR更改标记为cur,它的父结点为p(注意这里p是删除D结点后的结点),它的兄弟结点为b。为了避免结点过多导致图像复杂,简化的图像会有多个标记落在空结点上。
1.cur为p的右孩子,b为黑:
在这种情况中,还需要细分为四个小情况:
它们对应的解决办法为:
2.cur为p的右孩子,b为红:
对于这种情况,需要把他转换成上面的情况再进行操作:
6. 红黑树的检查
bool Check(Node* cur){if (cur == nullptr)return true;if (cur->_col == RED && cur->_parent->_col == RED){cout << cur->_kv.first << "存在连续的红色节点" << endl;return false;}return Check(cur->_left)&& Check(cur->_right);}
黑树的检查
bool Check(Node* cur){if (cur == nullptr)return true;if (cur->_col == RED && cur->_parent->_col == RED){cout << cur->_kv.first << "存在连续的红色节点" << endl;return false;}return Check(cur->_left)&& Check(cur->_right);}