1.什么是平衡二叉树

平衡树(Balance Tree，BT) 指的是，任意节点的子树的高度差都小于等于1他是二叉排序树的改进，解决了二叉排序树的一些小问题平衡二叉树一定是二叉排序树

右子树的高度比左子树的高度要高的时候进行左旋转

左旋转的目的是为了降低右子树的高度

左子树的高度比右子树的高度要高的时候进行右旋转

右旋转的目的是为了降低左子树的高度

这个明显通过单个方向的旋转解决不了问题，需要使用双旋转

什么情况下需要使用双旋转：他的左子树的右子树高度大于他的左子树高度解决方案：先对当前节点的左节点进行左旋转在对当前节点进行右旋转操作

2.代码实现

package com.qin.avl; //平衡二叉树 public class AVLTreeDemo { public static void main(String[] args) { int[] arr = {10,11,7,6,8,9}; //创建一个AVLTree对象 AVLTree avlTree = new AVLTree(); //添加节点 for (int i = 0; i < arr.length; i++) { avlTree.add(new Node(arr[i])); } //中序遍历 System.out.println("中序遍历"); avlTree.infixOrder(); System.out.println("=================="); System.out.println("在旋转之后"); System.out.println("树的高度"+avlTree.getRoot().height()); System.out.println("树的左子树高度"+avlTree.getRoot().leftHeight()); System.out.println("树的右子树高度"+avlTree.getRoot().rightHeight()); } } //创建AVL Tree class AVLTree{ private Node root; public Node getRoot() { return root; } //添加节点的方法 public void add(Node node){ if (root==null){ root = node; //如果root为空，则直接让root指向node }else { root.add(node); } } //中序遍历 public void infixOrder(){ if (root!=null){ root.infixOrder(); }else { System.out.println("当前二叉排序树是空的，无法遍历"); } } } //创建node节点 class Node{ int value; Node left; Node right; public Node(int value) { this.value = value; } @Override public String toString() { return "Node{" + "value=" + value + '}'; } //添加节点的方法 //递归的形式添加节点，注意需要满足二叉排序树的要求 public void add(Node node){ if (node == null){ return; } //判断传入节点的值和当前子树根节点的值得关系 if (node.value<this.value){ //输入节点的值小于当前节点的值 if (this.left==null){ //如果当前节点的左子节点为空，那么就挂载当前节点的左子节点 this.left = node; }else { //递归的向左子树添加 this.left.add(node); } }else { if (this.right==null){ this.right = node; }else { //递归向右子树添加 this.right.add(node); } } //当添加完一个节点后，右子树的高度-左子树的高度的绝对值大于1 ,左旋转 if (rightHeight()-leftHeight()>1){ //如果他的右子树的左子树的高度大于它的右子树的高度 if (right!=null && right.left.height()>right.height()){ //对当前节点的右节点进行右旋转 right.rightRotate(); //在对当前节点进行左旋转 leftRotate(); }else { //否者对当前节点直接左旋转即可 leftRotate(); //左旋转 } return; //必须要！！！ } if (leftHeight()-rightHeight()>1){ //右旋转 //如果他的左子树的右子树的高度大于他的左子树的高度 if (left!=null && left.right.height()>left.leftHeight()){ //先对当前节点的左节点（左子树）进行左旋转 left.leftRotate(); //在对当前节点进行右旋转 rightRotate(); }else { //不满足条件，直接右旋转即可 rightRotate(); } } } //中序遍历 public void infixOrder(){ if (this.left!=null){ this.left.infixOrder(); } System.out.println(this); if (this.right!=null){ this.right.infixOrder(); } } //返回以该节点为根节点，这颗树的高度 public int height(){ return Math.max(left==null?0:left.height(),right==null?0:right.height())+1; } //返回左子树的高度 public int leftHeight(){ if (left==null){ return 0; } return left.height(); } //返回右子树的高度 public int rightHeight(){ if (right==null){ return 0; } return right.height(); } //左旋转的方法 private void leftRotate(){ //创建新的节点，以当前根节点的值 Node newNode = new Node(value); //把新的节点的左子树设置为当前节点的左子树 newNode.left = left; //把新的节点的右子树设置成当前节点的右子树的左子树 newNode.right = right.left; //把当前节点的值替换成右子节点的值 value = right.value; //把当前节点的右子树设置成当前节点右子树的右子树 right = right.right; //把当前节点的左子节点设置成新的节点 left = newNode; } //右旋转的方法 private void rightRotate(){ //创建新的节点，以当前根节点的值 Node newNode = new Node(value); //把新的节点的右子树设置为当前节点的右子树 newNode.right = right; //把新的节点的左子树设置成当前节点的左子树的右子树 newNode.left = left.right; //把当前节点的值替换为左子节点的值 value = left.value; //把当前节点的左子树设置成当前节点左子树的左子树 left = left.left; right = newNode; } }