一篇文章，带你快速读懂~数据结构之平衡查找树 _平衡查找树

平衡查找树AVL树在计算机科学中，AVL树是最先发明的自平衡二叉查找树。在AVL树中任何节点的两个子树的高度最大差别为1，所以它也被称为高度平衡树。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。
特点AVL树本质上还是一棵二叉搜索树，它的特点是： [1]
1.本身首先是一棵二叉搜索树。
2.带有平衡条件：每个结点的左右子树的高度之差的绝对值（平衡因子）最多为1 。
也就是说，AVL树，本质上是带了平衡功能的二叉查找树（二叉排序树，二叉搜索树）。
单旋转右旋转

文章插图

思路分析：
1、回溯找到失去平衡的节点，以该节点为根，创建一个新节点
2、把新节点的右子树设置为当前节点的右子树
3、把新节点的左子树设置为当前节点的左子树的右子树
4、把当前节点的值换为左子节点的值
5、把当前节点的左子树设置为左子树的左子树
6、把当前节点的右子树设置为新节点

【一篇文章，带你快速读懂~数据结构之平衡查找树】代码实现：
/*** @Title: rotateRight* @Description:右旋操作*1、回溯找到失去平衡的节点，以该节点为根，创建一个新节点*2、把新节点的右子树设置为当前节点的右子树*3、把新节点的左子树设置为当前节点的左子树的右子树*4、把当前节点的值换位左子节点的值*5、把当前节点的左子树设置为左子树的左子树*6、把当前节点的右子树设置为新节点* @param:* @return: void* @throws*/private void rotateRight() {//1、回溯找到失去平衡的节点，以该节点为根，创建一个新节点Node tempNode = new Node(data);//2、把新节点的右子树设置为当前节点的右子树tempNode.right = right;//3、把新节点的左子树设置为当前节点的左子树的右子树tempNode.left = left.right;//4、把当前节点的值换位左子节点的值data = https://www.isolves.com/it/cxkf/jiagou/2019-12-16/left.data;//5、把当前节点的左子树设置为左子树的左子树left = left.left;//6、把当前节点的右子树设置为新节点right = tempNode;}
左旋转

文章插图

思路分析：
1、回溯找到失去平衡的节点，以该节点为根，创建一个新节点
2、把新节点的左子树设置为当前节点的左子树
3、把新节点的右子树设置为当前节点的右子树的左子树
4、把当前节点的值替换为右子节点的值
5、把当前节点的右子树设置为右子树的右子树
6、把当前节点的左子树设置为新节点

代码实现：
/*** @Title: rotateLeft* @Description:左旋操作：*1、回溯找到失去平衡的节点，以该节点为根，创建一个新节点*2、把新节点的左子树设置为当前节点的左子树*3、把新节点的右子树设置为当前节点的右子树的左子树*4、把当前节点的值替换为右子节点的值*5、把当前节点的右子树设置为右子树的右子树*6、把当前节点的左子树设置为新节点* @param:* @return: void* @throws*/private void rotateLeft() {System.out.println("旋转代码中的 data = https://www.isolves.com/it/cxkf/jiagou/2019-12-16/" + data);//以根节点为参考，创建新的节点Node tempNode = new Node(data);//把新节点的左子树设置为当前节点的左子树tempNode.setLeft(left);//把新节点的右子树设置为当前节点的右子树的左子树tempNode.setRight(right.left);//把当前节点的值替换为右子树的值data = right.data;//把当前节点的右子树设置为当前节点右子树的右子树right = right.right;//把当前节点的左子树设置为新节点left = tempNode;}
双旋转右-左双旋转

文章插图

//先对当前节点的右孩子右旋
right.rotateRight();
//再进行左旋操作
rotateLeft();

左-右双旋转

文章插图

文章插图

//先对当前节点的左孩子进行左旋
left.rotateLeft();
//再进行右旋
rotateRight();
实现
平衡二叉树实现增加旋转功能完整代码如下：
/*** All rights Reserved, Designed By https://www.tulingxueyuan.com/ * @Title:AVLTree.JAVA* @Package com.tuling.tree* @Description:* @author: 小白* @Date 2019年12月8日下午10:09:37* @version V1.0* @Copyright:*/ package com.tuling.tree;/** * @ClassName AVLTree * @Description* @Author 北京图灵学院 * @Date 2019年12月8日下午10:09:37 */public class AVLTree {private Node root;/**** @Title: add* @Description:* @param: @param data* @return: void* @throws*/ public void add(int data) {System.out.print("当前添加数据：" + data + "");if(root == null) {root = new Node(data);}else {root.add(data);} }/*** @Title: rotateLeft* @Description:左旋操作* @param: node* @return: void* @throws*/ private Node rotateLeft(Node nodeN) {Node nodeC = nodeN.getRight();nodeN.setRight(nodeC.getLeft());nodeC.setLeft(nodeN);return nodeC; }public void inFixOrder() {if(root == null) {System.out.println("树为空！");}else {root.inFixOrder();} } public Node getRoot() {return root; } public void setRoot(Node root) {this.root = root; } class Node{private Node left,right;private int data;/*** @Title:Node* @Description:* @param:@param data* @throws*/public Node(int data) {this.data = https://www.isolves.com/it/cxkf/jiagou/2019-12-16/data;}/*** @Title: add* @Description:* @param: data* @return: void* @throws*/public void add(int data) {if(this.data > data) {if(this.left == null) {this.left = new Node(data);}else {this.left.add(data);}}else if(this.data