共计 4266 个字符，预计需要花费 11 分钟才能阅读完成。
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() {
// 创立新的节点，以以后节点的值作为 value
Node 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。
