AVL树详解

1. 简介2. 插入2.1 单向右旋平衡处理LL2.2 单向左旋平衡处理RR2.3 双向旋转（先左后右）平衡处理LR2.4 双向旋转（先右后左）平衡处理RL 3. 删除4 java代码例子

相关文章链接：

相关文章链接 第2节 数据结构

观前提示：

本文所使用的Eclipse版本为Photon Release (4.8.0)，IDEA版本为ultimate 2019.1，JDK版本为1.8.0_141，Tomcat版本为9.0.12。

1. 简介

AVL树是最先发明的自平衡二叉查找树。在AVL树中任何节点的两个子树的高度最大差别为1，所以它也被称为高度平衡树。

特点

本身首先是一棵二叉搜索树。

带有平衡条件：每个结点的左右子树的高度之差的绝对值（平衡因子）最多为1。

平衡因子： 某结点的左子树与右子树的高度(深度)差即为该结点的平衡因子（BF,Balance Factor）。平衡二叉树上所有结点的平衡因子只可能是 -1，0 或 1。

2. 插入

这里只介绍插入节点后破坏平衡所做的旋转操作。

2.1 单向右旋平衡处理LL

在左子树（L）的左孩子（L）插入节点失衡，需要进行单向右旋平衡处理LL。

2.2 单向左旋平衡处理RR

在右子树（R）的右孩子（R）插入节点失衡，需要进行单向左旋平衡处理RR。

2.3 双向旋转（先左后右）平衡处理LR

在左子树（L）的右孩子（R）插入节点失衡，需要进行双向旋转（先左后右）平衡处理LR。

2.4 双向旋转（先右后左）平衡处理RL

在右子树（R）的左孩子（L）插入节点失衡，需要进行双向旋转（先右后左）平衡处理RL。

3. 删除

AVL树删除操作步骤如下

搜索给定的key，确定其是否在树中。

如果不在树中，返回null；如果在树中，执行标准的BST删除操作，并返回该删除的结点。

检查被删除结点的所有祖先结点是否平衡，如果不平衡，则执行重平衡操作。

BST删除操作三种情况

当该节点为叶子节点，则让该节点的父节点指向其变为NULL，然后释放节点。

当该节点不是叶子节点，但左子树或者右子树为空，则： （1）若左子树为空，则让该节点父节点指向其右节点。 （2）若右子树为空，则让该节点父节点指向其左节点。

当该节点不是叶子节点，且左子树和右子树都不为空，则： （1）在该节点的左子树中找到最大节点Lmax（该节点必然是一个叶子节点）或者右子树中的最小节点Rmin，取出节点的值value，并删除该节点。 （2）将value的值赋到要删除的节点。

4 java代码例子

AVL树 AVLTree.java

package TestTree.AVL; public class AVLTree { private Integer root; private AVLTree left; private AVLTree right; private Integer height; public AVLTree(Integer root) { this.root = root; } public Integer getRoot() { return root; } public void setRoot(Integer root) { this.root = root; } public AVLTree getLeft() { return left; } public void setLeft(AVLTree left) { this.left = left; } public AVLTree getRight() { return right; } public void setRight(AVLTree right) { this.right = right; } public Integer getHeight() { return height; } /** * 获取指定节点深度 * @param node * @return */ public static Integer getHeight(AVLTree node){ if(node == null){ return 0; } return node.height; } public void setHeight(Integer height) { this.height = height; } /** * 指定节点深度赋值 * @param node * @param height */ public static void setHeight(AVLTree node, Integer height) { if(node == null){ return; } node.height = height; } /** * 获取最小节点 * @param node * @return */ public static AVLTree getMinNode(AVLTree node){ if(node != null && node.getLeft() == null){ return node; } return getMinNode(node.getLeft()); } }

树操作工具类 TreeOperateUtil.java

package TestTree.AVL; /** * 树操作工具类 * @author jjy * @date 2020-10-19 */ public class TreeOperateUtil { /** * 插入节点 * @param node * @param data * @return */ public static AVLTree insert(AVLTree node, int data){ // 根节点没有数据，直接插入 if(node == null || node.getRoot() == null){ node = new AVLTree(data); node.setHeight(1); return node; } if(node.getRoot() > data){ node.setLeft(insert(node.getLeft(), data)); } else { node.setRight(insert(node.getRight(), data)); } // 更新深度 node.setHeight(1 + Math.max(AVLTree.getHeight(node.getLeft()), AVLTree.getHeight(node.getRight()))); int balanceFactor = getBalanceFactor(node); // LL if(balanceFactor == 2 && getBalanceFactor(node.getLeft()) > 0 ){ System.out.println("-------------LL旋转-------------"); return LLRotate(node); } // LR if(balanceFactor == 2 && getBalanceFactor(node.getLeft()) < 0){ System.out.println("-------------LR旋转-------------"); return LRRotate(node); } // RR if(balanceFactor == -2 && getBalanceFactor(node.getRight()) < 0){ System.out.println("-------------RR旋转-------------"); return RRRotate(node); } // RL if(balanceFactor == -2 && getBalanceFactor(node.getRight()) > 0){ System.out.println("-------------RL旋转-------------"); return RLRotate(node); } return node; } /** * 删除节点 * @param node * @param data * @return */ public static AVLTree remove(AVLTree node, int data){ if(node == null){ return null; } if(node.getRoot() > data){ node.setLeft(remove(node.getLeft(), data)); } else if( node.getRoot() < data){ node.setRight(remove(node.getRight(), data)); } else { if(node.getLeft() == null) { // 没有左子树 node = node.getRight(); } else if(node.getRight() == null) { // 没有右子树 node = node.getLeft(); } else { // 左右子树均不为空，取右子树最小值（或者左子树最大值），替换当前要删除的节点 AVLTree minNode = AVLTree.getMinNode(node.getRight()); node.setRight(remove(node.getRight(), minNode.getRoot())); node.setRoot(minNode.getRoot()); } } // 只有根节点，删除后为空 if(node == null){ return null; } // 更新深度 node.setHeight(1 + Math.max(AVLTree.getHeight(node.getLeft()), AVLTree.getHeight(node.getRight()))); int balanceFactor = getBalanceFactor(node); // LL if(balanceFactor == 2 && getBalanceFactor(node.getLeft()) > 0 ){ System.out.println("-------------LL旋转-------------"); return LLRotate(node); } // LR if(balanceFactor == 2 && getBalanceFactor(node.getLeft()) < 0){ System.out.println("-------------LR旋转-------------"); return LRRotate(node); } // RR if(balanceFactor == -2 && getBalanceFactor(node.getRight()) < 0){ System.out.println("-------------RR旋转-------------"); return RRRotate(node); } // RL if(balanceFactor == -2 && getBalanceFactor(node.getRight()) > 0){ System.out.println("-------------RL旋转-------------"); return RLRotate(node); } return node; } /** * LL旋转 * @param node * @return */ private static AVLTree LLRotate(AVLTree node){ AVLTree result = node.getLeft(); node.setLeft(result.getRight()); result.setRight(node); AVLTree.setHeight(result.getLeft(), getTreeDepth(result.getLeft())); AVLTree.setHeight(result.getRight(), getTreeDepth(result.getRight())); AVLTree.setHeight(result, getTreeDepth(result)); return result; } /** * RR旋转 * @param node * @return */ private static AVLTree RRRotate(AVLTree node){ AVLTree result = node.getRight(); node.setRight(result.getLeft()); result.setLeft(node); AVLTree.setHeight(result.getLeft(), getTreeDepth(result.getLeft())); AVLTree.setHeight(result.getRight(), getTreeDepth(result.getRight())); AVLTree.setHeight(result, getTreeDepth(result)); return result; } /** * LR旋转 * @param node * @return */ private static AVLTree LRRotate(AVLTree node){ node.setLeft(RRRotate(node.getLeft())); return LLRotate(node); } /** * RL旋转 * @param node * @return */ private static AVLTree RLRotate(AVLTree node){ node.setRight(LLRotate(node.getRight())); return RRRotate(node); } /** * 获取平衡因子 * @param node * @return */ private static int getBalanceFactor(AVLTree node){ return AVLTree.getHeight(node.getLeft()) - AVLTree.getHeight(node.getRight()); } /** * 获取树的深度 * @param node * @return */ private static int getTreeDepth(AVLTree node){ if(node == null || node.getRoot() == null){ return 0; } AVLTree left = node.getLeft(); AVLTree right = node.getRight(); return Math.max(getTreeDepth(left), getTreeDepth(right)) + 1; } }

测试类 TestAVL.java

package TestTree.AVL; import java.util.Arrays; import java.util.List; public class TestAVL { public static void main(String[] args) { System.out.println("-------------插入操作-------------"); testInsert(); System.out.println("-------------第一组删除操作-------------"); testDelete(); System.out.println("-------------第二组删除操作-------------"); testDelete2(); } /** * 测试插入节点 */ private static void testInsert(){ AVLTree t1 = getTestData(); System.out.println("-------------插入前-------------"); TraversalUtil.init(); List<Integer> preList = TraversalUtil.preOrder(t1); System.out.println("先序排列结果为："); System.out.println(Arrays.toString(preList.toArray())); TraversalUtil.init(); List<Integer> inList = TraversalUtil.inOrder(t1); System.out.println("中序排列结果为："); System.out.println(Arrays.toString(inList.toArray())); TraversalUtil.init(); List<Integer> postList = TraversalUtil.postOrder(t1); System.out.println("后序排列结果为："); System.out.println(Arrays.toString(postList.toArray())); System.out.println("-------------1.插入70-------------"); t1 = TreeOperateUtil.insert(t1, 70); TraversalUtil.init(); preList = TraversalUtil.preOrder(t1); System.out.println("先序排列结果为："); System.out.println(Arrays.toString(preList.toArray())); TraversalUtil.init(); inList = TraversalUtil.inOrder(t1); System.out.println("中序排列结果为："); System.out.println(Arrays.toString(inList.toArray())); TraversalUtil.init(); postList = TraversalUtil.postOrder(t1); System.out.println("后序排列结果为："); System.out.println(Arrays.toString(postList.toArray())); t1 = getTestData(); System.out.println("-------------2.插入130-------------"); t1 = TreeOperateUtil.insert(t1, 130); TraversalUtil.init(); preList = TraversalUtil.preOrder(t1); System.out.println("先序排列结果为："); System.out.println(Arrays.toString(preList.toArray())); TraversalUtil.init(); inList = TraversalUtil.inOrder(t1); System.out.println("中序排列结果为："); System.out.println(Arrays.toString(inList.toArray())); TraversalUtil.init(); postList = TraversalUtil.postOrder(t1); System.out.println("后序排列结果为："); System.out.println(Arrays.toString(postList.toArray())); t1 = getTestData(); System.out.println("-------------3.插入85-------------"); t1 = TreeOperateUtil.insert(t1, 85); TraversalUtil.init(); preList = TraversalUtil.preOrder(t1); System.out.println("先序排列结果为："); System.out.println(Arrays.toString(preList.toArray())); TraversalUtil.init(); inList = TraversalUtil.inOrder(t1); System.out.println("中序排列结果为："); System.out.println(Arrays.toString(inList.toArray())); TraversalUtil.init(); postList = TraversalUtil.postOrder(t1); System.out.println("后序排列结果为："); System.out.println(Arrays.toString(postList.toArray())); t1 = getTestData(); System.out.println("-------------4.插入115-------------"); t1 = TreeOperateUtil.insert(t1, 115); TraversalUtil.init(); preList = TraversalUtil.preOrder(t1); System.out.println("先序排列结果为："); System.out.println(Arrays.toString(preList.toArray())); TraversalUtil.init(); inList = TraversalUtil.inOrder(t1); System.out.println("中序排列结果为："); System.out.println(Arrays.toString(inList.toArray())); TraversalUtil.init(); postList = TraversalUtil.postOrder(t1); System.out.println("后序排列结果为："); System.out.println(Arrays.toString(postList.toArray())); } /** * 测试数据 * 100 * / \ * 90 110 * / \ * 80 120 * @return */ private static AVLTree getTestData(){ AVLTree t1 = new AVLTree(100); AVLTree t2 = new AVLTree(90); AVLTree t3 = new AVLTree(110); AVLTree t4 = new AVLTree(80); AVLTree t5 = new AVLTree(120); t3.setHeight(1); t4.setHeight(1); t5.setHeight(1); t2.setLeft(t4); t2.setHeight(2); t3.setRight(t5); t2.setHeight(2); t1.setLeft(t2); t1.setRight(t3); t1.setHeight(3); return t1; } /** * 测试删除节点 */ private static void testDelete(){ AVLTree t1 = getTestDeleteData1(); System.out.println("-------------删除前-------------"); TraversalUtil.init(); List<Integer> preList = TraversalUtil.preOrder(t1); System.out.println("先序排列结果为："); System.out.println(Arrays.toString(preList.toArray())); TraversalUtil.init(); List<Integer> inList = TraversalUtil.inOrder(t1); System.out.println("中序排列结果为："); System.out.println(Arrays.toString(inList.toArray())); TraversalUtil.init(); List<Integer> postList = TraversalUtil.postOrder(t1); System.out.println("后序排列结果为："); System.out.println(Arrays.toString(postList.toArray())); System.out.println("-------------1.删除80-------------"); t1 = TreeOperateUtil.remove(t1, 80); TraversalUtil.init(); preList = TraversalUtil.preOrder(t1); System.out.println("先序排列结果为："); System.out.println(Arrays.toString(preList.toArray())); TraversalUtil.init(); inList = TraversalUtil.inOrder(t1); System.out.println("中序排列结果为："); System.out.println(Arrays.toString(inList.toArray())); TraversalUtil.init(); postList = TraversalUtil.postOrder(t1); System.out.println("后序排列结果为："); System.out.println(Arrays.toString(postList.toArray())); t1 = getTestDeleteData1(); System.out.println("-------------2.删除120-------------"); t1 = TreeOperateUtil.remove(t1, 120); TraversalUtil.init(); preList = TraversalUtil.preOrder(t1); System.out.println("先序排列结果为："); System.out.println(Arrays.toString(preList.toArray())); TraversalUtil.init(); inList = TraversalUtil.inOrder(t1); System.out.println("中序排列结果为："); System.out.println(Arrays.toString(inList.toArray())); TraversalUtil.init(); postList = TraversalUtil.postOrder(t1); System.out.println("后序排列结果为："); System.out.println(Arrays.toString(postList.toArray())); t1 = getTestDeleteData1(); System.out.println("-------------3.删除95-------------"); t1 = TreeOperateUtil.remove(t1, 95); TraversalUtil.init(); preList = TraversalUtil.preOrder(t1); System.out.println("先序排列结果为："); System.out.println(Arrays.toString(preList.toArray())); TraversalUtil.init(); inList = TraversalUtil.inOrder(t1); System.out.println("中序排列结果为："); System.out.println(Arrays.toString(inList.toArray())); TraversalUtil.init(); postList = TraversalUtil.postOrder(t1); System.out.println("后序排列结果为："); System.out.println(Arrays.toString(postList.toArray())); t1 = getTestDeleteData1(); System.out.println("-------------4.删除105-------------"); t1 = TreeOperateUtil.remove(t1, 105); TraversalUtil.init(); preList = TraversalUtil.preOrder(t1); System.out.println("先序排列结果为："); System.out.println(Arrays.toString(preList.toArray())); TraversalUtil.init(); inList = TraversalUtil.inOrder(t1); System.out.println("中序排列结果为："); System.out.println(Arrays.toString(inList.toArray())); TraversalUtil.init(); postList = TraversalUtil.postOrder(t1); System.out.println("后序排列结果为："); System.out.println(Arrays.toString(postList.toArray())); t1 = getTestDeleteData1(); System.out.println("-------------5.删除100-------------"); t1 = TreeOperateUtil.remove(t1, 100); TraversalUtil.init(); preList = TraversalUtil.preOrder(t1); System.out.println("先序排列结果为："); System.out.println(Arrays.toString(preList.toArray())); TraversalUtil.init(); inList = TraversalUtil.inOrder(t1); System.out.println("中序排列结果为："); System.out.println(Arrays.toString(inList.toArray())); TraversalUtil.init(); postList = TraversalUtil.postOrder(t1); System.out.println("后序排列结果为："); System.out.println(Arrays.toString(postList.toArray())); } /** * 测试数据 * 100 * / \ * 90 110 * / \ / \ * 80 95 105 120 * / \ * 70 130 * @return */ private static AVLTree getTestDeleteData1(){ AVLTree t1 = new AVLTree(100); AVLTree t2 = new AVLTree(90); AVLTree t3 = new AVLTree(110); AVLTree t4 = new AVLTree(80); AVLTree t5 = new AVLTree(95); AVLTree t6 = new AVLTree(105); AVLTree t7 = new AVLTree(120); AVLTree t8 = new AVLTree(70); AVLTree t9 = new AVLTree(130); t5.setHeight(1); t6.setHeight(1); t8.setHeight(1); t9.setHeight(1); t4.setLeft(t8); t4.setHeight(2); t7.setRight(t9); t7.setHeight(2); t2.setLeft(t4); t2.setRight(t5); t2.setHeight(3); t3.setLeft(t6); t3.setRight(t7); t3.setHeight(3); t1.setLeft(t2); t1.setRight(t3); t1.setHeight(4); return t1; } /** * 测试删除节点 */ private static void testDelete2(){ AVLTree t1 = getTestDeleteData2(); System.out.println("-------------删除前-------------"); TraversalUtil.init(); List<Integer> preList = TraversalUtil.preOrder(t1); System.out.println("先序排列结果为："); System.out.println(Arrays.toString(preList.toArray())); TraversalUtil.init(); List<Integer> inList = TraversalUtil.inOrder(t1); System.out.println("中序排列结果为："); System.out.println(Arrays.toString(inList.toArray())); TraversalUtil.init(); List<Integer> postList = TraversalUtil.postOrder(t1); System.out.println("后序排列结果为："); System.out.println(Arrays.toString(postList.toArray())); System.out.println("-------------1.删除95-------------"); t1 = TreeOperateUtil.remove(t1, 95); TraversalUtil.init(); preList = TraversalUtil.preOrder(t1); System.out.println("先序排列结果为："); System.out.println(Arrays.toString(preList.toArray())); TraversalUtil.init(); inList = TraversalUtil.inOrder(t1); System.out.println("中序排列结果为："); System.out.println(Arrays.toString(inList.toArray())); TraversalUtil.init(); postList = TraversalUtil.postOrder(t1); System.out.println("后序排列结果为："); System.out.println(Arrays.toString(postList.toArray())); t1 = getTestDeleteData2(); System.out.println("-------------2.删除105-------------"); t1 = TreeOperateUtil.remove(t1, 105); TraversalUtil.init(); preList = TraversalUtil.preOrder(t1); System.out.println("先序排列结果为："); System.out.println(Arrays.toString(preList.toArray())); TraversalUtil.init(); inList = TraversalUtil.inOrder(t1); System.out.println("中序排列结果为："); System.out.println(Arrays.toString(inList.toArray())); TraversalUtil.init(); postList = TraversalUtil.postOrder(t1); System.out.println("后序排列结果为："); System.out.println(Arrays.toString(postList.toArray())); } /** * 测试数据 * 100 * / \ * 90 110 * / \ / \ * 80 95 105 120 * \ / * 85 115 * @return */ private static AVLTree getTestDeleteData2(){ AVLTree t1 = new AVLTree(100); AVLTree t2 = new AVLTree(90); AVLTree t3 = new AVLTree(110); AVLTree t4 = new AVLTree(80); AVLTree t5 = new AVLTree(95); AVLTree t6 = new AVLTree(105); AVLTree t7 = new AVLTree(120); AVLTree t8 = new AVLTree(85); AVLTree t9 = new AVLTree(115); t5.setHeight(1); t6.setHeight(1); t8.setHeight(1); t9.setHeight(1); t4.setRight(t8); t4.setHeight(2); t7.setLeft(t9); t7.setHeight(2); t2.setLeft(t4); t2.setRight(t5); t2.setHeight(3); t3.setLeft(t6); t3.setRight(t7); t3.setHeight(3); t1.setLeft(t2); t1.setRight(t3); t1.setHeight(4); return t1; } }

测试结果为