什么是平衡二叉树？ 平衡二叉树 ：（Balanced Binary Tree）又被称为AVL树（有别于AVL算法），且具有以下性质：
它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。这个方案很好的解决了二叉查找树退化成链表的问题，把插入，查找，删除的时间复杂度最好情况和最坏情况都维持在O(logN)。但是频繁旋转会使插入和删除牺牲掉O(logN)左右的时间，不过相对二叉查找树来说，时间上稳定了很多。
在讲解平衡二叉树之前我们先了解以下树的高度以及层的概念
查询树的高度思路：通过递归实现查询当前节点的左右子树的最大高度，然后再 + 1（加上节点本身），此时就是树的最大高度
代码语言：javascript复制//查询树的高度
public int height(){
return Math.max(left == null ? 0:left.height(),right == null ? 0:right.height()) + 1;
}查询左右子树的高度代码语言：javascript复制//查询左子树的高度
public int leftHeight(){
if(left == null){
return 0;
}
return left.height();
}
//查询右子树的高度
public int rightHeight(){
if(right == null){
return 0;
}
return right.height();
}平衡二叉树实现左旋转节点的左子树的高度即h(左) 和 右子树即h(右)的差值大于1 。
具体来说就是 h(右) - h(左) > 1
当满足这个情况时我们就需要进行左旋转
思路new 一个新的节点newNode ，value 为当前节点的value设置newNode的left节点 为当前节点的left设置newNode 的right节点 为当前节点的right的left节点将当前节点的value设置为 当前节点的right的value把当前节点的right 设置为 当前节点的right 的right把当前节点的left设置为 newNode代码语言：javascript复制//左旋转
public void leftRotate(){
//new 一个新的节点，值为当前节点的val
Node newNode = new Node(this.val);
//将当前节点的left节点 设置为newNode的left
newNode.left = this.left;
//把当前节点this的right的left节点 设置为newNode的right
newNode.right = this.right.left;
//把当前节点的val修改成 当前节点的right的val
this.val = this.right.val;
//把当前节点的left设置为 newNode
this.left = newNode;
//把当前节点的right设置为 当前节点的right的right
this.right = this.right.right;
}右旋转当前节点的左子树的高度，即h(左) 和 右子树即h(右)的差值大于1 。
具体来说就是 h(左) - h(右) > 1
当满足这个情况时我们就需要进行右旋转
思路new 一个新的节点newNode ，value 为当前节点的value设置newNode的right节点 为当前节点的right设置newNode 的left节点 为当前节点的left的right节点将当前节点的value设置为 当前节点的left的value把当前节点的left设置为 当前节点的left 的left把当前节点的right设置为 newNode代码语言：javascript复制public void rightRotate(){
//new新的节点 ，值为this.val
Node newNode = new Node(this.val);
//newNode 的right节点为当前节点的right节点
newNode.right = this.right;
//newNode 的left节点 为当前节点的left的right节点
newNode.left = this.left.right;
//修改当前节点的val为 当前节点的left 的val
this.val = this.left.val;
//修改当前节点的left 为 当前节点的left 的 left
this.left = this.left.left;
//修改当前节点的right 为newNode
this.right = newNode;
}双旋转双旋转出现的原因以数组【10，11，7，6，8，9】为例
如下图可以看到，以节点8为根节点的right树高度 - left树的高度 > 1
这样如果我们还是按照之前的做法势必无法得到平衡二叉树。所以我们就需要先将以节点8 为根节点的二叉树进行左旋转使它成为平衡二叉树之后，再对整棵树进行右旋转， 这样我们才能使整棵树都是平衡二叉树
解决思路 如果当前树需要进行左旋转（即(rightHeight() - leftHeight() > 1)）
那么就需要判断右节点的rightHeight 是否 < rightHeight
如果满足， 那么就先将以right节点为根节点的树进行右旋转 ，然后再将整个树进行左旋转
同理
当前树需要进行右旋转（即(leftHeight() - rightHeight() > 1)）
那么就需要判断左节点的rightHeight 是否 > leftHeight
如果满足， 那么就先将以left节点为根节点的树进行左旋转 ，然后再将整个树进行右旋转
代码语言：javascript复制 if (rightHeight() - leftHeight() > 1){
//当前节点的右子树的右子树高度 < 当前节点的右子树的左子树高度
if (right != null && right.rightHeight() < right.leftHeight()){
//先将右子树进行右旋转 ，然后再将所有的树进行左旋转
right.rightRotate();
leftRotate();
}else {
leftRotate();
}
}
else if (leftHeight() - rightHeight() > 1){
//当前节点的左子树的右子树高度 > 当前节点的左子树的左子树高度
if (left != null && left.leftHeight() < left.rightHeight()){
//先将左子树进行左旋转 ，然后再将整棵树进行右旋转
left.leftRotate();
rightRotate();
}else {
rightRotate();
}
}
}代码实现代码语言：javascript复制public class Node {
public int val;
public Node right;
public Node left;
//左旋转
public void leftRotate(){
//new 一个新的节点，值为当前节点的val
Node newNode = new Node(this.val);
//将当前节点的left节点 设置为newNode的left
newNode.left = this.left;
//把当前节点this的right的left节点 设置为newNode的right
newNode.right = this.right.left;
//把当前节点的val修改成 当前节点的right的val
this.val = this.right.val;
//把当前节点的left设置为 newNode
this.left = newNode;
//把当前节点的right设置为 当前节点的right的right
this.right = this.right.right;
}
public void rightRotate(){
//new新的节点 ，值为this.val
Node newNode = new Node(this.val);
//newNode 的right节点为当前节点的right节点
newNode.right = this.right;
//newNode 的left节点 为当前节点的left的right节点
newNode.left = this.left.right;
//修改当前节点的val为 当前节点的left 的val
this.val = this.left.val;
//修改当前节点的left 为 当前节点的left 的 left
this.left = this.left.left;
//修改当前节点的right 为newNode
this.right = newNode;
}
//添加树
public void add(Node node){
if(node == null){
return;
}
if(node.val < this.val){
if(this.left == null){
this.left = node;
}else{
this.left.add(node);
}
}else{
//node.val >= this.val
if(this.right == null){
this.right = node;
}else{
this.right.add(node);
}
}
if (rightHeight() - leftHeight() > 1){
//当前节点的右子树的右子树高度 < 当前节点的右子树的左子树高度
if (right != null && right.rightHeight() < right.leftHeight()){
//先将右子树进行右旋转 ，然后再将所有的树进行左旋转
right.rightRotate();
leftRotate();
}else {
leftRotate();
}
}
else if (leftHeight() - rightHeight() > 1){
//当前节点的左子树的右子树高度 > 当前节点的左子树的左子树高度
if (left != null && left.leftHeight() < left.rightHeight()){
//先将左子树进行左旋转 ，然后再将整棵树进行右旋转
left.leftRotate();
rightRotate();
}else {
rightRotate();
}
}
}
//查询左子树的高度
public int leftHeight(){
if(left == null){
return 0;
}
return left.height();
}
//查询右子树的高度
public int rightHeight(){
if(right == null){
return 0;
}
return right.height();
}
//查询树的高度
public int height(){
return Math.max(left == null ? 0:left.height(),right == null ? 0:right.height()) + 1;
}
//中序遍历二叉树
public void infix(){
if(this.left != null){
this.left.infix();
}
System.out.println(this);
if (this.right != null){
this.right.infix();
}
}
public Node(int val) {
this.val = val;
}
@Override
public String toString() {
return "Node[" +
"val=" + val +
']';
}
}代码语言：javascript复制public class AVLTree {
public Node root;
public static void main(String[] args) {
//int[] arr = {4,3,6,5,7,8};
// int[] arr = {10,12,8,9,7,6};
int[] arr = {10,11,7,6,8,9,12,33,14,1,22,0,3,33,23,44,55,54,34};
AVLTree avl = new AVLTree();
for (int i=0;i avl.add(new Node(arr[i])); } avl.root.infix(); System.out.println("树的高度 :" + avl.root.height()); System.out.println("树的左子树高度 :" + avl.root.leftHeight()); System.out.println("树的右子树高度 :" + avl.root.rightHeight()); } public void add(Node node){ if (root == null){ root = node; }else{ root.add(node); } } }运行结果 Node[val=0] Node[val=1] Node[val=3] Node[val=6] Node[val=7] Node[val=8] Node[val=9] Node[val=10] Node[val=11] Node[val=12] Node[val=14] Node[val=22] Node[val=23] Node[val=33] Node[val=33] Node[val=34] Node[val=44] Node[val=54] Node[val=55] 树的高度 :5 树的左子树高度 :3 树的右子树高度 :4 进程已结束,退出代码0