二叉搜索树的学习 我们在这篇文章中学习了二叉搜索树，知道了当插入的元素序列趋于有序时，将会导致 其效率变得十分底下。
今天，我们就来学习AVL树。
目录
AVL树的相关概念
AVL树的相关操作
AVL树的插入
右旋
左旋
左右双旋
右左双旋
证明一棵二叉树是AVL树
AVL树的性能分析
AVL树的相关概念
二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率低下。因此，两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年 发明了一种解决上述问题的方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过 1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。
一棵AVL树要么是空树，要么是具有以下性质的二叉搜索树： 它的左右子树都是AVL树 左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)。如下图所示：
如果一棵二叉搜索树是高度平衡的，它就是AVL树。如果它有n个结点，其高度可保持在 log n，搜索时间复杂度O(log n)。 因此AVL树也叫平衡的二叉搜索树。
平衡因子的概念：一棵AVL树的右子树高度 减去 左子树的高度之差的结果。
AVL树的相关操作
首先，得定义一个树节点：
class TreeNode {
public int val;
// 根结点的右子树高度-左子树的高度
public int balanceFactor; // 平衡因子
public TreeNode parent; // 父亲
public TreeNode left; // 左子树
public TreeNode right; // 右子树
public TreeNode(int val) {
this.val = val;
}
}public TreeNode root;注意：
1、这里采用的是孩子双亲表示法；
2、一个新插入的节点，其平衡因子默认是0（因为其左子树和右子树皆为null，高度之差为0）。
AVL树的插入
思路：首先，得和二叉搜索树一样，找到合适的位置插入节点。
代码实现：
public boolean insert(int val) {
// 如果root为null，就直接插入元素即可
if (root == null) {
root = new TreeNode(val);
return true;
}
// 开始寻找要插入的元素位置
TreeNode cur = root;
TreeNode parent = null;
while (cur != null) {
parent = cur;
if (cur.val < val) {
cur = cur.right;
} else if (cur.val > val) {
cur = cur.left;
} else {
return false; // 不能插入两个相同的元素
}
}
// 插入元素
TreeNode node = new TreeNode(val);
if (parent.val > val) {
parent.left = node;
} else {
parent.right = node;
}
node.parent = parent;当插入成功之后，就得开始检查整棵树的平衡因子是否符合要求。但是整棵树的平衡因子都得检查一遍吗？不是的，我们在哪里插入的节点，就从该位置开始向上调整来修改平衡因子。如果平衡因子修改后符合我们的要求，则继续往上调整，直至parent为null即可，如果不符合要求，就得开始处理这种情况。处理完成之后肯定是符合我们的要求的，因此便可以不再进行检查了。
思路：从插入节点的位置开始向上调整：看插入节点的位置是处于其parent的哪边：如果是右边，就让平衡因子++，如果是左边就让平衡因子--。接着再进行判断：如果parent的平衡因子的绝对值大于1的话，就得进行调整；如果等于1的话，就继续往上判断；如果等于0的话，就说明已经平衡了，不需要再进行判断了。
代码实现：
// 判断是否是满足AVL树的条件：高度平衡（检查平衡因子）
cur = node;
while (parent != null) {
if (parent.left == cur) {
// 左树--
parent.balanceFactor--;
} else {
// 右树++
parent.balanceFactor++;
}
// 检查平衡因子的值
if (parent.balanceFactor == 0) {
// 说明已经平衡了
break;
} else if (parent.balanceFactor == 1 || parent.balanceFactor == -1) {
// 还得继续判断
cur = parent;
parent = cur.parent;
} else {
// 走到这里就说明平衡因子为2或者-2,是要进行修改的
if (parent.balanceFactor == 2) { // 右树高-->降低右树的高度
if (cur.balanceFactor == 1) {
// 左旋
rotateLeft(parent);
} else {
// 先右旋，再左旋（右左双旋）
ratateRL(parent);
}
} else { // 左树高-->降低左树的高度
if (cur.balanceFactor == 1) {
// 先左旋，再右旋（左右双旋）
ratateLR(parent);
} else {
// 右旋
rotateRight(parent);
}
}
// 调整完就说明已经是平衡的状态了，可以不用继续进行调整了
break;
}
}
return true;注意：
1、平衡因子是右子树的高度减去左子树的高度之差。因此，插入的节点位置为parent的右子树时，parent的平衡因子就得++；反之，就得--。
2、旋转的条件判断：
右旋
1、右旋的条件：全部是左树高（parent的左树高，cur的左树高），因此往右旋，以降低左树的高度，来达到平衡。
这里之所以把 cur.right 放到 parent 的左边，是因为 cur.right 肯定小于parent，且其位置被parent占有，因此只能往这里放。
代码实现：
private void rotateRight(TreeNode parent) {
TreeNode subL = parent.left;
TreeNode subLR = subL.right;
TreeNode parentP = parent.parent;
// 修改四个指针的指向
parent.parent = subL;
parent.left = subLR;
// 判断是否为null
if (subLR != null) {
subLR.parent = parent;
}
subL.right = parent;
// 修改高树的指向和本级新的根结点指向
if (parent == root) {
root = subL;
subL.parent = null;
} else {
subL.parent = parentP; // 先得保存下来
if (parentP.left == parent) {
parentP.left = subL;
} else {
parentP.right = subL;
}
}
// 修改平衡因子
subL.balanceFactor = 0;
parent.balanceFactor = 0;
}左旋
2、左旋的条件：全部是右树高（parent的右树高，cur的右树高），因此往左旋，以降低右树的高度，来达到平衡。
代码实现：
private void rotateRight(TreeNode parent) {
TreeNode subL = parent.left;
TreeNode subLR = subL.right;
TreeNode parentP = parent.parent;
// 修改四个指针的指向
parent.parent = subL;
parent.left = subLR;
// 判断是否为null
if (subLR != null) {
subLR.parent = parent;
}
subL.right = parent;
// 修改高树的指向和本级新的根结点指向
if (parent == root) {
root = subL;
subL.parent = null;
} else {
subL.parent = parentP; // 先得保存下来
if (parentP.left == parent) {
parentP.left = subL;
} else {
parentP.right = subL;
}
}
// 修改平衡因子
subL.balanceFactor = 0;
parent.balanceFactor = 0;
}左右双旋
3、左右双旋的条件：先左旋，再右旋（parent的左树高，cur的右树高） ：先左旋cur，再右旋parent，降低左树高度，再降低右树高度，达到平衡。
上面分别是 cur.right无子树、有左子树无右子树、有右子树无左子树的三种情况，情况不同对应的平衡因子处理的方式就不相同。 并且当cur.right 处于无子树的时候，经过左旋和右旋代码的处理，平衡因子已经处于一种正常的状态。
代码实现：
private void ratateLR(TreeNode parent) {
TreeNode subL = parent.left;
TreeNode subLR = subL.right;
// 通过subLR的平衡因子来判断节点的位置，从而确定调整后的平衡因子
int bf = subLR.balanceFactor;
// 先左旋parent的孩子节点
rotateLeft(parent.left);
// 再右旋parent节点
rotateRight(parent);
// 调整平衡因子、
// 前面的旋转调整只满足一种情况：
// 即平衡因子全为0的情况
if(bf == -1) {
subL.balanceFactor = 0;
subLR.balanceFactor = 0;
parent.balanceFactor = 1;
}else if (bf == 1){
subL.balanceFactor = -1;
subLR.balanceFactor = 0;
parent.balanceFactor = 0;
}
}右左双旋
4、右左双旋的条件： 先右旋，再左旋（parent的右树高，cur的左树高）：先右旋cur，再左旋parent，降低右树的高度，再降低左树的高度，达到平衡。
上面分别是 cur.left无子树、有左子树无右子树、有右子树无左子树的三种情况，情况不同对应的平衡因子处理的方式就不相同。 并且当cur.left 处于无子树的时候，经过左旋和右旋代码的处理，平衡因子已经处于一种正常的状态。
代码实现：
private void ratateRL(TreeNode parent) {
TreeNode subR = parent.right;
TreeNode subRL= subR.left;
// 通过subRL的平衡因子来判断节点的位置，从而确定调整后的平衡因子
int bf = subRL.balanceFactor;
// 先右旋parent的孩子节点
rotateRight(parent.right);
// 再左旋parent节点
rotateLeft(parent);
// 调整平衡因子、
// 前面的旋转调整只满足一种情况：
// 即平衡因子全为0的情况
if(bf == 1) {
parent.balanceFactor = -1;
subR.balanceFactor = 0;
subRL.balanceFactor = 0;
}else if(bf == -1) {
parent.balanceFactor = 0;
subR.balanceFactor = 1;
subRL.balanceFactor = 0;
}
}通过上面的代码，一棵AVL树就被构建出来了。但是还得去证明这棵树是正确的AVL树。因为AVL树是一棵高度平衡的二叉搜索树，所以我们只要能同时证明是二叉搜索树，并且是一棵二叉平衡树即可。
证明一棵二叉树是AVL树
1、证明是一棵二叉搜索树：
思路：只需要中序遍历这棵树即可。如果中序遍历的结果是有序的，那么就是一棵二叉搜索树。
代码实现：
public void inorder(TreeNode root) {
if (root == null) {
return;
}
inorder(root.left);
System.out.print(root.val+" ");
inorder(root.right);
}2、证明是一棵二叉平衡树：
思路：只要证明每棵树都是二叉平衡树 && 计算出来的平衡因子和每个节点对应的平衡因子相同即可。 证明每棵树都是二叉平衡树，就是先证明根结点是，再去递归证明左子树和右子树。在这里免不了去求树的高度。
代码实现：
public boolean isBalanceTree(TreeNode root) {
if (root == null) {
return true;
}
// 判断根结点是不是一棵二叉平衡树 + 其左右子树是不是一棵二叉平衡树
// 二叉平衡树：左右子树的高度差 <= 1
int leftHigh = TreeHigh(root.left);
int rightHigh = TreeHigh(root.right);
// 检查平衡因子
if(rightHigh - leftHigh != root.balanceFactor) {
System.out.println(root.val+" 平衡因子异常！");
//return false; // 可有可无
}
if (Math.abs(rightHigh-leftHigh) > 1) {
return false;
}
// 再判断左右子树是不是二叉平衡树
return isBalanceTree(root.left) && isBalanceTree(root.right);
}
// 求树的高度：根节点（1）+Math.max(左子树，右子树)
private int TreeHigh(TreeNode root) {
if (root == null) {
return 0;
}
if (root.left == null && root.right == null) {
return 1;
}
return 1 + Math.max(TreeHigh(root.left), TreeHigh(root.right));
}验证代码写出来之后，就可以开始去测试了。
思路：就是看是否同时满足上面两个条件即可。
代码实现：
public class Test {
public static void main(String[] args) {
AVLTree avlTree = new AVLTree();
int[] array = {16, 3, 7, 11, 9, 26, 18, 14, 15}; // 常见场景
//int[] array = {4, 2, 6, 1, 3, 5, 15, 7, 16, 14}; // 特殊场景
// 插入元素
for (int i = 0; i < array.length; i++) {
avlTree.insert(array[i]);
}
// 中序遍历
avlTree.inorder(avlTree.root);
System.out.println();
// 判断是否为二叉平衡树
System.out.println(avlTree.isBalanceTree(avlTree.root));
}
}
AVL树的删除步骤：
1、找到要删除的节点
2、和删除二叉搜索树一样，分为四种情况（具体可见上面的链接）
3、删除成功之后，就得要更新平衡因子（左树降低，平衡因子就++；反之，则--）。
注意：删除之后的调整是向上调整，可能会调整到根节点。
AVL树的性能分析
AVL树是一棵绝对平衡的二叉搜索树，其要求每个节点的左右子树高度差的绝对值都不超过1，这样可以保证查询时高效的时间复杂度，即log N。
但是如果要对AVL树做一些结构修改的操作，性能非常低下，比如：插入时要维护其绝对平衡，旋转的次数比较多，更差的是在删除时，有可能一直要让旋转持续到根的位置。
因此：如果需要一种查询高效且有序的数据结构，而且数据的个数为静态的(即不会改变)，可以考虑AVL树，但一个结构经常修改，就不太适合。因此就有了红黑树，我们下一期再学习。
好啦！本期 数据结构之AVL树 的学习之旅就到此结束啦！我们下一期再一起学习吧！
