二叉平衡树左右双旋(思维导图大纲+图解 看不懂来砍我！！！)

二叉平衡树左右双旋(思维导图大纲+图解 看不懂来砍我！！！)

文章目录

• • 为什么要使用二叉平衡树？
  • 平衡树的定义
  • 思路大纲
  • • 节点类
    • AVL树类
  • 什么时候需要左旋？
  • 什么时候需要右旋
  • 为什么要双旋？
  • 测试双旋方法
  • • 完整代码放上

为什么要使用二叉平衡树？

为了降低树的高度 避免出现树退化成数组的形式
如这样

平衡树的定义

划重点
任意节点的子树的高度差都小于等于1
任意节点的子树的高度差都小于等于1
任意节点的子树的高度差都小于等于1

如果超过1 即为不平衡树 需要旋转了

思路大纲

图片保存下做个笔记哦

先看一下这两个类 为后面做准备

节点类

方法：

1. 获取树的高度(重点掌握 递归求树的高度)
2. 获取左子树高度
3. 获取右子树高度
4. 根据value值插入结点方法
5. 遍历方法

获取树的高度

class Node {Node left;Node right;int value;/*** 获取树的高度*/public int getHeight() {return Math.max(left == null ? 0 : Height(), right == null ? 0 : Height()) + 1;}/*** 左子树可能为空** @return*/public int leftHeight() {if (left == null) {return 0;} else {Height();}}/*** 右子树可能为空** @return*/public int rightHeight() {if (right == null) {return 0;} else {Height();}}/*** 插入方法 判断插入的元素比根节点大还是小 小放左边 大放右边 为空直接作为根节点** @param node 待插入的节点*/public void add(Node node) {if (node == null) {return;}if (node.value < this.value) {//放左边if (this.left == null) {this.left = node;} else {this.left.add(node);}} else {//相等或大于就放右边if (this.right == null) {this.right = node;} else {this.right.add(node);}}}/*** 前序遍历方法*/public void preface() {System.out.print(this.value + " ");if (this.left != null) {this.left.preface();}if (this.right != null) {this.right.preface();}}/*** 中序遍历方法*/public void midface() {if (this.left != null) {this.left.midface();}System.out.print(this.value + " ");if (this.right != null) {this.right.midface();}}public Node(int value) {this.value = value;}@Overridepublic String toString() {return "Node{" +"value=" + value +'}';}
}

AVL树类

一系列遍历方法 重点放在节点类里

class AvlTree {Node root;/*** 二叉树添加节点方法 为空直接替换根节点** @param node*/public void add(Node node) {if (root == null) {root = node;} else {root.add(node);}}/*** 中序遍历树*/public void midlist() {if (root != null) {root.midface();System.out.println();}}/*** 前序遍历树*/public void prelist() {if (root != null) {root.preface();System.out.println();}}}

什么时候需要左旋？

如图 在没添加8节点前 还是一个平衡树 但添加过后

此时我们看到左子树的高度为1 右子树的高度为3

也就是右子树高度-左子树高度>1 超过1个单位时 我们就需要往左旋转 来保持平衡了

思路截一下图

配合图一起看

