一篇文章，带你快速读懂~数据结构之平衡查找树
平衡查找树
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 = 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 = " + 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 = 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 < data) {
if(this.right == null) {
this.right = new Node(data);
}else {
this.right.add(data);
}
}
//TODO:
//做完添加操作，
if(leftHeight() - rightHeight() > 1) {//如果左子树的高度大于右子树的高度，需要右旋操作。
if(left!=null && this.left.rightHeight()>left.leftHeight()) {
System.out.print("左旋再右旋 -- " + left.data);
//先对当前节点的左孩子进行左旋
left.rotateLeft();
//再进行右旋
rotateRight();
}else {
System.out.print("右旋" + data);
//直接右旋即可
rotateRight();
}
}
if(rightHeight() - leftHeight() > 1) {//如果右子树的高度大于左子树的高度，需要左旋操作
if(right!=null && right.leftHeight()>right.rightHeight()) {
System.out.print("右旋再左旋 -- " + right.data );
//先对象当前节点的右孩子右旋
right.rotateRight();
//再进行左旋操作
rotateLeft();
}else {
System.out.print("左旋 -- " + data);
//直接左旋节课
rotateLeft();
}
}
}
/**
* @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 = left.data;
//5、把当前节点的左子树设置为左子树的左子树
left = left.left;
//6、把当前节点的右子树设置为新节点
right = tempNode;
}
/**
* @Title: rotateLeft
* @Description:左旋操作：
* 1、回溯找到失去平衡的节点，以该节点为根，创建一个新节点
* 2、把新节点的左子树设置为当前节点的左子树
* 3、把新节点的右子树设置为当前节点的右子树的左子树
* 4、把当前节点的值替换为右子节点的值
* 5、把当前节点的右子树设置为右子树的右子树
* 6、把当前节点的左子树设置为新节点
* @param:
* @return: void
* @throws
*/
private void rotateLeft() {
System.out.println("旋转代码中的 data = " + data);
//以根节点为参考，创建新的节点
Node tempNode = new Node(data);
//把新节点的左子树设置为当前节点的左子树
tempNode.setLeft(left);
//把新节点的右子树设置为当前节点的右子树的左子树
tempNode.setRight(right.left);
//把当前节点的值替换为右子树的值
data = right.data;
//把当前节点的右子树设置为当前节点右子树的右子树
right = right.right;
//把当前节点的左子树设置为新节点
left = tempNode;
}
/**
* @Title: rightHeight
* @Description:
* @param: @return
* @return: int
* @throws
*/
private int rightHeight() {
if(right == null) {
return 0;
}
return height(right);
}
/**
* @Title: height
* @Description:
* @param:
* @return: int
* @throws
*/
private int height(Node node) {
if(node == null) return 0;
return 1+Math.max(height(node.left), height(node.right));
}
/**
* @Title: leftHeight
* @Description:
* @param: @return
* @return: int
* @throws
*/
private int leftHeight() {
if(left == null)return 0;
return height(left);
}
/**
* @Title: inFixOrder
* @Description:
* @param:
* @return: void
* @throws
*/
public void inFixOrder() {
if(this.left!=null) {
this.left.inFixOrder();
}
System.out.println(this.data);
if(this.right!=null) {
this.right.inFixOrder();
}
}
public Node getLeft() {
return left;
}
public void setLeft(Node left) {
this.left = left;
}
public Node getRight() {
return right;
}
public void setRight(Node right) {
this.right = right;
}
public int getData() {
return data;
}
public void setData(int data) {
this.data = data;
}
}
}