1.前言AVL树的历史在计算机科学中，AVL树是以它的两个苏联发明者GeorgyAdelson-Velsky和EvgeniiLandis在他们1962年发表的论文命名的。信息组织算法”。它是一种自平衡二叉搜索树(BST)，是第一个发明的此类数据结构。2.AVL树数据结构AVL自平衡二叉树的出现旨在解决二叉查找树退化为链表的问题。当我们依次将1、2、3、4、5、6、7个元素存入BST二叉搜索树时，它会退化为一个链表，从而失去了树查询的时间复杂度，所以我们需要AVL树平衡树高度。如图：那么AVL树是如何平衡树高的呢？当二叉树左右分支的高度差不为1时，需要进行左旋或右旋调整树的高度。这有点像开车的时候，如果车头向左转，就把方向盘打到右边，而车头向右转，方向盘也向左打才有意义。那么这个方向盘（左手，右手）怎么玩，主要分为以下四种情况；左撇子（新节点6）右撇子（新节点1）左撇子+右撇子（新节点4）右撇子左撇子（新节点3）条件：节点4，平衡因子为-2，左手条件：节点3，平衡因子为2，右手条件：节点3，平衡因子为2，右手。但是当节点2平衡因子-1第一个左撇子时。条件：节点2，平衡因子-2，左撇子。但是当节点5平衡因子1是右手优先时。节点树高：以节点4为例，最长的左右分支节点为节点4的最大树高。这里子节点绕节点4的最长路径为2，所以其树高为2。在同理，可以计算出其他节点的树高。平衡因子：平衡因子是通过当前节点的左右子节点的差来计算的，然后AVL树通过平衡因子来定义什么时候进行左旋和右旋。3.AVL树的代码实现AVL树的实现与BST二叉搜索树相比，在树节点的定义上多了一个树高属性。有些AVL树还利用了平衡因子的属性，平衡因子是计算树高的结果。树节点代码结构如下；公共课{公共课clazz;公共整数值；公共节点父节点；公共节点离开；公共节点权；公共高度；AVL树左手、右手、左手+右手、右手+左手的代码运算。别着急，没那么复杂，只要能算出左旋，就能算出右旋。两个自旋的组合不难理解。源码地址：https://github.com/fuzhengwei/java-algorithms本章源码：https://github.com/fuzhengwei/java-algorithms/tree/main/data-structures/src/main/java/stackanimationdemo:https://visualgo.net/zh/bst?slide=1——第一次看懂AVL树还是有难度的。可以结合学习内容做一些动画演示。1.左手图说明左手操作；是一个去除链条和更换调整节点的处理过程。傅大哥分解展示一下。整个过程如下；代码实现：protectedNode(Nodenode){Nodetemp=node.right;临时.parent=node.parent;node.right=temp.left;if(node.right!=null){node.right.parent=node;}temp.left=节点；node.parent=temp;if(temp.parent==null){root=temp;}else{if(temp.parent.left==node){temp.父母。左=温度；}else{温度。父母。右=温度；}}returntemp;}左旋的作用相当于将树高差大于1的右子节点向上迁移来降低树高的操作。通过节点4得到父节点2和右子节点5，并将父节点2和右子节点5与节点5的左子节点关联起来，相当于大于4小于4的值，这里不体现。那么节点4的左子节点应该迁移到节点3的右子节点。组织节点5的关系，左子节点为4。左子节点4的父节点为5，如果被迁移的节点5没有父节点，则为从父节点root=temp迁移过来的节点5，查找原节点4是否为左子节点或父节点对应的右子节点，对应设置节点5的左右位置。2.右旋图说明右旋操作；它是一个去除链接和替换调整节点的处理过程。傅大哥分解展示。整个过程如下；代码实现：protectedNode(Nodenode){Nodetemp=node.left;temp.parent=node.parent;node.left=temp.right;if(node.left!=null){node.left.parent=node;}temp.right=节点；node.parent=temp;如果（temp.parent==null）{root=temp;}else{if(temp.parent.left==node){temp.parent.left=temp;}else{temp.parent.right=temp;}}returntemp;}右旋的作用相当于将树高差大于1的右子节点向上迁移来降低树高的操作。通过节点3得到父节点4和左子节点2，并将父节点7和左子节点2与节点2的右子节点关联起来，相当于大于2小于3的值，这里不体现。那么节点2的右子节点应该迁移到节点3的左子节点。整理一下节点2的关系，右子节点为3。右子节点3的父节点为2。如果被迁移的节点2没有父节点，那么就是从父节点root=temp迁移过来的节点2，并找出原来的节点3是父节点对应的左子节点还是右子节点，并对应设置左和节点2的右位置。3.左手+右手会变成左手+右手的原因是右手操作不能平衡树的高度，而这个左子节点不平衡树是右子节点太长，所以要将不平衡节点的左子节点向左旋转一次，再向右旋转一次。代码实现：if(factor(node.left)>=0){Nodetemp=super.rotateRight(node);刷新高度（temp.right）；refreshHeight(temp);}else{Nodetemp=super.rotateLeft(node.left);刷新高度（温度。左）；刷新高度（温度）；node.left=temp;temp=super.rotateRight(node);刷新高度（temp.right）；刷新高度（温度）；}4。所以会出现右旋+左旋，因为一次左旋操作无法平衡树高，而这棵树的不平衡节点的右子节点的左子节点太长，所以不平衡的右子节点节点向右旋转一次，然后执行左旋转操作。代码实现：if(factor(node.right)<=0){Nodetemp=super.rotateLeft(node);刷新高度（温度。左）；refreshHeight(temp);}else{Nodetemp=super.rotateRight(node.right);刷新高度（temp.right）；刷新高度（温度）；node.right=temp;temp=super.rotateLeft(node);刷新高度（温度。左）；refreshHeight(temp);}4.AVL树功能测试为了验证AVL树的实现是否正确，这里我们插入随机节点。如果它能一直保持平衡，那么它就是一棵可靠的AVL平衡树。单元测试：publicvoid(){AVLTreetree=newAVLTree();对于(inti=0;i<30;i++){tree.insert(newRandom().nextInt(100));系统输出。println(tree);}测试结果：输入节点：61,3,34,82,1,75,56,65,87,18,3,96,53,50,42,24,69,11,95,69,1,1,84,22,5,70,28,55,38,92/-----96(0)/-----95(1)|\-----92(0)/-----87(2)||/-----84(0)|\-----82(1)/-----75(3)||/-----70(0)||/-----69(1)|\-----69(2)|\-----65(0)61(5)|/-----56(1)||\-----55(0)|/-----53(2)|||/-----50(0)||\-----42(1)||\-----38(0)\-----34(4)|/-----28(0)|/-----24(1)||\-----22(0)|/-----18(2)||\-----11(1)||\-----5(0)\-----3(3)|/-----3(1)||\-----1(0)\-----1(2)\-----1(0)Processfinishedwithexitcode0随机插入30个节点，打印出每个节点的顺序，经过AVL左右旋转平衡后，二叉结构始终保持树高平衡因子不超过1，则验证通过
