平衡二叉树（AVL树）
目录
一、二叉查询树的问题
二、平衡二叉树简介
三、实现树的高度
（1）实现树的高度
（2）分别实现左、右子树的高度方法
四、树的旋转
（1）实现左旋转
（2）实现右旋转
（3）实现双旋转
五、小结：
六、二叉平衡树完整版代码
一、二叉查询树的问题
二、平衡二叉树简介
三、实现树的高度
结点内部类：
//写一个结点内部类public static class Node{int value;Node left;Node right;public Node(int value){this.value = value;}
}（1）实现树的高度
在Node节点内部类中，实现计算当前结点到叶子结点的高度的代码。
思路：当前结点的高度 = 当前结点的子树高度 + 1
//在Node结点类中，实现当前结点到叶子结点的高度的代码//实现获取当前结点的高度的方法//思路：当前结点的高度 = 当前结点子树的高度+1public int height(){return Math.max(left == null?0:left.height(),right == null?0:right.height())+1;}（2）分别实现左、右子树的高度方法
在Node节点内部类中，实现左、右子树高度的代码。
//分别实现左、右子树的高度方法//因为后面需要对左右子树进行高度判断，如果左右子树高度差大于1，则是不平衡的。//获取左子树的高度public int leftHeight(){if (left == null){return 0;}return left.height();}//获取右子树的高度public int rightHeight(){if (right == null){return 0;}return right.height();}四、树的旋转
在Node节点内部类中，实现左、右、双旋转的代码。
（1）实现左旋转
思路：
//实现左旋转public void leftRotate(){//1.创建新的结点，存储当前结点的值Node newNode = new Node(this.value);//2.将新节点的左子节点，指向当前结点的左子节点newNode.left = this.left;//3.将新节点的右子节点，指向当前结点的右子节点的左子节点newNode.right = this.right.left;//4.将右子节点的值，放入到当前结点中this.value = this.right.value;//5.将当前结点的右子节点，指向右子节点的右子节点this.right = this.right.right;//6.将当前结点的左子节点指向新的结点this.left = newNode;}（2）实现右旋转
右旋转的实现原理跟左旋转一样，将思路和代码跟左旋转相反就行。
//实现右旋转public void rightRotate(){//1.创建新的结点，存储当前结点的值Node newNode = new Node(this.value);//2.将新节点的右子节点，指向当前结点的右子节点newNode.right = this.right;//3.将新节点的左子节点，指向当前结点的左子节点的右子节点newNode.left = this.left.right;//4.将左子节点的值，放入到当前结点中this.value = this.left.value;//5.将当前结点的左子节点，指向左子节点的左子节点this.left = this.left.left;//6.将当前结点的右子节点指向新的结点this.right = newNode;}（3）实现双旋转
为了实现一棵平衡二叉树，那么在插入元素的时候要进行一个判断，就是插入元素之后，如果树不满足平衡条件了，那么需要将树进行旋转来满足树的平衡。
//在插入完成时进行判断,根据情况对树进行旋转操作，来维持树的平衡//但是一次旋转往往不能满足平衡，需要双旋转才能满足(双旋转：左旋+右旋/右旋+左旋)//如果右子树的高度 - 左子树的高度 > 1if (root.right.rightHeight() - root.leftHeight() > 1){//当右子节点的左子树大于右子树的时候，需要将右子树进行右旋转if (root.right != null && root.right.leftHeight()>root.right.rightHeight()){//将右子节点进行右旋转root.right.rightRotate();}//执行左旋转root.leftRotate();}//左子树的高度 - 如果右子树的高度 > 1if (root.leftHeight() - root.rightHeight() > 1){//当左子节点的右子树大于左子树的时候，需要将左子树进行坐旋转if (root.left != null && root.left.rightHeight()>root.left.leftHeight()){//将左子节点进行左旋转root.left.leftRotate();}//执行右旋转root.rightRotate();}插入方法完整版代码：
//写一个插入类public void insert(int value){//如果树为null，则直接插入在根节点上if (root == null){root = new Node(value);}//声明一个游标结点，开始指向根节点Node node = root;//如果树不为null，则比较插入的值与根节点的大小，小放左边大放右边while(true){if (value < node.value){//如果root.left为null，则直接插入到root.left中if (node.left == null){node.left = new Node(value);break;}else{//将游标指向左子节点node = node.left;}}else {if (node.right ==null){node.right = new Node(value);break;}else {//将游标指向右子节点node = node.right;}}}//在插入完成时进行判断,根据情况对树进行旋转操作，来维持树的平衡//但是一次旋转往往不能满足平衡，需要双旋转才能满足(双旋转：左旋+右旋/右旋+左旋)//如果右子树的高度 - 左子树的高度 > 1if (root.right.rightHeight() - root.leftHeight() > 1){//当右子节点的左子树大于右子树的时候，需要将右子树进行右旋转if (root.right != null && root.right.leftHeight()>root.right.rightHeight()){//将右子节点进行右旋转root.right.rightRotate();}//执行左旋转root.leftRotate();}//左子树的高度 - 如果右子树的高度 > 1if (root.leftHeight() - root.rightHeight() > 1){//当左子节点的右子树大于左子树的时候，需要将左子树进行坐旋转if (root.left != null && root.left.rightHeight()>root.left.leftHeight()){//将左子节点进行左旋转root.left.leftRotate();}//执行右旋转root.rightRotate();}}五、小结：
1.AVL（二叉平衡树）主要是为了解决二叉查询树不平衡的情况下，导致查询效率低下的解决方案。
2.AVL的主要规则：左子树和右子树的高度差不能超过1，如果超过1那么则进行左旋转或者右旋转来达到平衡的状态。
3.具体的旋转规则如下：
（1）左子树的高度 - 右子树的高度 > 1
如果：左子节点的右子树的高度 > 左子树的高度，那么左子节点先进行左旋转
将当前根节点进行右旋转
（2）右子树的高度 - 左子树的高度 > 1
如果：右子节点的左子树的高度 > 右子树的高度，那么右子节点先进行右旋转
将当前根节点进行左旋转
六、二叉平衡树完整版代码
一些业务代码跟二叉查询树一样，像插入、删除、中序遍历、结点内部类等，都是跟二叉查询树一样的思路和代码，只是一些细节不一样，不一样的地方也就是插入的时候在最后需要判断一下是否平衡，不平衡则进行旋转、结点内部类多了三个方法，一个树的高度、两个左右子树高度的分别实现。
package Tree.AVLTree;import Tree.BinarySearchTree.BinarySearchTree;public class AVLTree {//写一个结点内部类public static class Node{int value;Node left;Node right;public Node(int value){this.value = value;}//在Node结点类中，实现当前结点到叶子结点的高度的代码//实现获取当前结点的高度的方法//思路：当前结点的高度 = 当前结点子树的高度+1public int height(){return Math.max(left == null?0:left.height(),right == null?0:right.height())+1;}//分别实现左、右子树的高度方法//因为后面需要对左右子树进行高度判断，如果左右子树高度差大于1，则是不平衡的。//获取左子树的高度public int leftHeight(){if (left == null){return 0;}return left.height();}//获取右子树的高度public int rightHeight(){if (right == null){return 0;}return right.height();}//实现左旋转public void leftRotate(){//1.创建新的结点，存储当前结点的值Node newNode = new Node(this.value);//2.将新节点的左子节点，指向当前结点的左子节点newNode.left = this.left;//3.将新节点的右子节点，指向当前结点的右子节点的左子节点newNode.right = this.right.left;//4.将右子节点的值，放入到当前结点中this.value = this.right.value;//5.将当前结点的右子节点，指向右子节点的右子节点this.right = this.right.right;//6.将当前结点的左子节点指向新的结点this.left = newNode;}//实现右旋转public void rightRotate(){//1.创建新的结点，存储当前结点的值Node newNode = new Node(this.value);//2.将新节点的右子节点，指向当前结点的右子节点newNode.right = this.right;//3.将新节点的左子节点，指向当前结点的左子节点的右子节点newNode.left = this.left.right;//4.将左子节点的值，放入到当前结点中this.value = this.left.value;//5.将当前结点的左子节点，指向左子节点的左子节点this.left = this.left.left;//6.将当前结点的右子节点指向新的结点this.right = newNode;}}//先定义一个根节点Node root;//写一个插入类public void insert(int value){//如果树为null，则直接插入在根节点上if (root == null){root = new Node(value);}//声明一个游标结点，开始指向根节点Node node = root;//如果树不为null，则比较插入的值与根节点的大小，小放左边大放右边while(true){if (value < node.value){//如果root.left为null，则直接插入到root.left中if (node.left == null){node.left = new Node(value);break;}else{//将游标指向左子节点node = node.left;}}else {if (node.right ==null){node.right = new Node(value);break;}else {//将游标指向右子节点node = node.right;}}}//在插入完成时进行判断,根据情况对树进行旋转操作，来维持树的平衡//但是一次旋转往往不能满足平衡，需要双旋转才能满足(双旋转：左旋+右旋/右旋+左旋)//如果右子树的高度 - 左子树的高度 > 1if (root.right.rightHeight() - root.leftHeight() > 1){//当右子节点的左子树大于右子树的时候，需要将右子树进行右旋转if (root.right != null && root.right.leftHeight()>root.right.rightHeight()){//将右子节点进行右旋转root.right.rightRotate();}//执行左旋转root.leftRotate();}//左子树的高度 - 如果右子树的高度 > 1if (root.leftHeight() - root.rightHeight() > 1){//当左子节点的右子树大于左子树的时候，需要将左子树进行坐旋转if (root.left != null && root.left.rightHeight()>root.left.leftHeight()){//将左子节点进行左旋转root.left.leftRotate();}//执行右旋转root.rightRotate();}}//实现中序遍历public void midTraversal(Node node){if (node == null){return;}//先遍历左子节点midTraversal(node.left);//打印根节点System.out.print(node.value+" ");//再遍历右子节点midTraversal(node.right);}public static final int LEFT = 0;public static final int RIGHT = 1;//实现删除指定结点public void deleteNode(int value){//定义一个游标指针Node node = root;//定义一个目标结点Node target = null;//定义一个target的父类结点Node parent = null;//定义一个结点类型,左结点为0，右节点为1int nodeType = 0;//先进行查找目标元素while (node != null){//当node等于null的时候说明树中没有目标结点if (node.value == value){//找到结点了target = node;break;}else if (value < node.value){parent = node;//先记录node的父节点node = node.left;//node往左下方遍历nodeType = LEFT;}else {parent = node;node = node.right;nodeType = RIGHT;}}//如果target为null，则表示树中没有此节点if (target == null){System.out.println("没有找到要删除的结点");}//删除结点的三种方式，原理有两种，一种是将父类结点的指针指向新的子节点，// 另一种是将一个子节点的值替换掉目标结点，同时删除那个替换的子节点。//1.如果结点是叶子结点，也就是没有子节点的情况if (target.left == null && target.right == null){//如果树只有一个根节点,删除根节点的情况if (parent == null){//将root设置为null即可root = null;return;}//判断目标的结点是左子节点还是右子节点if (nodeType == LEFT){parent.left = null;}else{parent.right = null;}}else if (target.left != null && target.right != null){//2.如果删除的结点有两个子节点的情况//这种情况下，我们可以选择目标结点的左子树中最大的结点替换目标结点，// 也可以选择右子树中最小的结点替换掉目标结点//从target的右子树中查找最小的值Node min = target.right;while (min.left != null){min = min.left;}//将右子树中最小的值的结点删除deleteNode(min.value);//将最小值覆盖到目标结点上，完成目标结点的删除target.value = min.value;}else{//如果删除的是根节点，且根节点只有一个子节点if (parent == null){if (target.left != null){root = target.left;}else {root = target.right;}return;}//3.如果删除的结点只有一个子节点的情况if (nodeType == LEFT){if (target.left != null){//将父类的子节点指向待删除子节点的左子节点parent.left = node.left;}else {//将父类的子节点指向待删除子节点的右子节点parent.left = node.right;}}else {if (target.left != null){//将父类的子节点指向待删除子节点的左子节点parent.right = node.left;}else {//将父类的子节点指向待删除子节点的右子节点parent.right = node.right;}}}}
}
main方法测试：
package Tree.AVLTree;public class TestAVLTree {public static void main(String[] args) {
// int[] arr = {5,6,7,8,9};//右倾斜树，需要左旋
// int[] arr = {9,8,7,6,5};//左倾斜树，需要右旋//右倾斜树，同时右子节点的左子树大于右子树，需要先对子树右旋转再对根节点进行左旋转
// int[] arr = {3,2,6,4,7,5};//左倾斜树，同时左子节点的右子树大于左子树，需要先对子树左旋转再对根节点进行右旋转int[] arr = {11,12,8,7,9,10};AVLTree avl = new AVLTree();//给AVL树赋值，创建一棵二叉树for (int i = 0;i<arr.length;i++){avl.insert(arr[i]);}//使用中序遍历进行顺序输出avl.midTraversal(avl.root);System.out.println();//输出一下整个树的高度System.out.println("树的高度："+avl.root.height());//输出左子树的高度System.out.println("左子树的高度："+avl.root.leftHeight());//输出右子树的高度System.out.println("右子树的高度："+avl.root.rightHeight());}
}
