（一）回顾二叉搜索树
在之前我们说二叉搜索树有以下性质：
若左子树不为空则左子树上的值小于根节点
若右子树不为空则右子树上的值大于根节点
左右子树也都为二叉搜索树
我们之前在实现的时候分析了查找的时间复杂度有两种情况 分别是：完全二叉树O(logN)和单分支的树O（N）那如果是完全二叉树肯定是最好的，但是如果是单支树，那么效率就会大大降低，所以我们要尽量的让左右子树平衡，所以就出现了AVL树---一种平衡的二叉搜索树
（二）AVL树
AVL树具有以下性质：
在二叉搜索树的基础上，他的左右子树高度差（平衡因子）绝对值是不超过1的
他的左右子树也都是AVL树
如果我们保证他的左右子树高度差在1以内，那么我们查询的时间复杂度就可以稳定在O(logN)
（三）实现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;}}//cur == nullif(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 -1if(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 == -1rotateRL(parent);}}else {//parent.bf == -2 左树高-》需要降低左树的高度if(cur.bf == -1) {//右旋rotateRight(parent);}else {//cur.bf == 1rotateLR(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) {parent.bf = -1;subR.bf = 0;subRL.bf = 0;}else if(bf == -1){parent.bf = 0;subR.bf = 1;subRL.bf = 0;}}/*** 左右双旋* @param parent*/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;}}/*** 左单旋* @param parent*/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(root == parent) {root = subR;root.parent = null;}else {if(pParent.left == parent) {pParent.left = subR;}else {pParent.right = subR;}subR.parent = pParent;}subR.bf = parent.bf = 0;}/*** 右单旋* @param parent*/private void rotateRight(TreeNode parent) {TreeNode subL = parent.left;TreeNode subLR = subL.right;parent.left = subLR;subL.right = parent;//没有subLRif(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;}//中序遍历的结果是有序的 就能说明当前树 一定是AVL树吗？ 不一定的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;}return Math.abs(leftH-rightH) <= 1&& isBalanced(root.left)&& isBalanced(root.right);}public static void main(String[] args) {int[] array = {4, 2, 6, 1, 3, 5, 15, 7, 16,14};//int[] array = {30,20,90,60,180,40};AVLTree avlTree = new AVLTree();for (int i = 0; i < array.length; i++) {avlTree.insert(array[i]);}System.out.println(avlTree.isBalanced(avlTree.root));}
}