数据结构树和图讲解：五分钟一篇文章

数据结构树和图讲解：五分钟一篇文章2、把新节点的右子树设置为当前节点的右子树1、回溯找到失去平衡的节点，以该节点为根，创建一个新节点也就是说，AVL树，本质上是带了平衡功能的二叉查找树（二叉排序树，二叉搜索树）。思路分析：

平衡查找树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; } } }