JAVA数据结构与算法 11.树

4 平衡二叉树

4.1 平衡二叉树介绍

​ 平衡二叉树也叫平衡二叉搜索树，又被称为AVL树，可以保证查询效率较高。具有以下的特点：在二叉排序树的基础上，它是一颗空树或它的左右两颗子树的高度差绝对值不超过1，并且左右两个子树都是一颗平衡二叉树。

问题1：如何构建一颗平衡二叉树？

​ 在构建二叉排序树的时候，每添加一个结点，判断根结点的左右子树的高度差，若大于1，则需要进行相应的处理。

问题2：处理分为哪几种情况，每种情况需要做什么处理？

​ 当当前结点右子树的高度-左子树的高度>1时。此时需要减少右子树的高度，执行左旋转操作。

​ 当左子树的高度-右子树的高度>1时，此时需要减少左子树的高度，执行右旋转操作。

4.2 平衡二叉树的构建操作

4.2.1 左旋转

​ 当当前结点右子树的高度-左子树的高度>1时。此时需要减少右子树的高度，执行左旋转操作。

图解：

原理分析：所谓左旋，就是先将当前结点 T 的右子结点 R 作为新的根结点并指向 T （此时T成为了R的新左子树），再将当前结点 T 的左子树设置为原右子树 R 的左子树 Y。此时左旋结束。

代码思路分析：

创建一个新的结点newNode，值等于当前左旋的二叉树根结点的值 T.value；将新结点 newNode的左子树设置为 T 的 左子树，将newNode的右子树设置为 T 结点 右子树 R 的左子结点 Y ；将当前结点 T 的值换位右子结点 R 的值，并将结点T的右指针，指向当前右子树R的右子树Z；将当前结点T的左指针指向新创建结点newNode；

代码实现：

