BST
二叉查找树、二叉搜索树、二叉排序树都是同一个概念,只是名字不同而已。
二叉查找树(BST)具备以下特性:
- 左子树上所有结点的值均小于或等于它的根结点的值。
- 右子树上所有结点的值均大于或等于它的根结点的值。
- 左、右子树也分别为二叉排序树。
缺点:
很有可能退化成单链表,时间复杂度为O(n)。
为了避免这种情况,引入了二叉平衡树和红黑树,它们都是通过建树规则来控制树的层数和节点位置。
AVL
特性:
- 首先是一颗二叉查找树。
- 任何一个节点的左右子树的高度差最多为1。
- 它的左右子树都是AVL树。
1、AVL的恢复平衡过程的三个操作
当插入和删除节点后的树可能会破坏平衡二叉树的规则,如何恢复平衡?
分为左旋和右旋。
(1)左旋
①旋转之前,首先确定旋转支点(pivot): 从添加的节点开始,不断地往父节点去找不平衡的节点,把第一个不平衡的节点作为旋转支点。
②具体的旋转步骤:
1、把旋转支点E原来的右子节点S向上晋升为根节点;
2、旋转支点E左旋降级,变成新的根节点S的左子节点。
但是当需要晋升的节点有左子节点的话,这时候怎么旋转呢?
1、把旋转支点E原来的右子节点S向上晋升为根节点
2、旋转支点E左旋降级,变成新的根节点S的左子节点
3、S原来的左子节点变成旋转支点E的右子节点。
(2)右旋
①旋转之前,首先确定旋转支点;
②具体的旋转步骤:
1、把旋转支点E原来的左子节点S向上晋升为根节点;
2、旋转支点E右旋降级,变成根节点S的右子节点;
3、如果S有右子节点,则S原来的右子节点变成旋转支点E的左子节点。
2、AVL子树失衡的四大场景
导致AVL失衡的场景就是有限的4个:
左左结构失衡(LL型失衡)
右右结构失衡(RR型失衡)
左右结构失衡(LR型失衡)
右左结构失衡(RL型失衡)
删除元素,也会导致AVL失衡,需要再平衡,但是原理和插入元素是类似的。
这里聚焦 介绍插入元素的平衡过程, 删除元素,不做介绍。
场景1:左左结构失衡(LL型失衡)
当左子树的左子树有节点插入时破坏平衡规则。
一次右旋便可。
场景2:右右结构失衡(RR型失衡)
当右子树的右子树有节点插入时破坏平衡规则。
一次左旋便可。
场景3:左右结构失衡(LR型失衡)
当左子树的右子树有节点插入时破坏平衡规则。
先局部左旋把左右变成左左,然后再整体进行一次右旋。
场景4:右左结构失衡(RL型失衡)
当右子树的左子树有节点插入时破坏平衡规则。
先局部进行右旋把右左变成右右,然后再整体进行左旋。
正是由于这种严格的平衡条件,导致AVL在插入和删除的时候,可能需要频繁地进行旋转来保持平衡,所以AVL树多用于查询, 而不是频繁增加删除的场景。
RBT
红黑树也是一种自平衡二叉查找树,放宽了树的平衡条件。
(1)它与AVL树类似,都在添加和删除的时候通过旋转操作保持二叉树的平衡,以求更高效的查询性能。
(2)与AVL树相比,红黑树牺牲了部分平衡性,以换取插入/删除操作时较少的旋转操作,整体来说性能要优于AVL树。
1、红黑规则
可以按照括号里边的分类,记住红黑树的几个原则:
(颜色属性)性质1:节点非黑即红
(根属性)性质2:根节点一定是黑色
(叶子属性)性质3:叶子节点(NIL)一定是黑色
(红色属性)性质4:每个红色节点的两个子节点,都为黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
(黑色属性)性质5:任一节点到其每个叶子的所有路径,都包含相同数目的黑色节点。
记忆要点:根叶黑,不红红,黑路同。
(1)黑色属性,可以理解为平衡特征, 如果满足不了平衡特征,就要进行平衡操作。
(2)基于上面的原则,我们一般在插入节点的时候,会将这个节点设置为红色,
原因参照最后一条原则: 红色破坏原则的可能性最小,如果是黑色, 很可能导致这条支路的黑色节点比其它支路的要多1,破坏了平衡。
(3)空间换时间
RBT有点属于一种空间换时间类型的优化,在AVL的节点上,增加了颜色的属性,相当于增加了空间的消耗。通过颜色属性的增加, 换取后面平衡操作的次数减少。
2、红黑树的恢复平衡过程的三个操作
一旦红黑树5个原则有不满足的情况,我们视为平衡被打破,如何恢复平衡?
靠它的三种操作:变色、左旋、右旋。
(1)变色
节点的颜色由红变黑或由黑变红。
(2)左旋
红黑树的左旋、右旋操作,AVL树的左旋,右旋操作差不多。
(3)右旋
3、红黑树插入节点情景分析
(1)红黑树的节点结构
红黑树中的节点设计:
class TreeNode<K, V> {
K key;
V value;
TreeNode<K, V> left, right, parent;
Color color;
public TreeNode(K key, V value, TreeNode<K, V> parent) {
this.key = key;
this.value = value;
this.parent = parent;
this.color = Color.RED; // 默认新插入节点为红色
}
}
默认新插入节点为红色。
场景1:红黑树为空树
将节点的颜色修改为黑色即可。
场景2:插入节点的Key已经存在
将对应的Value更新为新插入节点的值。
场景3:插入节点的父节点为黑色
由于新插入的节点是红色,而父节点是黑色,所以并不会改变路径中黑色节点的数目,因此不需要进行调整,直接插入就行。
场景4:插入节点的父节点为红色
根据性质2:根节点是黑色。
如果插入节点的父节点为红色节点,那么该父节点不可能为根节点,所以插入节点总是存在祖父节点(三代关系)。
根据性质4:每个红色节点的两个子节点一定是黑色的。不能有两个红色节点相连。
此时会出现两种状态:
父亲和叔叔为红色
父亲为红色,叔叔为黑色
如图
只关注这一部分。
首先来看没插入之前,不关注叶子节点,左左这一路径中黑色节点的个数为1,想要在插入新节点时不破坏黑色平衡,即不改变这个路径中黑色节点的个数,所以将爷父插入节点的颜色修改为红黑红,由于父节点的颜色由红色变为黑色,需要关注在右右这一路径中黑色节点的个数,如果叔叔节点是红色,此时可以修改为黑色,则没有破坏黑色平衡,而如果是黑色,则需要旋转。
场景4.1:父亲和叔叔为红色节点
总结下来就是:
变色处理:黑红红 ==> 红黑红
1.将父节点和叔叔节点改为黑色;
2.将爷爷改为红色;
3.将爷爷设置为当前节点,进行后续处理。
这里有一个细节需要注意:
如果插入节点的爷爷节点为根节点,则需要把根节点重新变成黑色,这样为什么没有问题呢?
因为如果是改变根节点的颜色的话,从任一节点到叶子节点的黑色节点数目都会+1,并不违反性质5。
如果爷爷的父节点是黑色,那么又回到了场景2,无需做任何处理;
但如果爷爷的父节点是红色,则违反红黑树性质了,所以需要将爷爷设置为当前节点,继续插入操作, 作自平衡处理,直到整体平衡为止。
场景4.2:叔叔为黑色,父亲为红色,并且插在父亲的左节点
分为两种情况:
- LL 红色插入
- LR 红色插入
叔叔为黑色,并且节点的父亲节点是爷爷节点的左子节点。
场景4.2.1 LL型失衡
细分场景 1: 新插入节点,为其父节点的左子节点(LL红色情况), 插入后 就是LL 型失衡。
自平衡处理:
1.变颜色:将父亲节点设置为黑色,将爷爷节点设置为红色;
2.以爷爷节点为支点进行右旋。
场景4.2.2 LR型失衡
细分场景 2: 新插入节点,为其父节点的右子节点(LR红色情况), 插入后就是LR 型失衡。
自平衡处理:
1.先将左右变成左左,即以父节点为支点进行左旋;
2.再将父节点设置为当前节点,得到LL红色情况;
3.按照LL红色情况处理(1.变色 2.以爷爷节点为支点进行右旋)。
情景4.3:叔叔为黑节点,父亲为红色,并且父亲节点是祖父节点的右子节点
情景4.3.1:RR型失衡
新插入节点,为其父节点的右子节点(RR红色情况)。
自平衡处理:
1.变色:将父亲节点设置为黑色,将爷爷节点设置为红色;
2.以爷爷节点为支点进行左旋。
情景4.3.2:RL型失衡
新插入节点,为其父节点的左子节点(RL红色情况)。
自平衡处理:
1.以父节点为支点进行右旋;
2.将父节点设置为当前节点,得到RR红色情况;
3.按照RR红色情况处理(1.变色 2.以爷爷节点为支点进行左旋)
总结的一张图:
参考博客: