本文图片来源:手把手教,手写AVL树 - 不止是编程 - 博客园
AVL树的概念
自平衡
当二叉搜索树处于平衡状态的时候,其操作时间复杂度为O(logN),但当二叉搜索树是单支树的时候,其搜索效率则为O(N)。可见,二叉搜索树的平衡性是影响其操作效率的关键。
由此出发,学者们设计了第一个平衡二叉搜索树,即AVL树。AVL树作为第一个平衡的二叉搜索树,其影响非常深远,后来的很多平衡结构都借鉴了AVL树的设计思想。
AVL树的定义
一棵AVL树或者是空树,或者是具有下列性质的二叉搜索树:
- 它的左子树和右子树都是AVL树。
- 左子树和右子树的高度之差的绝对值不超过1。
要注意,AVL的平衡性是一种相对的平衡,并非一种绝对的平衡。它不要求左子树和右子树的高度绝对相等,而仅仅是左子树和右子树的高度之差的绝对值不超过1即可。因为绝对的平衡难以实现。
如果给AVL树中的每一个节点都附加一个数字,该数字指示该节点右子树的高度减去左子树的高度所得的高度差,那么这个数字即为该节点的平衡因子。根据AVL树的定义,任一节点的平衡因子只能取-1、0或1。
AVL树的旋转
在一个平衡的二叉搜索树中插入一个新节点,就会造成其失衡,需要从插入位置沿通向根的路径回溯,检查各节点的平衡因子,在某一节点发现高度不平衡,则停止回溯。然后从发生不平衡的节点起,往下取三层,可以归纳为四种情况:
- 向某节点的左子树中插入一个左孩子。
- 向某节点的右子树中插入一个右孩子。
- 向某节点的左子树中插入一个右孩子。
- 向某节点的右子树中插入一个左孩子。
对应的处理方式:
单旋
- 右旋操作
以中间节点为轴,进行顺时针旋转,该中间节点的原父节点将变成该节点的右子节点,该中间节点的右子树则变成其原父节点的左子树。


- 左旋操作
对应的,左旋的方法是以三个呈直线排列的节点的中间节点为轴,进行逆时针旋转。该中间节点的原父节点将变成该节点的左子节点,该中间节点的左子树则变成其原父节点的右子树
双旋
- 先左后右双旋转
以3个成折线排列的节点中的末节点为轴,进行逆时针旋转。使末节点代替中间节点的位置,也就是让末节点成为原中间节点的父节点,这时,三个节点将成一直线排列,再以新的中间节点为旋转轴做右旋操作,即可完成平衡化操作。


- 先右后左双旋转
以3个成折线排列的节点中的中间节点为轴,进行顺时针旋转。使末节点代替中间节点的位置,也就是让末节点成为原中间节点的父节点,这时,三个节点将成一直线排列,再以新的中间节点为旋转轴做左旋操作,即可完成平衡化操作。
原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/avl%e6%a0%91-%e8%87%aa%e5%b9%b3%e8%a1%a1%e7%9a%84%e4%ba%8c%e5%8f%89%e6%90%9c%e7%b4%a2%e6%a0%91/