数据结构之AVL树

找往期文章包括但不限于本期文章中不懂的知识点：

个人主页：我要学编程(ಥ_ಥ)-CSDN博客

所属专栏：数据结构（Java版）

二叉搜索树的学习我们在这篇文章中学习了二叉搜索树，知道了当插入的元素序列趋于有序时，将会导致其效率变得十分底下。

今天，我们就来学习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;// 判断是否为nullif (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;// 判断是否为nullif (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;}// 判断根结点是不是一棵二叉平衡树 + 其左右子树是不是一棵二叉平衡树// 二叉平衡树：左右子树的高度差 <= 1int 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、删除成功之后，就得要更新平衡因子（左树降低，平衡因子就++；反之，则--）。

注意：删除之后的调整是向上调整，可能会调整到根节点。