红黑树

1. 二叉搜索树（BST）

1.1 概念

二叉搜索树（BST）具备以下特性：

• 左子树上所有结点的值均小于或等于它的根结点的值
• 右子树上所有结点的值均大于或等于它的根结点的值
• 左、右子树也分别为二叉排序树

1.2 退化

如下图绿色部分，二叉搜索树在理想情况下可以将查找的效率达到O(logN)。如下图蓝色部分，如果插入的节点顺序是完全单调的，此时二叉搜索树会退化为链表

BST退化

对此，平衡二叉树（AVL） 和 红黑树（Red-Black Tree） 通过设计建树的规则，控制了树的层数和节点位置，解决了这一问题

2. 平衡二叉树（AVL）

2.1 概念

平衡二叉树（AVL）在具备二叉搜索树特性的同时，也具备以下特性：

• 任何两个节点的子树高度最大差为1（平衡因子）
• 增加和删除节点时，需要旋转来重新平衡

2.2 AVL旋转

AVL在插入或删除节点后，如果不满足平衡因子最大差为1的原则，则会触发旋转机制，其中左旋为逆时针旋转，右旋为顺时针旋转

2.2.1 AVL失衡条件

导致AVL失衡的条件有4个：

• LL：左左结构失衡，插入的元素在子树root的左侧不平衡元素的左侧
• RR：右右结构失衡，插入的元素在子树root右侧的不平衡子树的右侧
• LR：左右结构失衡，插入的元素在子树root的左侧不平衡元素的右侧
• RL：右左结构失衡，插入的元素在子树root右侧的不平衡子树的左侧

2.2.2 AVL插入

1. LL & RR

LL&RR

LL和RR类似，当失衡节点在一侧的时候，需要向另一侧进行旋转

• LL：右旋
• RR：左旋

比如LL的情况，插入1之后，发生了LL失衡，此时需要向右侧填充节点，故将跟节点这一层移动到其左子树的右侧，取缔原右侧的节点8位置。同时因为二叉树搜索树的性质，原右侧节点8小于节点9，所以可以将8放在9的左侧

2. LR & RL

LR&RL

LR和RL类似，当失衡节点出现时，需要先进行一次旋转，将其转换为LL和RR的情况再处理，具体表现为：

• LR：先左旋再右旋
• RL：先右旋再左旋

2.2.3 AVL删除

删除和插入类似，有以下条件：

• 删除叶子节点时，并不断向上判断父节点是否失衡并根据类型旋转
• 删除节点只有一个子节点时，直接删除，并用子节点替换自己，并进行判断和旋转
• 删除节点有两个子节点时，找到前驱或后驱节点进行替换，并进行判断和旋转

2.3 AVL特点

AVL虽然保持了树的平衡，但其对树高度平衡的限制过于严格，在实际使用中时，往往经常触发旋转。所以AVL更适合用在查找频繁，增删不频繁的场景。

对此，红黑树拓宽了对树高度平衡的限制条件，平衡了查找和增删效率

3. 红黑树（RBTree）

3.1 概念

红黑树的通过增加颜色的属性，以空间换时间，具有均衡的查找、增删性能，使用范围很广。如Java中的HashMap、TreeMap等都以其作为底层实现，具有以下特点：

• 节点非黑即红
• 根节点一定是黑色
• 叶子节点一定是黑色
• 红色节点的父、子不能是红色
• 从任意节点到叶子的所有路径，都包含相同数量的黑色节点

RBTree的叶子节点是NULL的，而AVL不是。由于红色节点的限制较少，所以插入的时候会将节点设置为红色。

3.2 红黑树平衡

当红黑树的5项原则被打破的时候，根据三种操作来恢复：

• 变色：红变黑或黑变红
• 左旋
• 右旋

3.2.1 红黑树插入

当插入后出现冲突时红黑树具有以下策略

1. 失衡在根节点左侧时，父节点和子节点均为红：

• 叔叔为红：爷爷节点变为红色，父和叔叔节点变为黑色，整体由黑红红变为红黑红

红黑树插入

• 叔叔为黑：
  • LL失衡：父亲F变为黑，爷爷P变为红，对F进行右旋
  • LR失衡：对F进行左旋，转换为LL失衡进行处理

父节点为红叔叔节点为黑

2. 失衡节点在右侧时同理，对称处理即可