一：二叉搜索树
1.1 回顾二叉搜索树
我们在树的章节中学习了二叉搜索树的概念。二叉搜索树满足以下性质：如果它的左子树存在，则左子树所有节点的值均小于根节点的值；如果右子树存在，则右子树所有节点的值均大于根节点的值。同时，左右子树也必须分别是二叉搜索树。这些特性使得二叉搜索树能够高效地执行查找、插入和删除操作。
从上述概念以及图中可以看出，二叉搜索树具有以下特性：
- 二叉搜索树中最左侧的节点是树中最小的节点，最右侧节点一定是树中最大的节点
- 采用中序遍历遍历二叉搜索树，可以得到一个有序的序列
1.2 二叉搜索树的查找
既然将其称之为二叉搜索树，所以这棵树最主要的作用肯定是进行查询，而且其查询原理特别简单，插入和删除操作也都依赖于查找来完成。那么我们可以思考一下今天：二叉搜索树的查找效率究竟有多高呢？
插入和删除操作都必须基于查找，因此查找效率直接影响二叉搜索树中各项操作的性能。在一个包含 n 个节点的二叉搜索树中，如果每个元素被查找的概率相同，那么节点越深，所需的比较次数就越多。此外，对于相同的关键码集合，插入顺序的不同可能导致生成不同结构的二叉搜索树，从而影响树的性能表现。
在最优情况下，二叉搜索树呈完全二叉树结构，此时平均比较次数最低；而在最差情况下，二叉搜索树则可能退化为单支树，导致平均比较次数显著增加，性能大幅下降。因此，我们不禁思考：是否存在一种改进方案，使得无论关键码的插入顺序如何，都能够保持二叉搜索树的最佳性能？由此我们就引入了二叉平衡树，而二叉平衡树又包含了 AVL 树和红黑树
二：AVL 树
尽管二叉搜索树能够提高查找效率，但当数据有序或接近有序时，二叉搜索树会退化为单支树，这使得查找元素的效率下降，类似于在顺序表中搜索。
为解决这一问题，一名俄罗斯数学家发明了一种自平衡的二叉搜索树 —— AVL 树。AVL 树保持每个节点左右子树的高度差的绝对值不超过1，从而降低树的高度，减少平均搜索长度，我们把每个节点左右子树的高度差的绝对值叫做平衡因子，AVL 树的平衡因子只能为 -1、0 或 1。
2.1 AVL 树节点的定义
为了能够更简单的实现一个 AVL 树，我们在定义节点的时候维护一个平衡因子，具体节点定义如下：
class AVLTreeNode {
public AVLTreeNode left = null; // 节点的左孩子
public AVLTreeNode right = null; // 节点的右孩子
public AVLTreeNode parent = null; // 节点的双亲
public int val = 0; // 节点的值
public int bf = 0; // 当前节点的平衡因子 = 右子树高度 - 左子树的高度
public AVLTreeNode(int val) {
this.val = val;
}
}
2.2 AVL 树的插入
AVL 树是在二叉搜索树的基础上引入平衡因子的，因此也可以视为一种特殊的二叉搜索树。AVL 树的插入过程可以分为两步：第一步是按照二叉搜索树的规则插入新节点；第二步是插入新节点后，pParent 的平衡因子需要进行调整。在插入之前，pParent 的平衡因子有三种情况：-1、0 和 1，根据插入的方向，可以分为以下两种情况：
- 如果 pCur 被插入到 pParent 的左侧，则将 pParent 的平衡因子减 1。
- 如果 pCur 被插入到 pParent 的右侧，则将 pParent 的平衡因子加 1。
此时，pParent 的平衡因子可能出现以下三种情况：
平衡因子为 0：这表示在插入之前，pParent 的平衡因子为 -1 或 1，插入后更新为 0，此时满足 AVL 树的平衡性质，插入成功。
平衡因子为 +1 或 -1：这表明插入之前，pParent 的平衡因子一定为 0，插入后更新为 +1 或 -1，此时以 pParent 为根的树的高度增加，需要继续向上更新父节点的平衡因子，因为子树的平衡因子由 0 变化成 - 1 和 1 说明树的高度增加了，所以插入新节点可能会影响父节点的高度。
平衡因子为 +2 或 -2：这种情况违反了 AVL 树的平衡性质，因此需要对 pParent 进行旋转处理，以恢复平衡。
boolean insert(int val) {
// 按照二叉搜索树的规则将节点插入到 AVL 树中。
// 此处省略代码
// cur插入后，parent 的平衡因子一定会发生改变，此时必须对 parent 的平衡因子进行调整
while (null != parent) {
// 更新双亲节点的平衡因子
if (cur == parent.left) {
parent.bf--;
} else {
parent.bf++;
}
if (parent.bf == 0) {
break;
} else if (parent.bf == -1 || parent.bf == 1) {
// 向上调整
cur = parent;
parent = cur.parent;
} else {
if (-2 == parent.bf) {
// 右单旋
// 此处代码省略
} else {
// 左旋
// 此处代码省略
}
break;
}
}
return true;
}
2.3 AVL 树的旋转
在原本平衡的 AVL 树中插入一个新节点可能导致树的不平衡。为了恢复平衡，树的结构需要进行调整。根据新节点插入的位置不同，AVL 树的旋转可以分为以下四种情况：
- 新节点插入到较高左子树的左侧：执行右单旋转。
- 新节点插入到较高右子树的右侧：执行左单旋转。
- 新节点插入到较高左子树的右侧：先进行左单旋转，然后再进行右单旋转（左右双旋）。
- 新节点插入到较高右子树的左侧：先进行右单旋转，然后再进行左单旋转（右左双旋）。
2.3.1 右单旋
在插入新节点之前，AVL 树是平衡的。当新节点被插入到 30 的左子树时，30 的左子树高度增加了一层，导致以 60 为根的二叉树失去了平衡。为了恢复平衡，必须将 60 的左子树高度减少一层，并增加右子树的高度，即将左子树的根往上提。
由于 60 大于 30，因此可以将 60 插入到 30 的右子树，以实现左子树高度的减少和右子树高度的增加。如果 30 已经有右孩子，右孩子的值一定大于 30 小于 60，因此新节点将放在 60 的左子树中。此外，由于 30 的右子树已经存在，此时又增加了一个 60 右子树，此时它就有 3 个分支了，这就不符合搜索树的特性了，所以要把一个子树进行转移，原右子树的节点需要转移至 60 的左子树，以保持 AVL 树的特性。旋转完成后，需要更新相关节点的平衡因子。
在旋转过程中，还需要考虑以下几种情况：
- 30 节点的右孩子可能存在，也可能不存在。
- 60 可能是树的根节点，也可能是子树的一部分。
- 如果 60 是根节点，旋转完成后需要更新根节点。
- 如果 60 是某个子树的根，可能是其父节点的左子树或右子树之一。
// 右单旋代码
private void rotateRight(TreeNode parent) {
// 获取 parent 的左子节点和左子节点的右子节点
TreeNode subL = parent.left;
TreeNode subLR = subL.right;
// 将 parent 的左子树指向 subL 的右子树
parent.left = subLR;
// 如果 subLR 不为空，更新其 parent 指针
if (subLR != null) {
subLR.parent = parent;
}
// 将 subL 变为新的根节点，并将 parent 设为 subL 的右子树
subL.right = parent;
// 记录当前 parent 的父节点
TreeNode parParent = parent.parent;
parent.parent = subL; // 更新 parent 的父节点为 subL
// 如果 parent 是树的根节点，则更新根节点为 subL
if (parent == root) {
root = subL; // 更新全局根节点
root.parent = null; // subL 的父节点设为 null
} else {
// 如果 parent 不是根节点，则调整其在父节点中的位置
if (parParent.left == parent) {
parParent.left = subL; // 如果 parent 是左子树，则更新左子树
} else {
parParent.right = subL; // 如果 parent 是右子树，则更新右子树
}
subL.parent = parParent; // 更新 subL 的父节点为 parParent
}
// 更新节点的平衡因子
subL.bf = 0; // 新根节点的平衡因子设为 0
parent.bf = 0; // 旧根节点的平衡因子设为 0
}
2.3.2 左单旋
左单旋的思路和实现可以参照右单旋的思路和实现：
// 左单旋
private void rotateLeft(AVLTreeNode parent) {
// 获取 parent 的右子节点和右子节点的左子节点
TreeNode subR = parent.right;
TreeNode subRL = subR.left;
// 1. 将 parent 的右子树指向 subRL
parent.right = subRL;
// 2. 如果 subRL 不为空，更新其父指针
if (subRL != null) {
subRL.parent = parent;
}
// 3. 将 subR 设为新的根节点，parent 作为 subR 的左子节点
subR.left = parent;
// 记录 parent 的父节点
TreeNode parentParent = parent.parent;
// 4. 更新 parent 的父节点为 subR
parent.parent = subR;
// 5. 如果 parent 是树的根节点，则更新根节点为 subR
if (parent == root) {
root = subR;
root.parent = null; // subR 的父节点设为 null
} else {
// 更新父节点的指针，调整子树位置
if (parent == parentParent.left) {
parentParent.left = subR; // 更新左子树
} else {
parentParent.right = subR; // 更新右子树
}
subR.parent = parentParent; // 更新 subR 的父指针
}
// 更新平衡因子
subR.bf = 0; // 新根节点的平衡因子设为 0
parent.bf = 0; // 旧根节点的平衡因子设为 0
}
2.3.3 左右双旋
将双旋变成单旋后再旋转，即：先对 30 进行左单旋，然后再对 90 进行右单旋，旋转完成后再考虑平衡因子的更新。
注意：左右单旋和右左单旋的单旋和纯左单旋和纯右单旋不同，纯左单旋和纯右单旋拿走的是低的树，而左右单旋和右左单旋拿走的是高的树
private void rotateLR(TreeNode parent) {
// 获取 parent 的左子节点和左子节点的右子节点
TreeNode subL = parent.left;
TreeNode subLR = subL.right;
// 记录 subLR 的平衡因子
int bf = subLR.bf;
// 先对 subL 进行左旋，调整 parent 的左子树
rotateLeft(parent.left);
// 再对 parent 进行右旋，完成 LR 旋转
rotateRight(parent);
// 根据 subLR 的平衡因子更新节点的平衡因子
if (bf == -1) {
// 情况 1: subLR 的平衡因子为 -1
subL.bf = 0; // subL 的平衡因子更新为 0
parent.bf = 1; // parent 的平衡因子更新为 1
subLR.bf = 0; // subLR 的平衡因子更新为 0
} else if (bf == 1) {
// 情况 2: subLR 的平衡因子为 1
subL.bf = -1; // subL 的平衡因子更新为 -1
parent.bf = 0; // parent 的平衡因子更新为 0
subLR.bf = 0; // subLR 的平衡因子更新为 0
}
}
2.3.4 右左双旋
将双旋变成单旋后再旋转，即：先对 90 进行右单旋，然后再对 60 进行左单旋，旋转完成后再考虑平衡因子的更新。
private void rotateRL(TreeNode parent) {
// 获取 parent 的右子节点和右子节点的左子节点
TreeNode subR = parent.right;
TreeNode subRL = subR.left;
// 记录 subRL 的平衡因子
int bf = subRL.bf;
// 先对 subR 进行右旋，调整 parent 的右子树
rotateRight(parent.right);
// 再对 parent 进行左旋，完成 RL 旋转
rotateLeft(parent);
// 根据 subRL 的平衡因子更新节点的平衡因子
if (bf == -1) {
// 情况 1: subRL 的平衡因子为 -1
subR.bf = 0; // subR 的平衡因子更新为 0
parent.bf = 1; // parent 的平衡因子更新为 1
subRL.bf = 0; // subRL 的平衡因子更新为 0
} else if (bf == 1) {
// 情况 2: subRL 的平衡因子为 1
subR.bf = -1; // subR 的平衡因子更新为 -1
parent.bf = 0; // parent 的平衡因子更新为 0
subRL.bf = 0; // subRL 的平衡因子更新为 0
}
}
2.3.5 总结
新节点插入后，如果以 pParent 为根的子树不平衡了，即 pParent 的平衡因子为 2 或 -2，此时需要进行相应的旋转调整：
当 pParent 的平衡因子为 2：这意味着 pParent 的右子树较高，此时设 pParent 的右子树根为 pSubR。
- 如果 pSubR 的平衡因子为 1，那么执行左单旋转。
- 如果 pSubR 的平衡因子为 -1，那么执行右左双旋转。
当 pParent 的平衡因子为 -2：这意味着 pParent 的左子树较高，此时设 pParent 的左子树根为 pSubL。
- 如果 pSubL 的平衡因子为 -1，执行右单旋转。
- 如果 pSubL 的平衡因子为 1，执行左右双旋转。
总结来说，当 pParent 与其较高子树节点的平衡因子同号时，执行单旋转；当异号时，执行双旋转。旋转完成后，原 pParent 为根的子树的高度降低，并已经恢复平衡，因此不需要再向上更新。
2.4 AVL 树的验证.
要验证一棵树是否为AVL树，可以分为两个步骤：
- 验证其为二叉搜索树：如果对树进行中序遍历得到的序列是有序的，那么可以确定该树是二叉搜索树。
- 验证其平衡性：每个节点的左右子树高度差的绝对值不得超过 1。如果节点中没有显式存储平衡因子，可以通过计算每个节点的子树高度来判断。
private boolean isBalance(TreeNode root) {
// 如果节点为空，返回平衡
if (root == null) {
return true;
}
// 计算左右子树的高度
int leftH = height(root.left);
int rightH = height(root.right);
// 检查平衡因子是否正确
if (rightH - leftH != root.bf) {
System.out.println(root.val + " 平衡因子异常！");
return false;
}
// 检查当前节点的平衡性以及左右子树的平衡性
return Math.abs(leftH - rightH) <= 1
&& isBalance(root.left)
&& isBalance(root.right);
}
2.5 AVL 树性能分析
AVL树是一种自平衡的二叉搜索树，它要求每个节点的左右子树高度差的绝对值不超过1，从而确保其查询操作具有高效的时间复杂度。然而，AVL树在进行结构修改时，如插入和删除操作，性能会显著下降。这是因为在插入时需要调整树的平衡，可能导致频繁的旋转，而在删除时，旋转调整甚至可能持续到根节点。因此，如果需要频繁高效的查询，AVL树是一个不错的选择；但如果需要频繁修改，此时 AVL 树并不适合。
三：红黑树
3.1 红黑树的概念
红黑树是一种自平衡的二叉搜索树，它在每个节点上增加了一个颜色属性，可以是红色或黑色。通过对从根节点到每个叶子节点路径上节点颜色的限制，红黑树确保没有任何一条路径的长度会超过其他路径长度的两倍，从而保持接近平衡。
3.2 红黑树的性质
- 最长路径的节点数最多是最短路径节点数的两倍。
- 每个节点要么是红色，要么是黑色。
- 根节点始终是黑色。
- 如果一个节点是红色，则其两个子节点必须是黑色，即不存在连续的红色节点，但是可以存在连续的黑色节点。
- 对于每个节点，从该节点到其所有后代叶子节点的简单路径上，必须包含相同数量的黑色节点。
- 每个叶子节点都是黑色，此处的叶子节点指的是空节点。
为何上述性质能够确保红黑树的最长路径中的节点数不会超过最短路径节点数的两倍？ 由于红黑树的定义确保了从根到叶子的每条路径上的黑色节点数量相同，因此最短路径和最长路径之间的黑色节点数量是相等的。而最长路径上的红色节点只能插入在黑色节点之间，且最多只能插入一个红色节点，这样意味着最长路径最多会比最短路径多出一倍的节点。因此，红黑树保持了接近平衡，确保了其最长路径的节点数不会超过最短路径节点数的两倍。
3.3 红黑树节点的定义
class RBTreeNode {
// 左子节点
RBTreeNode left = null;
// 右子节点
RBTreeNode right = null;
// 父节点
RBTreeNode parent = null;
// 节点的颜色，默认为红色
COLOR color = RED;
// 节点的值
int val;
public RBTreeNode(int val) {
this.val = val;
}
}
注意！节点默认颜色为红色，这样可以让黑红树在插入节点和维护平衡的时候更加高效
3.4 红黑树的插入
红黑树是在二叉搜索树的基础上增加了平衡性质的限制，因此红黑树的插入过程可以分为两个步骤：
- 按照二叉搜索树的规则插入新节点。
- 检查新节点插入后是否破坏了红黑树的性质。
由于新插入的节点默认为红色，如果其父节点的颜色为黑色，则不会违反红黑树的任何性质，因此无需调整。但当新插入节点的父节点为红色时，就违反了不能有连续的红色节点的性质。此时，需要根据不同情况进行调整。约定如下：cur 为当前节点，p 为父节点，g 为祖父节点，u 为叔叔节点。
- cur 为红，p 为红，g 为黑，u 存在且为红
当当前节点 cur 和父节点 p 均为红色时，违反了红黑树的性质三。在这种情况下，不能直接将父节点 p 改为黑色，因为这样可能会影响树的其他性质，因为你这样会直接导致黑色节点的个数加一，但是你要记住，所有路径上的黑色节点的个数要一样，你这样平白无故加一肯定是不行的。
解决方案：将父节点 p 和叔叔节点 u 的颜色改为黑色，同时将祖父节点 g 的颜色改为红色。然后，将祖父节点 g 视为新的当前节点 cur，继续向上调整树的结构，以维护红黑树的性质，这样就可以保证这条路径上的红色节点个数和黑色节点个数的相对数量不变。
- cur 为红，p 为红，g 为黑，u 不存在或者 u 为黑
- 如果父节点 p 是祖父节点 g 的左孩子，并且当前节点 cur 是 p 的左孩子，则进行右单旋转
- 如果父节点 p 是祖父节点 g 的右孩子，并且当前节点 cur 是 p 的右孩子，则进行左单旋转。
在旋转之后，将父节点 p 和祖父节点 g 的颜色进行调整：将 p 的颜色改为黑色，将 g 的颜色改为红色。
- cur 为红，p 为红，g 为黑，u 不存在或者 u 为黑
- 如果父节点 p 是祖父节点 g 的左孩子，并且当前节点 cur 是 p 的右孩子，则对 p 进行左单旋转。
- 如果父节点 p 是祖父节点 g 的右孩子，并且当前节点 cur 是 p 的左孩子，则对 p 进行右单旋转。
public boolean insert(int val) {
// 插入逻辑的代码省略
// 新节点插入后，如果父节点的颜色是红色，则一定违反了红黑树的性质三（不能有两个连续的红色节点）
while (parent != null && parent.color == COLOR.RED) {
RBTreeNode grandFather = parent.parent; // 获取祖父节点
if (parent == grandFather.left) { // 情况一：父节点是祖父节点的左孩子
RBTreeNode uncle = grandFather.right; // 获取叔叔节点
if (uncle != null && uncle.color == COLOR.RED) { // 叔叔节点存在且为红色
// 情况一处理：将叔叔和父节点改为黑色，祖父节点改为红色
parent.color = COLOR.BLACK;
uncle.color = COLOR.BLACK;
grandFather.color = COLOR.RED;
// 更新当前节点为祖父节点，继续往上调整
cur = grandFather;
parent = cur.parent;
} else {
// 如果叔叔节点不存在或为黑色，则进入情况二或情况三
if (cur == parent.right) { // 情况三：当前节点是父节点的右孩子
// 针对父节点进行左单旋转，将当前节点调整为父节点
rotateLeft(parent);
RBTreeNode temp = parent; // 临时存储父节点
parent = cur; // 当前节点变为父节点
cur = temp; // 继续处理之前的父节点
}
// 情况二：当前节点是父节点的左孩子，进行右单旋转
rotateRight(grandFather);
parent.color = COLOR.BLACK; // 将父节点颜色设为黑色
grandFather.color = COLOR.RED; // 将祖父节点颜色设为红色
}
} else { // 情况一的反情况：父节点是祖父节点的右孩子
// 获取叔叔节点
RBTreeNode uncle = grandFather.left;
if (uncle != null && uncle.color == COLOR.RED) { // 叔叔节点存在且为红色
// 处理情況一
parent.color = COLOR.BLACK;
uncle.color = COLOR.BLACK;
grandFather.color = COLOR.RED;
// 更新当前节点为祖父节点，继续往上调整
cur = grandFather;
parent = cur.parent;
} else {
// 如果叔叔节点不存在或为黑色，则进入情况二或情况三
if (cur == parent.left) { // 情况三：当前节点是父节点的左孩子
// 针对父节点进行右单旋转，将当前节点调整为父节点
rotateRight(parent);
RBTreeNode temp = parent; // 临时存储父节点
parent = cur; // 当前节点变为父节点
cur = temp; // 继续处理之前的父节点
}
// 情况二：当前节点是父节点的右孩子，进行左单旋转
rotateLeft(grandFather);
parent.color = COLOR.BLACK; // 将父节点颜色设为黑色
grandFather.color = COLOR.RED; // 将祖父节点颜色设为红色
}
}
}
// 最后，确保根节点始终是黑色，以维持红黑树的性质一
root.color = COLOR.BLACK;
return true;
}
3.5 红黑树验证
红黑树的检测分为两步：
- 检测其是否满足二叉搜索树，即中序遍历是否为有序序列
- 检测其是否满足红黑树的性质
// 中序遍历
public void inorder(RBTreeNode root) {
if (root == null) {
return;
}
inorder(root.left);
System.out.print(root.val + " ");
inorder(root.right);
}
// 检测是否满足红黑树的性质
public boolean isValidRBTree() {
// 空树也是红黑树
if (root == null) {
return true;
}
// 检查根节点颜色是否为黑色
if (root.color != COLOR.BLACK) {
System.out.println("违反了性质2：根节点不是黑色");
return false;
}
// 获取从根节点到叶子节点路径中的黑色节点数量
int blackCount = 0;
RBTreeNode cur = root;
while (cur != null) {
if (cur.color == COLOR.BLACK) {
blackCount++;
}
cur = cur.left; // 遍历左子树
}
// 递归检查红黑树的有效性
return _isValidRBtree(root, 0, blackCount);
}
private boolean _isValidRBtree(RBTreeNode root, int pathCount, int blackCount) {
if (root == null) {
return true; // 空节点视为合法
}
// 统计当前路径中黑色节点的数量
if (root.color == COLOR.BLACK) {
pathCount++;
}
// 验证性质4：检查父节点是红色且当前节点也是红色
RBTreeNode parent = root.parent;
if (parent != null && parent.color == COLOR.RED && root.color == COLOR.RED) {
System.out.println("违反了性质4：有连在一起的红色节点");
return false;
}
// 检查是否为叶子节点
if (root.left == null && root.right == null) {
// 验证路径中黑色节点的总数是否一致
if (pathCount != blackCount) {
System.out.println("违反了性质5：路径中黑色节点数量不一致");
return false;
}
}
// 递归检查左右子树
return _isValidRBtree(root.left, pathCount, blackCount) &&
_isValidRBtree(root.right, pathCount, blackCount);
}
3.6 AVL 树和红黑树的比较
对于 AVL 树和红黑树的删除代码这里不做涉及，下面对这两种树进行比较：红黑树和 AVL 树都是高效的平衡二叉树，增、删、改和查的时间复杂度均为 O(log n)。与 AVL 树不同，红黑树并不追求绝对平衡，而是确保最长路径不超过最短路径的两倍。这种相对宽松的平衡策略降低了插入和旋转的次数，因此在频繁进行增删操作的场景中，红黑树的性能通常优于 AVL 树。此外，红黑树的实现相对简单，因此在实际应用中更为常见，在 Java 集合框架中的 TreeMap、TreeSet 底层使用的就是红黑树。