当前位置: 首页 > 科技观察

Java数据结构和算法树(AVL)

时间:2023-03-14 16:24:22 科技观察

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,则验证通过