    /*** 左旋方法*/public void leftRotate() {Node newnode = new Node(value);//将新节点左子树设置为当前节点左子树newnode.left = left;//新节点右子树设置为当前节点右子树的左子树newnode.right = right.left;//root的值替换为他的右子节点的值value = right.value;//root的右边指向右子树的右子节点right = right.right;//root的左边指向新节点newnodeleft = newnode;}

注意 我们左旋方法的添加是在节点添加方法里实现的

即 每添加一个节点 就判断左右树的高度 所以不用担心后面的子树 子树的子树之类的情况哦！

左旋过后 该树平衡

	//add方法添加左旋代码//计算左子树的高度int l = leftHeight();//计算右子树的高度int r = rightHeight();//当他们高度相差2时 就需要旋转if (l - r > 1) {leftRotate();}

什么时候需要右旋

看图 此时添加6 该树不平衡了

也就是左子树高度-右子树高度>1 超过1个单位时 我们就需要往右旋转 来保持平衡了

/*** 右旋方法*/public void rightRotate() {Node newnode = new Node(value);newnode.right = right;newnode.left = left.right;value = left.value;left = left.left;right = newnode;}

同样的 也要在add方法里添加判断的条件

为什么要双旋？

看图

我们可以数一数 新的左右子树的 高度 发现是左边为3 右边为1 明显相差2 所以就引出了双旋

我们以10为根节点 判断如果左子树大于右子树 则右旋 否则左旋

这是整个add方法的步骤

  /*** 插入方法 判断插入的元素比根节点大还是小 小放左边 大放右边 为空直接作为根节点** @param node 待插入的节点*/public void add(Node node) {if (node == null) {return;}if (node.value < this.value) {//放左边if (this.left == null) {this.left = node;} else {this.left.add(node);}} else {//相等或大于就放右边if (this.right == null) {this.right = node;} else {this.right.add(node);}}//计算左子树的高度int l = leftHeight();//计算右子树的高度int r = rightHeight();//当他们高度相差2时 就需要旋转if (l - r > 1) {//双旋的情况 左子树的左子树的高度小于左子树的右子树的高度if (left.leftHeight() < left.rightHeight()) {//要将左子树左旋 再将整个树右旋left.leftRotate();rightRotate();} else {rightRotate();}}if (r - l > 1) {//双旋的情况 右子树的左子树的高度大于右子树的左子树的高度if (right.leftHeight() > right.rightHeight()) {//要将右子树右旋 再将整个树左旋right.rightRotate();leftRotate();} else {leftRotate();}}}

测试双旋方法

//对双旋做个测试  写入public static void main(String[] args) {int[] arr = {7, 6, 10, 9, 8, 11};AvlTree tree = new AvlTree();for (int i : arr) {tree.add(new Node(i));}System.out.println("整个树的高度为"&#etHeight());System.out.println("左子树高度为"&#leftHeight());System.out.println("右子树高度为"&#ightHeight());//前序tree.prelist();//中序tree.midlist();}
}

打印结果

整个树的高度为3
左子树高度为2
右子树高度为2
9 7 6 8 10 11
6 7 8 9 10 11

完整代码放上

package cn.bb.study;/*** @program: datastructure* @description: 平衡二叉树* @author: sharpbb* @create: 2020-10-29 08:11**/public class Demo {
//对双旋做个测试  写入public static void main(String[] args) {int[] arr = {7, 6, 10, 9, 8, 11};AvlTree tree = new AvlTree();for (int i : arr) {tree.add(new Node(i));}System.out.println("整个树的高度为"&#etHeight());System.out.println("左子树高度为"&#leftHeight());System.out.println("右子树高度为"&#ightHeight());//前序tree.prelist();//中序tree.midlist();}
}class AvlTree {Node root;/*** 二叉树添加节点方法 为空直接替换根节点** @param node*/public void add(Node node) {if (root == null) {root = node;} else {root.add(node);}}/*** 中序遍历树*/public void midlist() {if (root != null) {root.midface();System.out.println();}}/*** 前序遍历树*/public void prelist() {if (root != null) {root.preface();System.out.println();}}}class Node {Node left;Node right;int value;/*** 左旋方法*/public void leftRotate() {Node newnode = new Node(value);//将新节点左子树设置为当前节点左子树newnode.left = left;//新节点右子树设置为当前节点右子树的左子树newnode.right = right.left;value = right.value;right = right.right;left = newnode;}/*** 右旋方法*/public void rightRotate() {Node newnode = new Node(value);newnode.right = right;newnode.left = left.right;value = left.value;left = left.left;right = newnode;}/*** 左子树可能为空** @return*/public int leftHeight() {if (left == null) {return 0;} else {Height();}}/*** 右子树可能为空** @return*/public int rightHeight() {if (right == null) {return 0;} else {Height();}}/*** 获取树的高度*/public int getHeight() {return Math.max(left == null ? 0 : Height(), right == null ? 0 : Height()) + 1;}/*** 插入方法 判断插入的元素比根节点大还是小 小放左边 大放右边 为空直接作为根节点** @param node 待插入的节点*/public void add(Node node) {if (node == null) {return;}if (node.value < this.value) {//放左边if (this.left == null) {this.left = node;} else {this.left.add(node);}} else {//相等或大于就放右边if (this.right == null) {this.right = node;} else {this.right.add(node);}}//计算左子树的高度int l = leftHeight();//计算右子树的高度int r = rightHeight();//当他们高度相差2时 就需要旋转if (l - r > 1) {//双旋的情况 左子树的左子树的高度小于左子树的右子树的高度if (left.leftHeight() < left.rightHeight()) {//要将左子树左旋 再将整个树右旋left.leftRotate();rightRotate();} else {rightRotate();}}if (r - l > 1) {//双旋的情况 右子树的左子树的高度大于右子树的左子树的高度if (right.leftHeight() > right.rightHeight()) {//要将右子树右旋 再将整个树左旋right.rightRotate();leftRotate();} else {leftRotate();}}}/*** 前序遍历方法*/public void preface() {System.out.print(this.value + " ");if (this.left != null) {this.left.preface();}if (this.right != null) {this.right.preface();}}/*** 中序遍历方法*/public void midface() {if (this.left != null) {this.left.midface();}System.out.print(this.value + " ");if (this.right != null) {this.right.midface();}}public Node(int value) {this.value = value;}@Overridepublic String toString() {return "Node{" +"value=" + value +'}';}
}

ps：要多想 在那以前要多想