平衡二叉树也叫平衡二叉搜索树，又被称为AVL树，可以保证查询效率较高，它是一颗空树或者它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是平衡二叉树

    具有下列性质：

    • 它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1。
    • 若将二叉树节点的平衡因子BF定义为该节点的左子树的深度减去它的右子树的深度，则平衡二叉树上所有节点的平衡因子只可能为-1,0,1.
    • 只要二叉树上有一个节点的平衡因子的绝对值大于1，那么这颗平衡二叉树就失去了平衡。

    平衡二叉树 - 图1
    平衡二叉树 - 图2
    平衡二叉树 - 图3

    1. /**
    2.  * 《平衡二叉树》
    3.  *   平衡算法：
    4.  *      1、单向左旋平衡处理
    5.  *      2、单向右旋平衡处理
    6.  *      3、双向旋转（先左后右）平衡处理
    7.  *      4、双向旋转（先右后左）平衡处理
    8.  *
    9.  *   下图二叉排序树（BST）存在的问题分析
    10.  *      1
    11.  *       \
    12.  *        2
    13.  *         \
    14.  *          3
    15.  *           \
    16.  *            4
    17.  *      左子树全部为空，从形式上看，更像一个单链表。插入速度没有影响。查询速度明显降低(因为需要依次比较), 不能发挥BST的优势，
    18.  *   因为每次还需要比较左子树，其查询速度比单链表还慢。解决方案-平衡二叉树(AVL)。
    19.  */
    20. public class AVLTree {
    22.     /**
    23.      * 根结点
    24.      */
    25.     private TreeNode rootNode;
    27.     /**
    28.      * 树结点
    29.      */
    30.     class TreeNode {
    31.         /**
    32.          * 结点值
    33.          */
    34.         private int value;
    35.         /**
    36.          * 左子结点
    37.          */
    38.         private TreeNode left;
    39.         /**
    40.          * 左子结点
    41.          */
    42.         private TreeNode right;
    44.         public TreeNode(int value) {
    45.             this.value = value;
    46.         }
    48.         /**
    49.          * 返回以该结点为根结点的树的高度
    50.          */
    51.         private int height() {
    52.             return Math.max((this.left != null ? this.left.height() : 0), (this.right != null ? this.right.height() : 0)) + 1;
    53.         }
    55.         /**
    56.          * 返回左子树的高度
    57.          */
    58.         private int leftHeight() {
    59.             if (this.left == null) {
    60.                 return 0;
    61.             }
    62.             return this.left.height();
    63.         }
    65.         /**
    66.          * 返回右子树的高度
    67.          */
    68.         private int rightHeight() {
    69.             if (this.right == null) {
    70.                 return 0;
    71.             }
    72.             return this.right.height();
    73.         }
    75.         /**
    76.          * 左旋转
    77.          */
    78.         private void leftRotate() {
    79.             // 1、创建新的结点，以当前根结点的值
    80.             TreeNode newNode = new TreeNode(this.value);
    81.             // 2、把新的结点的左子结点设置成当前结点的左子结点
    82.             newNode.left = this.left;
    83.             // 3、把新的结点的右子结点设置成当前结点的右子结点的左子结点
    84.             newNode.right = this.right.left;
    85.             // 4、把当前结点的值替换成右子结点的值
    86.             this.value = this.right.value;
    87.             // 5、把当前结点的右子结点设置成当前结点右子结点的右子结点
    88.             this.right = this.right.right;
    89.             // 6、把当前结点的左子结点设置成新的结点
    90.             this.left = newNode;
    91.         }
    93.         /**
    94.          * 右旋转
    95.          */
    96.         private void rightRotate() {
    97.             // 1、创建新的结点，以当前根结点的值
    98.             TreeNode newNode = new TreeNode(this.value);
    99.             // 2、把新的结点的右子结点设置成当前结点的右子结点
    100.             newNode.right = this.right;
    101.             // 3、把新的结点的左子结点设置成当前结点的左子结点的右子结点
    102.             newNode.left = this.left.right;
    103.             // 4、把当前结点的值替换成左子结点的值
    104.             this.value = this.left.value;
    105.             // 5、把当前结点的左子结点设置成当前结点左子结点的左子结点
    106.             this.left = this.left.left;
    107.             // 6、把当前结点的右子结点设置成新的结点
    108.             this.right = newNode;
    109.         }
    111.         /**
    112.          * 插入结点
    113.          */
    114.         private void addNode(TreeNode node) {
    115.             // 插入结点小于当前结点，则往当前结点左子结点进行插入
    116.             if (node.value < this.value) {
    117.                 if (this.left == null) {
    118.                     // 左子结点为空时，则直接插入
    119.                     this.left = node;
    120.                 } else {
    121.                     // 左子结点不为空时，则往左子结点插入
    122.                     this.left.addNode(node);
    123.                 }
    124.             // 否则往当前结点右子结点进行插入
    125.             } else {
    126.                 if (this.right == null) {
    127.                     // 右子结点为空时，则直接插入
    128.                     this.right = node;
    129.                 } else {
    130.                     // 右子结点不为空时，则往右子结点插入
    131.                     this.right.addNode(node);
    132.                 }
    133.             }
    135.             // 当添加完一个结点后，如果: (右子树的高度-左子树的高度) > 1 , 左旋转
    136.             if(rightHeight() - leftHeight() > 1) {
    137.                 //如果它的右子树的左子树的高度大于它的右子树的右子树的高度
    138.                 if(right != null && right.leftHeight() > right.rightHeight()) {
    139.                     //先对右子结点进行右旋转
    140.                     right.rightRotate();
    141.                     //然后在对当前结点进行左旋转
    142.                     leftRotate(); //左旋转..
    143.                 } else {
    144.                     //直接进行左旋转即可
    145.                     leftRotate();
    146.                 }
    147.             // 当添加完一个结点后，如果 (左子树的高度 - 右子树的高度) > 1, 右旋转
    148.             } else if(leftHeight() - rightHeight() > 1) {
    149.                 //如果它的左子树的右子树高度大于它的左子树的高度
    150.                 if(left != null && left.rightHeight() > left.leftHeight()) {
    151.                     //先对当前结点的左结点(左子树)->左旋转
    152.                     left.leftRotate();
    153.                     //再对当前结点进行右旋转
    154.                     rightRotate();
    155.                 } else {
    156.                     //直接进行右旋转即可
    157.                     rightRotate();
    158.                 }
    159.             }
    160.         }
    162.         /**
    163.          * 中序遍历
    164.          */
    165.         private void middleOrder() {
    166.             // 1、中序遍历左子树
    167.             if (this.left != null) {
    168.                 this.left.middleOrder();
    169.             }
    170.             // 2、输出结点
    171.             System.out.printf("%s ", this.value);
    172.             // 3、中序遍历右子树
    173.             if (this.right != null) {
    174.                 this.right.middleOrder();
    175.             }
    176.         }
    177.     }
    179.     /**
    180.      * 中序遍历
    181.      */
    182.     public void middleOrderPrint() {
    183.         if (rootNode == null) {
    184.             return;
    185.         }
    186.         rootNode.middleOrder();
    187.     }
    189.     /**
    190.      * 插入结点
    191.      */
    192.     public void add(int value) {
    193.         TreeNode node = new TreeNode(value);
    194.         // 根结点为空时，则插入结点直接当作根结点
    195.         if (rootNode == null) {
    196.             rootNode = node;
    197.         } else {
    198.             rootNode.addNode(node);
    199.         }
    200.     }
    202.     public static void main(String[] args) {
    203.         int[] arr1 = {4, 3, 6, 5, 7, 8};
    204.         int[] arr2 = {10, 12, 8, 9, 7, 6};
    205.         int[] arr3 = {10, 11, 7, 6, 8, 9};
    206.         //树1左旋转
    207.         AVLTree avlTree1 = new AVLTree();
    208.         for (int i = 0; i < arr1.length; i++) {
    209.             avlTree1.add(arr1[i]);
    210.         }
    211.         System.out.println("左旋转平衡处理~~");
    212.         System.out.println("树1的高度=" + avlTree1.rootNode.height());
    213.         System.out.println("树1的左子树高度=" + avlTree1.rootNode.leftHeight());
    214.         System.out.println("树1的右子树高度=" + avlTree1.rootNode.rightHeight());
    215.         System.out.println();
    217.         //树2右旋转
    218.         AVLTree avlTree2 = new AVLTree();
    219.         for (int i = 0; i < arr2.length; i++) {
    220.             avlTree2.add(arr2[i]);
    221.         }
    222.         System.out.println("右旋转平衡处理~~");
    223.         System.out.println("树2的高度=" + avlTree2.rootNode.height());
    224.         System.out.println("树2的左子树高度=" + avlTree2.rootNode.leftHeight());
    225.         System.out.println("树2的右子树高度=" + avlTree2.rootNode.rightHeight());
    226.         System.out.println();
    228.         //树3双旋转
    229.         AVLTree avlTree3 = new AVLTree();
    230.         for (int i = 0; i < arr3.length; i++) {
    231.             avlTree3.add(arr3[i]);
    232.         }
    233.         System.out.println("双旋转平衡处理~~");
    234.         System.out.println("树3的高度=" + avlTree3.rootNode.height());
    235.         System.out.println("树3的左子树高度=" + avlTree3.rootNode.leftHeight());
    236.         System.out.println("树3的右子树高度=" + avlTree3.rootNode.rightHeight());
    237.         System.out.println();
    238.     }
    240. }