一、什么是AVL树
在了解什么是AVL树之前，我们先回顾二叉搜索树的概念
二叉搜索树（二叉排序树），它或是一棵空树，或具有以下性质：
1. 若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
2. 若它的右子树不为空，则右子树上所有节点的值都大于根节点
3. 它的左右子树也分别是二叉搜索树
根据二叉搜索树的性质，我们可以发现：
1. 二叉搜索树中最左侧的节点是树中最小的节点，最右侧的节点是树中最大的节点
2. 若采用中序遍历二叉搜索树，则可得到一个有序的序列
二叉搜索树最主要的作用就是用于进行查询：
当二叉搜索树是一颗完全二叉树时：
其查询的平均查找次数为: 
而当二叉搜索树是一颗单支树时：
其平均查找次数为： 
由此可见二叉搜索树的平均查找次数与二叉搜索树的深度成正相关，即深度越深，比较查找的次数越多。而当其是单支树时，二叉搜索树的性能就降低了，此时，能否对其进行改进，使其无论怎样插入，都能够使二叉搜索树的性能最佳？
AVL树的出现解决了这个问题。
ALV树（也就是平衡二叉查找树，简称平衡二叉树）或是一颗空树，或具有以下性质：
1. 它的左右子树高度之差（简称平衡因子）的绝对值不超过1
2. 它的左右子树都是AVL树
由AVL树的性质，我们可以发现：
1. 每当向AVL树中插入新的节点时，都要保证每个节点的左右子树高度差（平衡因子）的绝对值不超过1（当超过时需要对树中的节点进行调整，即降低树的高度，从而减少平均搜索长度）
2. 若一颗AVL树有n个节点，它的高度能够保持在 
，因此，其搜索的时间复杂度为O( 
)
二、AVL树的实现
AVL树的节点
在这里，我们通过一个内部类来实现AVL树节点的定义，通过维护节点的左孩子、右孩子和父亲节点来实现AVL树，同时定义一个平衡因子bf，通过平衡因子来判断是否需要调整树中节点。同时，我们需要定义根节点：
public class AVLTree { static class TreeNode{ public int val;//节点的值 public int bf;//平衡因子 public TreeNode left;//左孩子 public TreeNode right;//右孩子 public TreeNode parent;//父亲节点 public TreeNode(int val){ this.val = val; } } public TreeNode root;//根节点 }
当前节点的平衡因子 = 右子树的高度 - 左子树的高度
AVL树的插入
AVL树就是在二叉搜索树的基础上引入了平衡因子，因此，我们可以将AVL树的插入过程分为两步：
1. 插入新的节点
2. 调整节点的平衡因子
现在我们对新的节点进行插入：
1. 当AVL树为空时，插入的节点即为根节点
2. AVL树不为空，则寻找新节点的插入位置
如何寻找新节点的插入位置？
若新节点node的值val > 当前节点cur的值val，则在cur的右子树寻找插入位置；
若node.val < cur.val，则在cur的左子树寻找插入位置；
若node.val = cur.val，则AVL树中已有该节点，插入失败，直接返回false
在找到插入位置后，我们需要知道其父亲节点，从而进行插入，因此在查找过程中，我们可以定义当前节点cur的父亲节点parent，用于最后进行插入新节点：
//节点的插入 public boolean insert(int val){ TreeNode node = new TreeNode(val); //若根节点为空，则直接将插入为根节点 if(root == null){ root = node; return true; } //根节点不为空，查找其插入位置 TreeNode parent = null; TreeNode cur = root; while (cur != null){ if(cur.val < val){ parent = cur; cur = cur.right; }else if(cur.val > val){ parent = cur; cur = cur.left; }else{ return false;//若已有该节点，则插入失败，直接返回false } } //将节点插入 node.parent = parent; cur = node; }
AVL树的旋转
在插入新的节点之后，此时AVL树中某些节点的平衡因子会发生改变，因此我们需要对平衡因子进行修改，而在插入新节点后，节点的平衡因子的绝对值可能超过1，此时我们需要对节点进行调整
我们首先对平衡因子进行修改：
在插入新节点时，我们定义了其父亲节点parent，由于在这里平衡因子 = 右子树的高度 - 左子树的高度
因此，若新插入的节点在parent的左子树，则其平衡因子 -1；而若新插入的节点在parent的右子树，则平衡因子 +1
在修改完当前平衡因子后，我们需要对当前平衡因子进行检查，判断其是否符合条件：
1. 若修改后的平衡因子 = 0，则表明未修改时parent的平衡因子bf = 1 或 -1，在插入后被调整成为0，此时子树parent已经平衡了，且其高度并未发生改变，不会影响上面节点的平衡因子，因此不用再继续向上判断
2. 若修改后的平衡因子 = 1 或 -1，则表明未修改时parent的平衡因子bf = 0，在插入之后被调整成 1 或 -1，此时子树parent的高度增加，上面节点的平衡因子也会被影响，因此需要继续向上更新平衡因子
3. 若修改后的平衡因子的绝对值 > 1，此时则需要对AVL树的节点进行调整，重新使其平衡
在这里，我们通过旋转来调整节点的平衡因子，AVL树的旋转分为四种情况：
右单旋
（1）新节点插入较高左子树的左侧->右单旋
当新节点插入较高左子树的左侧时：
此时 patent.bf = -2, cur.bf = -1，要想办法降低左子树的高度，因此对其进行调整：
将对于以parent 为根的子树：
将cur作为其根；parent作为cur的右子树；cur原右子树（若有的话）作为parent的左子树，
这样重新调整后，cur和parent的平衡因子都被调整为0，此时以cur为根的子树已经平衡
因此，我们调整的步骤为：
我们设parent的左孩子cur为subL，cur的右孩子为subLR（因为要考虑cur的右孩子不存在的情况）
1. 将parent的左孩子更新为subLR，将subLR的父亲节点更新为parent
注：此时要考虑subLR为空的情况，若subLR为空，则不需要更新
2. 将subL的右孩子更新为parent，将parent的父亲节点更新为subL
注：在更新parent的父亲节点时，我们首先要将parent的父亲节点pParent保存起来，因为我们需要将subL的父亲节点更新为parent的父亲节点
3. 更新subL的父亲节点，
若parent原为根节点，此时需要将根节点更新为subL，同时将subL的父亲节点更新为null；
若parent原不为根节点，则更新subL的父亲节点为pParent，同时需要更新pParent的孩子节点，此时需要判断parent为pParent的左孩子还是右孩子，并更新
右单旋代码：
//右单旋 private void rotateRight(TreeNode parent){ TreeNode subL = parent.left; TreeNode subLR = subL.right; parent.left = subLR; if(subLR != null){//只有当subLR不为空时，才能修改其父亲节点 subLR.parent = parent; } subL.right = parent; //在修改parent的父亲节点时，必须先记录其父亲节点，以便修改subL的父亲节点 TreeNode pParent = parent.parent; parent.parent = subL; //判断subL是否被修改为根节点 if(parent == root){ root = subL; root.parent = null; }else { subL.parent = pParent; //判断是左子树还是右子树 if(pParent.left == parent){ pParent.left = subL; }else { parent.right = subL; } } //修改平衡因子 subL.bf = 0; parent.bf = 0; }
左单旋
新节点插入较高右子树的右侧->左单旋
左单旋与右单旋类似：
当新的节点插入到较高右子树的右侧时：
此时 parent.bf = 2, cur.bf = 1，要想办法降低右子树的高度，对以parent为根的子树进行调整：
设parent的右孩子cur为subR，subR的左孩子为subRL（要考虑subR的左孩子为空的情况）
1. 将parent的右孩子更新为subRL，将subRL的父亲节点更新为parent（若subRL不为空）
2. 将subR的左孩子更新为parent，保存parent的父亲节点pParent，再更新parent的父亲节点为subR
3. 更新subR的父亲节点，若parent原为根节点，则更新根节点为subR，并将其父亲节点更新为null；若parent原不为根节点，则更新subR的父亲节点为pParent，判断parent原为pParent的左孩子还是右孩子，并将subR更新为pParent的孩子节点
左单旋代码：
//左单旋 private void rotateLeft(TreeNode parent){ TreeNode subR = parent.right; TreeNode subRL = subR.left; parent.right = subRL; if(subRL != null){//只有当subRL不为空时，才能修改其父亲节点 subRL.parent = parent; } subR.left = parent; //在修改parent父亲节点前将其进行记录，以便后续修改subR的父亲节点 TreeNode pParent = parent.parent; parent.parent = subR; //判断subR是否被修改为根节点 if(parent == root){ root = subR; root.parent = null; }else { //判断是其左子树还是右子树 if(pParent.left == parent){ pParent.left = subR; }else{ pParent.right = subR; } subR.parent = pParent; } //修改平衡因子 subR.bf = 0; parent.bf = 0; }
左右双旋
新节点插入较高左子树的右侧->左右双旋（先左单旋再右单旋）
当新的节点插入较高左子树的右侧时：
此时 parent.bf = -2, cur.bf = 1，此时对于以parent为根的子树，无论是进行右单旋，还是进行左单旋，都不能使其平衡。因此，此时不能只进行一次旋转，而需要进行两次旋转：
首先，我们需要对以cur为根的子树进行一次左单旋：
然后再对以parent为根的子树进行一次右单旋：
此时调整后的子树达到平衡状态，由于进行的左单旋和右单旋会更改其中节点的平衡因子，因此我们需要对被修改的平衡因子进行重新调整：
平衡因子被修改的节点有：parent、parent的左孩子subL、subL的右孩子subLR
它们的平衡因子都被修改为0，
然而经过两次旋转后，它们的平衡因子并不都为0
通过观察我们发现，当subLR的平衡因子原为-1时，经过调整后，parent的平衡更新为1
当subLR的平衡因子原为1时，经过调整后，subL的平衡因子被更新为-1：
当subLR的平衡因子原为0时，经过调整后，parent、subL和subLR的平衡因子都为0：
因此，我们根据subLR原平衡因子来调整旋转两次之后的平衡因子
为什么subLR的平衡因子不同，两次旋转后的平衡因子也不同呢？
当subLR的平衡因子为-1时，经过一次左单旋，subRL的左子树变为subR的右子树，由于subR的平衡因子为1，经过这次左旋后，其右子树的高度减一（少了subRL），此时subR的平衡因子变为0，且subRL变为subR的父亲节点。
当subLR变为subR的父亲节点时，其平衡因子变为 -2 ，这是因为subRL的原平衡因子为-1，经过一次左旋后，其左子树高度增加1（增加了subR），右子树高度不变，因此平衡因子变为 -2。
而parent的平衡因子不变，仍是 -2，这是因为在经过一次左单旋后，其右子树高度不变，虽其左孩子变为了subRL，但其高度未改变，因此parent的平衡因子不变
其过程更新过程如下图：
此时，我们假设subLR的左子树高度为m，由于其平衡因子为-2，则subLR的右子树高度为m-2，而parent的左子树高度为m+1，parent的右子树高度为m-1
当进行一次右旋后，由于subR的左右子树不变，因此其平衡因子仍为0
而parent变为subLR的右子树，且其左子树变为subLR的右子树，parent的右子树高度未改变，任为m - 1，而parent的左子树变为subLR的右子树，因此其高度变为m-2，则parent子树的高度为m-1，平衡因子变为 1
subLR的左子树为改变，高度任为m，而右子树变为以parent为根的子树，parent子树的高度为m-1，再加上parent，则为m，因此subLR的平衡因子变为0
当subLR的平衡因子为1和为0时也是同样的分析过程，大家可自行进行分析，这里就不再进行分析了
左右双旋代码：
//左右双旋 private void rotateLR(TreeNode parent){ TreeNode subL = parent.left; TreeNode subLR = subL.right; //记录subLR平衡因子 int bf = subLR.bf; rotateLeft(parent.left);//先左旋 rotateRight(parent);//再右旋 //修改平衡因子 if(bf == -1){ parent.bf = 1; }else if(bf == 1){ subL.bf = -1; } }
右左双旋
新节点插入较高右子树的左侧->右左双旋（先右单旋再左单旋）
右左双旋与左右双旋的情况类似
当新节点插入较高右子树的左侧时：
此时 parent.bf = 2, cur.bf = -1，仍要进行两次旋转，才能将以parent为根的子树调整为平衡的子树
此时要先对其进行右旋：
再对其进行左旋：
最后，我们再根据原subRL的平衡因子对平衡因子对其修改：
当subRL原平衡因子为1时，更新后的parent的平衡因子为-1
当subRL原平衡因子为-1时，更新后的subR的平衡因子为1
当subRL原平衡因子为0时，更新后parent、subR和subRL的平衡因子都为0
右左双旋的代码为：
//右左双旋 private void rotateRL(TreeNode parent){ TreeNode subR = parent.right; TreeNode subRL = subR.left; //记录subRL的平衡因子 int bf = subRL.bf; rotateRight(subR);//先右旋 rotateLeft(parent);//再左旋 //修改平衡因子 if(bf == 1){ parent.bf = -1; }else if(bf == -1){ subR.bf = 1; } }
由上述四种旋转过程可知：经过旋转后，都能使节点的平衡因子到达平衡，此时无需再向上调整，因此修改平衡因子的代码为：
//修改平衡因子 //平衡因子 = 右子树高度 - 左子树高度 while (parent != null){ //判断cur是parent的左还是右，从而决定其平衡因子是++还是-- if(cur == parent.right){ parent.bf++; }else { parent.bf--; } //检查当前平衡因子 判断是否符合条件（-1 0 1） if(parent.bf == 0){ //已经平衡 break; }else if(parent.bf == 1 || parent.bf == -1){ //需要继续向上判断是否需要修改平衡因子 cur = parent; parent = cur.parent; }else { //不平衡，需要进行旋转，使其平衡 if(parent.bf == 2){//右树高，需要左旋，从而降低右树高度 if(cur.bf == 1){ //直接左旋 rotateLeft(parent); }else { //右左双旋 rotateRL(parent); } }else {//左树高，需要右旋，从而降低左树高度 if(cur.bf == -1){ //直接右旋 rotateRight(parent); }else { //左右双旋 rotateLR(parent); } } //旋转之后，平衡 break; } }
AVL树的验证
在我们插入节点后，如何验证我们创建出的树是否是AVL树？
AVL树是高度平衡的二叉搜索树，其平衡因子的绝对值不超过1，能否通过节点的平衡因子来验证？
不能通过平衡因子来验证，因为平衡因子是我们通过计算得出的，若我们在计算时出现错误，那我们通过平衡因子验证的结果也是错误的（例如在左右双旋时，未在最后修改平衡因子，则此时计算的平衡因子不完全正确）
那么我们应该如何进行验证呢？
首先，AVL树也是二叉搜索树，二叉搜索树中序遍历的结果是有序的，因此我们可以通过中序遍历来验证
public void inorder(TreeNode root) { if(root == null) return; inorder(root.left); System.out.print(root.val+" "); inorder(root.right); }
其次，AVL树节点的平衡因子绝对值不超过1，即左右子树的高度差不超过1，我们可以通过计算左右子树的高度差来判断树是否是高度平衡的，同时，通过比较计算出的高度差和平衡因子，我们也可以验证当前节点的平衡因子是否正确
private int height(TreeNode root) {//计算子树高度 if(root == null) return 0; int leftH = height(root.left); int rightH = height(root.right); return leftH > rightH ? leftH+1 : rightH+1; } public boolean isBalanced(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; } //判断左右子树高度差绝对值是否不超过1 return Math.abs(leftH-rightH) <= 1 && isBalanced(root.left) && isBalanced(root.right); }
完整代码：
public class AVLTree { static class TreeNode{ public int val;//节点的值 public int bf;//平衡因子 public TreeNode left;//左孩子 public TreeNode right;//右孩子 public TreeNode parent;//父亲节点 public TreeNode(int val){ this.val = val; } } public TreeNode root;//根节点 //节点的插入 public boolean insert(int val) { TreeNode node = new TreeNode(val); //若根节点为空，则直接将插入为根节点 if (root == null) { root = node; return true; } //根节点不为空，查找其插入位置 TreeNode parent = null; TreeNode cur = root; while (cur != null) { if (cur.val < val) { parent = cur; cur = cur.right; } else if (cur.val > val) { parent = cur; cur = cur.left; } else { return false;//若已有该节点，则插入失败，直接返回false } } //将节点插入 node.parent = parent; cur = node; //修改平衡因子 //平衡因子 = 右子树高度 - 左子树高度 while (parent != null){ //判断cur是parent的左还是右，从而决定其平衡因子是++还是-- if(cur == parent.right){ parent.bf++; }else { parent.bf--; } //检查当前平衡因子 判断是否符合条件（-1 0 1） if(parent.bf == 0){ //已经平衡 break; }else if(parent.bf == 1 || parent.bf == -1){ //需要继续向上判断是否需要修改平衡因子 cur = parent; parent = cur.parent; }else { //不平衡，需要进行旋转，使其平衡 if(parent.bf == 2){//右树高，需要左旋，从而降低右树高度 if(cur.bf == 1){ //直接左旋 rotateLeft(parent); }else { //先右旋，再左旋 rotateRL(parent); } }else {//左树高，需要右旋，从而降低左树高度 if(cur.bf == -1){ //直接右旋 rotateRight(parent); }else { //先左选，再右旋 rotateLR(parent); } } //经过旋转之后，就平衡 break; } } return true; } //左单旋 private void rotateLeft(TreeNode parent){ TreeNode subR = parent.right; TreeNode subRL = subR.left; parent.right = subRL; if(subRL != null){//只有当subRL不为空时，才能修改其父亲节点 subRL.parent = parent; } subR.left = parent; //在修改parent父亲节点前将其进行记录，以便后续修改subR的父亲节点 TreeNode pParent = parent.parent; parent.parent = subR; //判断subR是否被修改为根节点 if(parent == root){ root = subR; root.parent = null; }else { //判断是其左子树还是右子树 if(pParent.left == parent){ pParent.left = subR; }else{ pParent.right = subR; } subR.parent = pParent; } //修改平衡因子 subR.bf = 0; parent.bf = 0; } //右单旋 private void rotateRight(TreeNode parent){ TreeNode subL = parent.left; TreeNode subLR = subL.right; parent.left = subLR; if(subLR != null){//只有当subLR不为空时，才能修改其父亲节点 subLR.parent = parent; } subL.right = parent; //在修改parent的父亲节点时，必须先记录其父亲节点，以便修改subL的父亲节点 TreeNode pParent = parent.parent; parent.parent = subL; //判断subL是否被修改为根节点 if(parent == root){ root = subL; root.parent = null; }else { subL.parent = pParent; //判断是左子树还是右子树 if(pParent.left == parent){ pParent.left = subL; }else { parent.right = subL; } } //修改平衡因子 subL.bf = 0; parent.bf = 0; } //左右双旋 private void rotateLR(TreeNode parent){ TreeNode subL = parent.left; TreeNode subLR = subL.right; //记录subLR平衡因子 int bf = subLR.bf; rotateLeft(parent.left);//先左旋 rotateRight(parent);//再右旋 //修改平衡因子 if(bf == -1){ parent.bf = 1; }else if(bf == 1){ subL.bf = -1; } } //右左双旋 private void rotateRL(TreeNode parent){ TreeNode subR = parent.right; TreeNode subRL = subR.left; //记录subRL的平衡因子 int bf = subRL.bf; rotateRight(subR);//先右旋 rotateLeft(parent);//再左旋 //修改平衡因子 if(bf == 1){ parent.bf = -1; }else if(bf == -1){ subR.bf = 1; } } //验证 public void inorder(TreeNode root) {//中序遍历 if (root == null) return; inorder(root.left); System.out.print(root.val + " "); inorder(root.right); } private int height(TreeNode root) {//计算子树高度 if(root == null) return 0; int leftH = height(root.left); int rightH = height(root.right); return leftH > rightH ? leftH+1 : rightH+1; } public boolean isBalanced(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; } //判断左右子树高度差绝对值是否不超过1 return Math.abs(leftH-rightH) <= 1 && isBalanced(root.left) && isBalanced(root.right); } }
三、AVL树的性能分析
AVL树是一颗绝对平衡的二叉搜索树，要求每个节点的左右子树高度差的绝对值都不超过1，这样能够保证查询时的高效，即查询的时间复杂度为O（ 
）。但当对AVL树进行一些结构的修改操作时，性能就会比较低下（在插入时为了保持其绝对平衡，就需要进行旋转）。因此，若需要一种查询高效且有序的数据结构，且数据的个数为静态的（不改变），可以考虑使用AVL树，但若是其经常进行修改，就不太适合使用AVL树。
