本文图片来源：手把手教，手写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/
