红黑树(RBTree)
红黑树是一种特化的AVL树(平衡二叉树)
红黑树是在1972年由Rudolf Bayer发明的,当时被称为平衡二叉B树(symmetric binary B-trees).
在1978年被 Leo J. Guibas 和 Robert Sedgewick 修改为如今的“红黑树”.
什么是红黑树?
红黑树也是一种自平衡二叉查找树,它与AVL树类似,都在添加和删除的时候通过旋转操作保持二叉树的平衡,以求更高效的查询性能。
与AVL树相比,红黑树牺牲了部分平衡性,以换取插入/删除操作时较少的旋转操作,整体来说性能要优于AVL树。
虽然RBTree是复杂的, 但它的最坏情况运行时间也是非常良好的,并且在实践中是高效的:
它可以在O(log n)时间内做查找,插入和删除,这里的n 是树中元素的数目.
红黑树的特性
红黑树是实际应用中最常用的平衡二叉查找树,它不严格的具有平衡属性,但平均的使用性能非常良好。
在红黑树中,节点被标记为红色和黑色两种颜色。
红黑树的原则有以下几点:
- 特性1:节点非黑即红
- 特性2:根节点一定是黑色
- 特性3:叶子节点(NIL)一定是黑色
- 特性4:每个红色节点的两个子节点都为黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
- 特性5:从任一节点到其每个叶子的所有路径,都包含相同数目的黑色节点。
红色属性 说明,红色节点的孩子,一定是黑色。 但是,RBTree 黑色节点的孩子,可以是红色,也可以是黑色,具体如下图。
叶子属性 说明, 叶子节点可以是空nil ,AVL的叶子节点不是空的,具体如下图。
基于上面的原则,我们一般在插入红黑树节点的时候,会将这个节点设置为红色,
原因参照最后一条原则: 红色破坏原则的可能性最小,如果是黑色, 很可能导致这条支路的黑色节点比其它支路的要多1,破坏了平衡。
记忆要点:
可以按照括号里边的分类,记住 红黑树的几个原则:
- (颜色属性)性质1:节点非黑即红
- (根属性)性质2:根节点一定是黑色
- (叶子属性)性质3:叶子节点(NIL)一定是黑色
- (红色属性)性质4:每个红色节点的两个子节点,都为黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
- (黑色属性)性质5:从任一节点到其每个叶子的所有路径,都包含相同数目的黑色节点。
黑色属性,可以理解为平衡特征, 如果满足不了平衡特征,就要进行平衡操作。
空间换时间
RBT有点属于一种空间换时间类型的优化,
在avl的节点上,增加了 颜色属性的 数据,相当于 增加了空间的消耗。 通过颜色属性的增加, 换取,后面平衡操作的次数 减少。
黑色完美平衡
红黑树并不是一颗AVL平衡二叉搜索树,从图上可以看到,根节点P的左子树显然比右子树高
根据 红黑树的特性5,从任一节点到其每个叶子的所有路径,都包含相同数目的黑色节点, 说明:
rbt 的 左子树和右子树的黑节点的层数是相等的
红黑树的平衡条件,不是以整体的高度来约束的,而是以黑色 节点的 高度,来约束的。
所以称红黑树这种平衡为黑色完美平衡。
看看黑色完美平衡的效果,
去掉 rbt中的红色节点,会得到 一个四叉树, 从根节点到每一个叶子,高度相同,就是rbt的root到叶子的黑色路径长度。
红黑树的恢复平衡过程的三个操作
一旦红黑树5个原则有不满足的情况,我们视为平衡被打破,如何 恢复平衡?
靠它的三种操作:变色、左旋、右旋。
1.变色
节点的颜色由红变黑或由黑变红。(这个操作很好了解)
2.左旋
以某个结点作为支点(pivot),其父节点(子树的root)旋转为自己的左子树(左旋),pivot的原左子树变成 原root节点的 右子树,pivot的原右子树保持不变。
3.右旋:
以某个结点作为支点(pivot),其父节点(子树的root)旋转为自己的右子树(右旋),pivot的原右子树变成 原root节点的 左子树,pivot的原左子树保持不变。
红黑树的左旋、右旋操作,AVL树的左旋,右旋操作 差不多
说明:本文会以pdf格式持续更新,更多最新尼恩3高pdf笔记,请从下面的链接获取:语雀 或者 码云
红黑树插入节点情景分析
红黑树的节点结构
先看看红黑树的节点结构
以HashMap中的红黑树的结构定义为例子:
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
volatile V val;
volatile Node<K,V> next;
}
/**
* Nodes for use in TreeBins
*/
static final class TreeNode<K,V> extends Node<K,V> {
TreeNode<K,V> parent; // red-black tree links
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev; // needed to unlink next upon deletion
boolean red;
TreeNode(int hash, K key, V val, Node<K,V> next,
TreeNode<K,V> parent) {
super(hash, key, val, next);
this.parent = parent;
}
默认新插入的节点为红色:
因为父节点为黑色的概率较大,插入新节点为红色,可以避免颜色冲突
场景1:红黑树为空树
直接把插入结点作为根节点就可以了
另外:根据红黑树性质 2根节点是黑色的。还需要把插入节点设置为黑色。
场景2:插入节点的Key已经存在
更新当前节点的值,为插入节点的值。
情景3:插入节点的父节点为黑色
由于插入的节点是红色的,当插入节点的父节点是黑色时,不会影响红黑树的平衡,
所以: 直接插入无需做自平衡。
情景4:插入节点的父节点为红色
根据性质2:根节点是黑色。
如果插入节点的父节点为红色节点,那么该父节点不可能为根节点,所以插入节点总是存在祖父节点(三代关系)。
根据性质4:每个红色节点的两个子节点一定是黑色的。不能有两个红色节点相连。
此时会出现两种状态:
- 父亲和叔叔为红色
- 父亲为红色,叔叔为黑色
如图
场景4.1:父亲和叔叔为红色节点
根据性质4:红色节点不能相连 ==》祖父节点肯定为黑色节点:
父亲为红色,那么此时该插入子树的红黑树层数的情况是:黑红红。
因为不可能同时存在两个相连的红色节点,需要进行 变色, 显然处理方式是把其改为:红黑红
变色 处理:黑红红 ==> 红黑红
1.将F和V节点改为黑色
2.将P改为红色
3.将P设置为当前节点,进行后续处理
可以看到,将P设置为红色了,
如果P的父节点是黑色,那么无需做处理;
但如果P的父节点是红色,则违反红黑树性质了,所以需要将P设置为当前节点,继续插入操作, 作自平衡处理,直到整体平衡为止。
场景4.2:叔叔为黑色,父亲为红色,并且插在父亲的左节点
分为两种情况
- LL 红色插入
叔叔为黑色,或者不存在(NIL)也是黑节点,并且节点的父亲节点是祖父节点的左子节点
注意:单纯从插入来看,叔叔节点非红即黑(NIL节点),否则破坏了红黑树性质5,此时路径会比其他路径多一个黑色节点。
场景4.2.1 LL型失衡
细分场景 1: 新插入节点,为其父节点的左子节点(LL红色情况), 插入后 就是LL 型失衡
自平衡处理:
1.变颜色:
将F设置为黑色,将P设置为红色
2.对F节点进行右旋
场景4.2.2 LR型失衡
细分场景 2: 新插入节点,为其父节点的右子节点(LR红色情况), 插入后 就是LR 型失衡
自平衡处理:
1.对F进行左旋
2.将F设置为当前节点,得到LL红色情况
3.按照LL红色情况处理(1.变色 2.右旋P节点)
情景4.3:叔叔为黑节点,父亲为红色,并且父亲节点是祖父节点的右子节点
情景4.3.1:RR型失衡
新插入节点,为其父节点的右子节点(RR红色情况)
自平衡处理:
1.变色:
将F设置为黑色,将P设置为红色
2.对P节点进行左旋
情景4.3.2:RL型失衡
新插入节点,为其父节点的左子节点(RL红色情况)
自平衡处理:
1.对F进行右旋
2.将F设置为当前节点,得到RR红色情况
3.按照RR红色情况处理(1.变色 2.左旋 P节点)
暂无评论内容