又称AVL树（Adelson-Velskii and Landis）
一棵平衡二叉树或者是空树，或者是具有下列性质的二叉排序树：
①左子树与右子树的高度之差的绝对值小于等于1
②左子树和右子树也是平衡二叉排序树
为了方便起见，给每个结点附加一个数字，给出该结点左子树与右子树的高度差，这个数字称为结点的平衡因子（BF）
平衡因子=结点左子树的高度-结点右子树的高度
根据平衡二叉树的定义，平衡二叉树上所有的结点的平衡因子只能是-1，0或1
失衡二叉排序树的分析与调整：
平衡调整的四种类型：
（1）LL型调整过程：
①B结点带左子树α一起上升
②A结点成为B的右孩子
③原来B结点的右子树β作为A的左子树
（2）RR型调整过程：
①B结点带右子树β一起上升
②A结点成为B的左孩子
③原来B结点的左子树α作为A的右子树
（3）LR型调整过程：
①C结点穿过A、B结点上升
②B结点成为C的左孩子，A结点成为C的右子树
③原来C结点的左子树β作为B的左子树，原来C结点的右子树γ作为A的左子树
（4）RL型调整过程：
若有收获，就点个赞吧
0 人点赞