/** * 对当前结点进行左旋 */ public void leftRotate(){ //此时this 就是 T //1.创建一个新的结点newNode，值等于当前左旋的二叉树根结点的值 T.value， Node newNode = new Node(this.value); //2.将新结点 newNode的左子树设置为 T 的 左子树，将newNode的右子树设置为 T 结点 右子树 R 的左子结点 Y newNode.left = this.left; newNode.right = this.right.left; //3.将当前结点 T 的值换位右子结点 R 的值，并将结点T的右指针，指向当前右子树R的右子树Z this.value = this.right.value; this.right = this.right.right; //4.将当前结点T的左指针指向新创建结点newNode this.left = newNode; }

4.2.2 右旋转

​ 当左子树的高度-右子树的高度>1时，此时需要减少左子树的高度，执行右旋转操作。

图解：

原理分析：所谓右旋，就是先将当前结点 T 的左子结点 L 作为新的根结点并指向 T （此时T成为了L的新右子树），再将当前结点 T 的右子树设置为原左子树 L 的右子树 Y。此时右旋结束。

代码思路分析：实现思路与左旋相同，左右方位相反

代码实现：

public void rightRotate(){ //1.创建一个新的结点newNode，值等于当前右旋的二叉树根结点的值 T.value， Node newNode = new Node(this.value); //2.将新结点 newNode的右子树设置为 T 的 右子树，将newNode的左子树设置为 T 结点 左子树 L 的右子结点 Y newNode.right = this.right; newNode.left = this.left.right; //3.将当前结点 T 的值换位左子结点 L 的值，并将结点T的左指针，指向当前右子树L的右子树X this.value = this.left.value; this.left = this.left.left; //4.将当前结点T的右指针指向新创建结点newNode this.right = newNode; }

4.2.3 双旋转

当满足以下两种情况时，进行一次左旋或者右旋后，树仍然无法保持平衡，此时就需要双旋转：

需要进行左旋（当前结点右子树的高度-左子树的高度>1）时，若【当前结点右子树的左子树高度】大于【当前结点右子树的右子树高度】时，需要先对当前结点的右子树进行右旋，再对当前结点进行左旋；需要进行右旋（当前结点左子树的高度-右子树的高度>1）时，若【当前结点左子树的右子树高度】大于【当前结点左子树的左子树高度】时，需要先对当前结点的左子树进行左旋，再对当前结点进行右旋；

完整代码实现：

public class AVLTreeDemo { public static void main(String args[]){ // int[] arr = {4,3,6,5,7,8}; int[] arr = {10,11,7,6,8,9}; AVLTree avlTree = new AVLTree(); for (int num:arr){ avlTree.addNode(new Node(num)); } avlTree.inOrder(); System.out.println("当前树的高度"+avlTree.root.height());//4 System.out.println(avlTree.root.leftHeight());//1 System.out.println(avlTree.root.rightHeight());//3 } } class AVLTree{ public Node root; public void addNode(Node node){ if(root == null){ root = node; }else { root.add(node); } } public void inOrder(){ if(root == null){ System.out.println("树为空"); return; } root.inOrder(); System.out.println(); } } class Node{ public int value; public Node left; public Node right; public Node(int value) { this.value = value; } @Override public String toString() { return "{" + "value=" + value + '}'; } public void add(Node node){ if(node == null)return; if(node.value < this.value){ //值小于当前节点，向左子树判断 if(this.left == null){ //若左子节点为空，则直接将node添加到左子节点 this.left = node; return; }else { //若不为空则继续向左递归直到找到可以添加的叶子节点为止 this.left.add(node); } }else { if(this.right == null){ //值大于当前节点，向右子树判断 this.right = node; return; }else { this.right.add(node); } } //添加结束后调整二叉树的平衡 if((this.rightHeight() - this.leftHeight()) >1){ //特殊的情况：(当前结点的右子树的左子树的高度) 大于 (当前结点右子树右子树的高度)，需要先对当前结点的右子树进行右旋，再对该节点进行左旋 if(this.right!= null && this.right.leftHeight() > this.right.rightHeight()){ this.right.rightRotate(); } this.leftRotate(); return; } if((this.leftHeight() - this.rightHeight()) >1){ //特殊的情况：(当前结点的左子树的右子树的高度) 大于 (当前结点左子树左子树的高度)，需要先对当前结点的左子树进行左旋，再对该节点进行右旋 if(this.left!= null &&this.left.rightHeight() > this.left.leftHeight()){ this.left.leftRotate(); } this.rightRotate(); return; } } //中序遍历 public void inOrder(){ if(this.left != null) this.left.inOrder(); System.out.print(this+"=>"); if(this.right != null) this.right.inOrder(); } /** * 返回以当前结点为根结点的树的高度 * @return */ public int height(){ return Math.max(this.left == null ?0 :this.left.height(),this.right == null ? 0:this.right.height())+1; } public int leftHeight(){ if(this.left == null) return 0; return this.left.height(); } public int rightHeight(){ if(this.right == null) return 0; return this.right.height(); } /** * 对当前结点进行左旋 */ public void leftRotate(){ //此时this 就是 T //1.创建一个新的结点newNode，值等于当前左旋的二叉树根结点的值 T.value， Node newNode = new Node(this.value); //2.将新结点 newNode的左子树设置为 T 的 左子树，将newNode的右子树设置为 T 结点 右子树 R 的左子结点 Y newNode.left = this.left; newNode.right = this.right.left; //3.将当前结点 T 的值换位右子结点 R 的值，并将结点T的右指针，指向当前右子树R的右子树Z this.value = this.right.value; this.right = this.right.right; //4.将当前结点T的左指针指向新创建结点newNode this.left = newNode; } public void rightRotate(){ //1.创建一个新的结点newNode，值等于当前右旋的二叉树根结点的值 T.value， Node newNode = new Node(this.value); //2.将新结点 newNode的右子树设置为 T 的 右子树，将newNode的左子树设置为 T 结点 左子树 L 的右子结点 Y newNode.right = this.right; newNode.left = this.left.right; //3.将当前结点 T 的值换位左子结点 L 的值，并将结点T的左指针，指向当前右子树L的右子树X this.value = this.left.value; this.left = this.left.left; //4.将当前结点T的右指针指向新创建结点newNode this.right = newNode; } }