济南学习网站制作,游戏培训学校,互联网小程序设计师,浙江门户网站建设公司目录
前言#xff1a;
AVL树的概念:
AVL树节点的定义#xff1a;
AVL树的插入#xff08;重点#xff09;
AVL树的旋转#xff1a;
#xff08;1#xff09;新节点插入较高左子树的左侧---右单旋
#xff08;2#xff09;新节点插入较高右子树的右侧---左单旋 …目录
前言
AVL树的概念:
AVL树节点的定义
AVL树的插入重点
AVL树的旋转
1新节点插入较高左子树的左侧---右单旋
2新节点插入较高右子树的右侧---左单旋
3新节点插入较高左子树的右侧---左右双旋
4新节点插入较高右子树的左侧---右左双旋
总结
AVL树的验证
验证用例
AVL树的删除了解
AVL树性能分析
结语 前言
如果有友友需要本文章的全部源码的话请前往AVL树源码
AVL树的概念:
二叉搜索树虽可以缩短查找的效率但如果数据有序或接近有序二叉搜索树将退化为单支树查找元素相当于在顺序表中搜索元素效率低下。因此两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法当向二叉搜索树中插入新结点后如果能保证每个结点的左右子树高度之差的绝对值不超过 1(需要对树中的结点进行调整)即可降低树的高度从而减少平均搜索长度。
一棵AVL树或者是空树或者是具有以下性质的二叉搜索树 1它的左右子树都是AVL树 2左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1) 如果一棵二叉搜索树是高度平衡的它就是AVL树。如果它有n个结点其高度可保持在OlogN 搜索时间复杂度O(logN)。
例如下图就是一个AVL树圆圈外面的数字就是平衡因子为右子树高度 - 左子树高度。 AVL树节点的定义
为了AVL树实现简单AVL树节点在定义时维护一个平衡因子和采用孩子双亲表示法具体节点定义如下
因为在实际开发时我们都是树节点单独创建一个类不是很经常使用静态内部类故我们这里就创建一个TreeNode类来实现。
public class TreeNode {public int val;//节点值public int bf;//AVL树的平衡因子public TreeNode left;//左孩子引用public TreeNode right;//右孩子引用public TreeNode parent;//父亲节点引用public TreeNode(int val){this.val val;}}
注意
当前节点的平衡因子 右子树高度 - 左子树的高度。但是不是每棵树都必须有平衡因子这只是其中的一种实现方式。
AVL树的插入重点
AVL树就是在二叉搜索树的基础上引入了平衡因子因此AVL树也可以看成是二叉搜索树。那么AVL树的插入过程可以分为两步 1按照二叉搜索树的方式插入新节点。 2调整节点的平衡因子。 但是在插入节点后要更新平衡因子这时AVL树的平衡性就可能会遭到破坏我们就要进行调整。
假设插入节点为nodenode的父亲节点为parent在node节点插入后parent节点的平衡因子一定要进行调整在插入之前parent的平衡因子分为三种情况-101。
1如果cur插入到parent的左侧只需给parent的平衡因子 -1 即可。
2如果cur插入到parent的右侧只需给parent的平衡因子 1 即可。
此时parent的平衡因子可能有三种情况0正负1 正负2。对应分析如下
1如果parent的平衡因子为0说明插入之前parent的平衡因子为正负1插入后被调整成0此时满足AVL树的性质插入成功就不需要向上调整因为对于上面的节点来说这颗子树的最大高度没有改变。
2如果parent的平衡因子为正负1说明插入前parent的平衡因子一定为0插入后被更新成正负1此时以parent为根的树的高度增加需要继续向上更新。
3如果parent的平衡因子为正负2则parent的平衡因子违反平衡树的性质需要对其进行旋转处理。
根据上面的分析我们可以先写出如下代码大体框架首先我们先根据二叉搜索树的查找节点方式找到要插入节点的父亲节点插入节点后修改平衡因子根据修改后平衡因子的情况分为三种情况。
public boolean insert(int val){//根据二叉搜索树查找节点的方式找到插入点TreeNode node new TreeNode(val);//根节点为空if(root null){root node;}TreeNode cur root;TreeNode parent null;//parent始终是cur的父亲节点当cur为null时parent就是我们要插入节点的父亲节点while(cur ! null){if(cur.val val){//去左子树找parent cur;cur cur.left;}else if(cur.val val){//去右子树找parent cur;cur cur.right;}else{//插入节点已存在插入失败return false;}}//插入节点if(parent.val val){parent.right node;}else{parent.left node;}node.parent parent;cur node;//调整插入节点父亲节点的平衡因子while(parent ! null){if(cur parent.left){parent.bf--;}else{parent.bf;}//当调整后父亲节点平衡因子为0if(parent.bf 0){//说明插入后parent树的左右最大深度不变//已经平衡了break;}else if(parent.bf 1 || parent.bf -1){//说明插入后parent树的左右最大深度改变会影响parent树的parent的平衡因子//要继续向上修改平衡因子cur parent;parent cur.parent;}else{//parent的平衡因子为2要进行旋转调整//有两种情况分别为右树高和左树高if(parent.bf 2){if(cur.bf 1){//左旋rotateLeft(parent);}else{//进行右左双旋//其实就是先调整成能左旋的情况再左旋//cur.bf -1rotateRL(parent);}}else{//parent.bf -2左树高if(cur.bf -1){//右旋rotateRight(parent);}else{//左右双旋//先左旋成能将整体进行右旋的情况再进行右旋rotateLR(parent);//cur.bf 1}}//break;}}return true;}
如果对上面代码的else部分为什么是这么旋转感到疑惑的话可以先跳过在介绍完下面AVL树的旋转后就明白了。
AVL树的旋转
如果在一棵原本是平衡的AVL树中插入一个新节点可能造成不平衡此时必须调整树的结构使之平衡化。根据节点插入位置的不同AVL树的旋转分为四种
注意下面我画的四张图大家一定一定要会画总不可能记代码吧没有意义。
我最常用的例子节点是6030abc其中abc为满足要求的任意值
1新节点插入较高左子树的左侧---右单旋 上面的图便是我们右单旋的全过程了我们可以发现旋转完后这个AVL树变得平衡了且需要修改的平衡因子只有两个subL和parent的平衡因子。
具体代码如下
在这过程中subLR节点可能不存在故要来一次特判防止空指针异常接着要分是根节点和不是根节点两种情况如果不是根节点又要分是pParentparent的父亲节点的左子树还是右子树。主要要弄好指向和平衡因子的修改经过分析和作图后发现调整后只有subL和parent平衡因子发生改变。
private void rotateRight(TreeNode parent){//右旋TreeNode subL parent.left;//parent节点的左孩子节点TreeNode subLR subL.right;//parent节点的左孩子节点的右孩子节点parent.left subLR;//防止节点不存在空指针异常if(subLR ! null){subLR.parent parent;}subL.right parent;//在修改parent的父亲节点时要提前记入下来防止丢失TreeNode pParent parent.parent;parent.parent subL;//如果parent是根节点,即没有父亲节点if(parent root){root subL;subL.parent null;}else{//有父亲节点故要考虑其是父亲节点的左孩子还是右孩子if(pParent.left parent){pParent.left subL;}else{pParent.right subL;}subL.parent pParent;}//经过分析和作图发现调整后只有subL和parent平衡因子发生改变//subL平衡因子从-1变成0//parent平衡因子从-2变成0subL.bf 0;parent.bf 0;}
2新节点插入较高右子树的右侧---左单旋 上图为我们左单旋的全过程这个其实可以仿照我们右单旋的步骤来。具体代码如下
用private进行封装创建对应的孩子节点进行下面个个参数的指向修改时一定要画图节点的选取可以仿照我上面画的最后注意不要忘了修改对应节点的平衡因子。
这里教给大家一个记忆小技巧对哪个节点进行旋转新的parent节点的旋转方向根据名字节点要断掉。
private void rotateLeft(TreeNode parent){//左旋//小技巧对哪个节点进行旋转新的parent节点的旋转方向(根据名字)节点要断掉TreeNode subR parent.right;//parent的右孩子TreeNode subRL subR.left;//parent的右孩子的左孩子//防止节点不存在空指针异常if(subRL ! null){subRL.parent parent;}//这里建议画图理解parent.right subRL;subR.left parent;//在修改parent的父亲节点时要提前记入下来防止丢失TreeNode pParent parent.parent;parent.parent subR;if(parent root){root subR;subR.parent null;}else{if(pParent.left parent){pParent.left subR;}else{pParent.right subR;}subR.parent pParent;}subR.bf 0;parent.bf 0;}
3新节点插入较高左子树的右侧---左右双旋
在有些情况下只进行左旋和右旋还并不能解决所有情况例如下图如果友友感兴趣的话可以自己试试显然一次旋转完成不了。我们正确的旋转方式为左右双旋先左旋再进行右旋。 正确旋转过程如下图。
下图只演示了subLR的平衡因子为-1的情况还有1和0的情况就交给友友们自己去完成了都差不多的 代码如下
这里特别注意我们传入左右旋的方法的参数是传入parent而不是其孩子节点这个一定要弄清楚否则就错了下面之所以没有bf 0的情况是因为在 bf 0 的情况下在rotateLeft方法和rotateRight方法下就已经吧要修改的bf修改完成了。但是不能if后面用else必须是else if因为else会把bf 0的情况收纳进去这样就出错了。
private void rotateLR(TreeNode parent){//左右双旋TreeNode subL parent.left;TreeNode subLR subL.right;int bf subLR.bf;//bf的获取必须在旋转之前否则会因旋转而改变,旋转会改变对应的平衡因子rotateLeft(subL);rotateRight(parent);//画图这里可以分为插在左边还是右边if(bf -1){parent.bf 1;subL.bf 0;subLR.bf 0;}else if(bf 1){//bf 1parent.bf 0;subLR.bf 0;subL.bf -1;}}
4新节点插入较高右子树的左侧---右左双旋
右左双旋的实现友友们可以参考左右双旋。 具体流程和左右双旋差不多也有三种情况bf为01-1的三种情况注意传入左右旋方法的参数是传入对应的parent节点。
对应代码如下
private void rotateRL(TreeNode parent){//右左双旋TreeNode subR parent.right;TreeNode subRL subR.left;int bf subRL.bf;//bf的获取必须在旋转之前否则会因旋转而改变//旋转传入的父亲节点为原来的不是改变后的rotateRight(subR);rotateLeft(parent);//画图这里可以分为插在左边还是右边if(bf 1){parent.bf -1;subRL.bf 0;subR.bf 0;}else if(bf -1){// bf -1subRL.bf 0;parent.bf 0;subR.bf 1;}}
总结
新节点插入后假设以pParent为根的子树不平衡即pParent的平衡因子为2或者-2分以下情况考虑
1.pParent的平衡因子为2说明pParent的右子树高设pParent的右子树的根为pSubR。
1当pSubR的平衡因子为1时执行左单旋。
2当pSubR的平衡因子为-1时执行右左双旋。
2.pParent的平衡因子为-2说明pParent的左子树高设pParent的左子树的根为pSubL。
1当pSubL的平衡因子为-1是执行右单旋。
2当pSubL的平衡因子为1时执行左右双旋。
即pParent与其较高子树节点的平衡因子时同号时单旋转异号时双旋转。
旋转完成后原pParent为根的子树个高度降低已经平衡不需要再向上更新。
AVL树的验证
分为两步
1验证其为二叉搜索树
如果中序遍历可得到一个有序的序列就说明为二叉搜索树
2验证其为平衡树
1.每个节点子树高度差的绝对值不超过1(注意节点中如果没有平衡因子)
2.节点的平衡因子是否计算正确
对应代码如下
public boolean isBalance(TreeNode root){if(root null) return true;int heightL height(root.left);int heightR height(root.right);if(heightR - heightL ! root.bf){System.out.println(root.val :的平衡因子计算错误);return false;}return Math.abs(heightL - heightR) 1 isBalance(root.left) isBalance(root.right);}private int height(TreeNode root){if(root null) return 0;int heightL height(root.left);int heightR height(root.right);return Math.max(heightL,heightR) 1;}public void inOrder(TreeNode root){if(root null) return;inOrder(root.left);System.out.print(root.val );inOrder(root.right);} 验证用例
大家可以自己完成AVL树的代码后把下面这三个实例带进去验证如果是true且中序遍历为升序的话代码就没什么问题了。 这里再补充一个用例int[] array {30,20,90,60,180,40};
AVL树的删除了解
因为AVL树也是二叉搜索树可按照二叉搜索树的方式将节点删除然后再更新平衡因子只不过与删除不同的是删除节点后的平衡因子更新最差情况下一直要调整到根节点的位置。
这里由于实现比较麻烦要考虑的东西很多且面试一般也不会让你写代码文章篇幅有限只说大致流程
1、找到需要删除的节点。
2、按照搜索树的删除规则删除节点。
3、更新平衡因子如果出现了不平衡进行旋转。单旋双旋。
AVL树性能分析
AVL树是一棵绝对平衡的二叉搜索树其要求每个节点的左右子树高度差的绝对值都不超过1这样可以保证查询时高效的时间复杂度即 。但是如果要对AVL树做一些结构修改的操作性能非常低下比如插入时要维护其绝对平衡旋转的次数比较多更差的是在删除时有可能一直要让旋转持续到根的位置。因此如果需要一种查询高效且有序的数据结构而且数据的个数为静态的(即不会改变)可以考虑AVL树但一个结构经常修改就不太适合。
结语
其实写博客不仅仅是为了教大家同时这也有利于我巩固知识点和做一个学习的总结由于作者水平有限对文章有任何问题还请指出非常感谢。如果大家有所收获的话还请不要吝啬你们的点赞收藏和关注这可以激励我写出更加优秀的文章。
