AVL树
AVL树
AVL树的命名是取自两位发明者的首字母G. M. Adelson-Velsky和E. M. Landis，AVL树是一种平衡二叉搜索树。AVL树能够调整自身的平衡性，AVL树遵循高度平衡，任何结点的两个子树高度差不会超过1。
对于AVL树的每一个结点，平衡因子（balance factor）是它左子树高度和右子树高度的差值。只有当二叉树所有结点的平衡因子都是-1、0、1这三个值时，这棵树才是一个合格的AVL树。
失衡调整
当AVL树插入或删除结点时，平衡有可能被打破。
通过对AVL树进行左旋转、右旋转的操作，就能使其重新恢复平衡。
左旋转
逆时针旋转AVL树的两个结点X和Y，使得父结点被自己的右孩子取代，而自己成为左孩子。
互动实验
左旋：保留中间子树
访问权限PRO
PRO EXCLUSIVE探索不止于此
尊享 Pro 权益解锁完整互动实验、进阶解析与精选参考答案。
右旋转
顺时针旋转AVL树的两个结点X和Y，使得父结点被自己的左孩子取代，而自己成为右孩子。
互动实验
右旋：保留中间子树
访问权限PRO
PRO EXCLUSIVE探索不止于此
尊享 Pro 权益解锁完整互动实验、进阶解析与精选参考答案。
AVL树的失衡调整可以分为四种情况：
左左局面（LL）：右旋转
互动实验
LL：一次右旋
访问权限PRO
PRO EXCLUSIVE探索不止于此
尊享 Pro 权益解锁完整互动实验、进阶解析与精选参考答案。
右右局面（RR）：左旋转
互动实验
RR：一次左旋
访问权限PRO
PRO EXCLUSIVE探索不止于此
尊享 Pro 权益解锁完整互动实验、进阶解析与精选参考答案。
左右局面（LR）：先左旋转、再右旋转
互动实验
LR：先左旋，再右旋
访问权限PRO
PRO EXCLUSIVE探索不止于此
尊享 Pro 权益解锁完整互动实验、进阶解析与精选参考答案。
右左局面（RL）：先右旋转、再左旋转
互动实验
RL：先右旋，再左旋
访问权限PRO
PRO EXCLUSIVE探索不止于此
尊享 Pro 权益解锁完整互动实验、进阶解析与精选参考答案。
插入/删除结点
例如依次向AVL树添加结点3, 2, 1, 4, 5, 6, 7, 16, 15, 14。
互动实验
AVL插入与删除：沿祖先恢复平衡
访问权限PRO
PRO EXCLUSIVE探索不止于此
尊享 Pro 权益解锁完整互动实验、进阶解析与精选参考答案。
知识测验
题目
结点X的bf=2，它的左孩子Y的bf=-1，应怎样修复？
知识测验
题目
删除后X的bf=-2，右孩子Y的bf=0，应如何调整X？
动手练习
一次双旋与删除后的单旋
依次插入30、10、20、40、50，再删除10。每次失衡写出类型、旋转结点与方向，画出关键中间树；删除时特别检查右孩子bf=0的情况。