数据结构之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.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) { 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树 的学习之旅就到此结束啦！我们下一期再一起学习吧！