AVL树的概念
二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺
序表中搜索元素，效率低下。因此，两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年 发明了一种
解决上述问题的方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过
1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。
一棵AVL树或者是空树，或者是具有以下性质的二叉搜索树：
它的左右子树都是AVL树
左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)
平衡因子bf = 右子树高度 - 左子树高度
如果一棵二叉搜索树是高度平衡的，它就是AVL树。如果它有n个结点，其高度可保持在O(log_2 n)，搜索时间
复杂度O(log_2 n)。
AVL树的插入
AVL树节点在定义时维护一个平衡因子，具体节点定义如下：
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; } }
AVL树的插入过程可以分为两步：
1. 按照二叉搜索树的方式插入新节点
2. 调整节点的平衡因子
按照二叉搜索树的方式插入新节点：
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){ return false; }else { parent = cur; cur = cur.left; } } if (parent.val < val){ parent.right = node; }else { parent.left = node; } 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 { //cur.bf == -1 rotateRL(parent); } }else { //parent.bf == -2 左树高-》需要降低左树的高度 if (cur.bf == -1){ //右单旋 rotateRight(parent); }else { //cur.bf == 1 //左右双旋 rotateLR(parent); } } //上述代码走完就已经平衡了 break; } }
左单旋-插入位置在较高右子树的右侧：（parent.bf = 2, cur.bf = 1）
//左单旋 private void rotateLeft(TreeNode parent) { TreeNode subR = parent.right; TreeNode subRL= subR.left; parent.right = subRL; subR.left = parent; if (subRL != null){ subRL.parent = parent; } TreeNode pParent = parent.parent; parent.parent = 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）
//右单旋 private void rotateRight(TreeNode parent) { TreeNode subL = parent.left; TreeNode subLR = subL.right; parent.left = subLR; subL.right = parent; if (subLR != null){ subLR.parent = parent; } //必须先记录当前的父亲的父亲节点 TreeNode pParent = parent.parent; parent.parent = subL; //检查当前节点是不是根节点 if (parent == root){ root = subL; root.parent = null; }else { //不是根节点，判断这颗子树是左子树还是右子树 if (pParent.left == parent){ pParent.left = subL; }else { pParent.right = subL; } subL.parent = pParent; } subL.bf = 0; parent.bf = 0; }
左右双旋-插入位置在较高左子树的右侧：（parent.bf = -2, cur.bf = 1）
//左右双旋 private void rotateLR(TreeNode parent) { TreeNode subL = parent.left; TreeNode subLR= subL.right; int bf = subLR.bf; rotateLeft(parent.left); rotateRight(parent); if (bf == -1){ subL.bf = 0; subLR.bf = 0; parent.bf = 1; }else if (bf == 1){ subL.bf = -1; subLR.bf = 0; parent.bf = 0; } }
右左双旋-插入位置在较高右子树的左侧：（parent.bf = 2, cur.bf = -1）
private void rotateRL(TreeNode parent) { TreeNode subR = parent.right; TreeNode subRL = subR.left; int bf = subRL.bf; rotateRight(parent.right); rotateLeft(parent); if (bf == 1){ subR.bf = 0; subRL.bf = 0; parent.bf = -1; }else if (bf == -1){ subR.bf = 1; subRL.bf = 0; parent.bf = 0; } }
AVL树插入操作的完整代码+验证代码
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){ return false; }else { parent = cur; cur = cur.left; } } if (parent.val < val){ parent.right = node; }else { parent.left = node; } 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 { //cur.bf == -1 rotateRL(parent); } }else { //parent.bf == -2 左树高-》需要降低左树的高度 if (cur.bf == -1){ //右单旋 rotateRight(parent); }else { //cur.bf == 1 //左右双旋 rotateLR(parent); } } //上述代码走完就已经平衡了 break; } } return true; } private void rotateRL(TreeNode parent) { TreeNode subR = parent.right; TreeNode subRL = subR.left; int bf = subRL.bf; rotateRight(parent.right); rotateLeft(parent); if (bf == 1){ subR.bf = 0; subRL.bf = 0; parent.bf = -1; }else if (bf == -1){ subR.bf = 1; subRL.bf = 0; parent.bf = 0; } } //左右双旋 private void rotateLR(TreeNode parent) { TreeNode subL = parent.left; TreeNode subLR= subL.right; int bf = subLR.bf; rotateLeft(parent.left); rotateRight(parent); if (bf == -1){ subL.bf = 0; subLR.bf = 0; parent.bf = 1; }else if (bf == 1){ subL.bf = -1; subLR.bf = 0; parent.bf = 0; } } //左单旋 private void rotateLeft(TreeNode parent) { TreeNode subR = parent.right; TreeNode subRL= subR.left; parent.right = subRL; subR.left = parent; if (subRL != null){ subRL.parent = parent; } TreeNode pParent = parent.parent; parent.parent = 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; subL.right = parent; if (subLR != null){ subLR.parent = parent; } //必须先记录当前的父亲的父亲节点 TreeNode pParent = parent.parent; parent.parent = subL; //检查当前节点是不是根节点 if (parent == root){ root = subL; root.parent = null; }else { //不是根节点，判断这颗子树是左子树还是右子树 if (pParent.left == parent){ pParent.left = subL; }else { pParent.right = subL; } subL.parent = pParent; } subL.bf = 0; parent.bf = 0; } //中序遍历 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 leftHeight = height(root.left); int rightHeight = height(root.right); return leftHeight > rightHeight ? leftHeight+1 : rightHeight+1; } public boolean isBalanced(TreeNode root){ if (root == null)return true; int leftHeight = height(root.left); int rightHeight = height(root.right); if (rightHeight-leftHeight != root.bf){ System.out.println("这个节点："+root.val + "有异常!"); return false; } return Math.abs(leftHeight-rightHeight) <= 1 && isBalanced(root.left) && isBalanced(root.right); } }
AVL树的删除
因为AVL树也是二叉搜索树，可按照二叉搜索树的方式将节点删除，然后再更新平衡因子，只不过与删除不
同的是，删除节点后的平衡因子更新，最差情况下一直要调整到根节点的位置。
1、找到需要删除的节点
2、按照搜索树的删除规则删除节点--参考https://blog.csdn.net/crazy_xieyi/article/details/127627063
3、更新平衡因子，如果出现了不平衡，进行旋转。--单旋，双旋
AVL树的性能分析
AVL树是一棵绝对平衡的二叉搜索树，其要求每个节点的左右子树高度差的绝对值都不超过1，这样可以保证查询
时高效的时间复杂度，即 。但是如果要对AVL树做一些结构修改的操作，性能非常低下，比如：插入时要
维护其绝对平衡，旋转的次数比较多，更差的是在删除时，有可能一直要让旋转持续到根的位置。因此：如果需要
一种查询高效且有序的数据结构，而且数据的个数为静态的(即不会改变)，可以考虑AVL树，但一个结构经常修
改，就不太适合。
