一篇文章，带你快速读懂~数据结构之平衡查找树
2019-12-16
加入收藏
平衡查找树
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; } } }
