PS：本文系转载文章，浏览原文可读性会更好，文章开端有原文链接
目录
1、二叉排序树可能存在的问题
2、均衡二叉树
2、1 均衡二叉树的根本介绍 2、2 二叉树的左旋转1、二叉排序树可能存在的问题
在二叉排序树（Java实现）这篇文章，咱们学习了二叉排序树，然而它可能存在一些问题，假如咱们拿到的是一个从小到大排序的数列 array = {3 , 4 , 5 , 6 , 7 , 8 , 9}，那么构建进去的二叉排序树就如图1所示；
图片
从图1能够看出，构建进去的二叉排序树有如下问题：左子树全副为空，像一个单链表；插入速度不受影响；查问速度会升高，不能施展二叉排序树的长处，每次还须要比拟左子树，其查问速度比单链表还慢；这时候如果要解决图1中呈现的问题，就要引入到均衡二叉树了。
2、均衡二叉树
2、1 均衡二叉树的根本介绍
均衡二叉树也叫均衡二叉搜寻树又被称为AVL树，能够保障查问效率；它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵均衡二叉树。
好，为了不便了解均衡二叉树，我这里列举2个案例一下；
案例1：看图2中的二叉树，根节点的左子节点2（以2节点看做是 “根节点”，此时红框里的3个节点也能够当做一棵小的二叉树）的高度为2，根节点的右子节5（以5节点看做是 “根节点”，此时红框里的1个节点也能够当做一棵小的二叉树）的高度为1，这时候根节点的左右子树的高度差的绝对值为1，不超过1，所以图2中的二叉树是均衡二叉树。
图片
案例2：看图3中的二叉树，根节点的左子节点8（以8节点看做是 “根节点”，此时红框里的4个节点也能够当做一棵小的二叉树）的高度为3，根节点的右子节11（以11节点看做是 “根节点”，此时红框里的1个节点也能够当做一棵小的二叉树）的高度为1，这时候根节点的左右子树的高度差的绝对值为2，超过了1，所以图3中的二叉树不是均衡二叉树。
图片
2、2 二叉树的左旋转
咱们进行一棵二叉树的左旋转，目标无非就是让这棵二叉树变成均衡二叉树；那进行左旋转无非就是这颗二叉树不是均衡二叉树，而且它左子树的高度比右子树的高度小，而且这个数值肯定至多是2。好了，假如咱们拿到一个数列 array = {2,1,4,3,5,6}，依据二叉排序树（Java实现）这篇文章所学到的常识，咱们构建的二叉排序树就如图4所示；
图片
看图4，左子树的高度为1，右子树的高度为3，显然它不是一颗均衡二叉树，左子树的高度比右子树的高度小，而且这个数值是2，所以如果咱们要把图4中的二叉树变成均衡二叉树，就要对图4这棵二叉树进行左旋转，如何进行左旋转呢？咱们对它进行思路剖析一下。
（1）创立一个新的节点，这个节点的值等于根节点的值，如图5所示；
图片
（2）咱们把根节点作为以后节点，把新节点的左子树指向以后节点的左子树，把新节点的右子树指向以后节点的右子树的左子树，这时候失去图6所示的结构图；
图片
（3）把以后节点的值改为以后节点的右子树的值，这时候就失去如图7所示的结构图；
图片
（4）把以后节点的右子树指向右子树的右子树（也就是红色数字4的右子树指向5节点），把以后节点的左子树指向新的节点（也就是红色数字4的左子树指向红色数字2），这时候就失去如图8所示的结构图；
图片
（5）这时候红色数字4的节点作为新的根节点，而红色数字4的节点没有任何节点指向它，咱们就把它省略掉，咱们把图8的结构图简化一下，失去图9所示的二叉树；
图片
（6）第一次左旋转实现后，咱们判断一下这棵二叉树是不是均衡二叉树，如果不是，那就进行下一轮的左旋转；很显然，图9中的二叉树的左子树的高度和右子树的高度都是2，所以是一棵均衡二叉树。
比照了一下图4和图9，咱们发现啊，进行一轮左旋转后，旧的根节点的右子树就变成了新的根节点，新的根节点的左子树就变成了旧的根节点，新的根节点的左子树就变成了旧的根节点的右子树；这里左旋转的规定无非就是将旧的右子节点作为新的根节点，将旧的根节点作为新根节点的左子节点，将旧的根节点的右子节点的左子节点作为新根节点的左子节点的右子节点。
好了，咱们当初对数列 array = {2,1,4,3,5,6} 进行构建一棵二叉排序树，并进行左旋转，当初用代码实现一把；
（1）新建一个节点类 Node ：
package com.xiaoer.binarysorttree;
public class Node {
private Node leftNode;private Node rightNode;private int value;//返回左子树的高度public int leftHeight() { int height = leftNode == null ? 0 : leftNode.height(); return height;}//返回右子树的高度public int rightHeight() { int height = rightNode == null ? 0 : rightNode.height(); return height;}//返回以后节点的高度public int height() { int height = Math.max(leftNode == null ? 0 : leftNode.height(), rightNode == null ? 0 : rightNode.height()) + 1; return height;}public Node(int value) {
super();this.value = value;}
//增加节点办法
public void addNode(Node node) {
if (node == null) { System.out.println("该节点为空，不进行增加"); return;}//判断传入节点的值是否比以后节点的值小if (node.value < value) { //如果以后节点的左子节点为空，那么就把传入的节点作为以后节点的左子节点 if (leftNode == null) { leftNode = node; //递归遍历以后节点的左子树增加 node } else { leftNode.addNode(node); } //否则增加的节点的值大于等于以后节点的值} else { //如果以后节点的右子节点为空，那么就把传入的节点作为以后节点的右子节点 if (rightNode == null) { rightNode = node; //递归遍历以后节点的右子树增加 node } else { rightNode.addNode(node); }}}
//这里进行左旋转，以后节点是指根节点
public void leftRotate() {
//创立新的节点，以以后节点的值作为 valueNode newNode = new Node(value);//把新的结点的左子树指向以后结点的左子树newNode.leftNode = leftNode;//把新的结点的右子树指向以后节点的右子树的左子树newNode.rightNode = rightNode.leftNode;//把以后节点的值批改为右子树的值value = rightNode.value;//把以后节点的右子树指向以后节点的右子树的右子树rightNode = rightNode.rightNode;//把以后节点的左子树指向新的节点leftNode = newNode;}
//后续遍历
public void postOrder() {
if (leftNode != null) { leftNode.postOrder();}if (rightNode != null) { rightNode.postOrder();}System.out.println(this);}
@Override
public String toString() {
return "Node [value=" + value + "]";}
}
（2）新建一个测试类 Test ：
package com.xiaoer.binarysorttree;
public class Test {
private Node rootNode;
public static void main(String[] args) {
int[] array = { 2, 1, 4, 3, 5, 6 };Test test = new Test();// for 循环将数组转化成二叉排序树for (int i = 0; i < array.length; i++) { test.addNode(new Node(array[i]));}System.out.println("在没有进行左旋转之前");System.out.println("左子树的高度：" + test.rootNode.leftHeight());System.out.println("右子树的高度：" + test.rootNode.rightHeight());// 二叉排序树的后续遍历test.postOrder();System.out.println("进行左旋转之后");test.leftRotate();System.out.println("左子树的高度：" + test.rootNode.leftHeight());System.out.println("右子树的高度：" + test.rootNode.rightHeight());// 二叉排序树的后续遍历test.postOrder();}
private void leftRotate() {
if (rootNode == null) { System.out.println("这是一棵空树，不能进行左旋转");} else { if (rootNode.rightHeight() - rootNode.leftHeight() > 1) { rootNode.leftRotate(); leftRotate(); }}}
private void addNode(Node node) {
if (rootNode == null) { rootNode = node;} else { rootNode.addNode(node);}}
private void postOrder() {
if (rootNode == null) { System.out.println("这是一棵空树");} else { rootNode.postOrder();}}
}
这里如何判断咱们的左旋转是否胜利呢？咱们看没旋转之前的图4，左子树的高度为1，右子树的高度为3，后序遍历为：1 3 6 5 4 2；旋转之后的图9，左子树的高度为2，右子树的高度为2，后序遍历为：1 3 2 6 5 4；运行程序一把；
图片
看到运行后果了没，和图9的后果是一样的，左子树的高度为2，右子树的高度为2，后序遍历为：1 3 2 6 5 4 。