数据结构与算法9-1の查找の平衡二叉树（AVL）
查找の平衡二叉树（AVL）
浙江大学数据结构与算法
1. 定义
平衡二叉树是一种搜索二叉树（或查找二叉树），其中每一个结点的左子树和右子树的高度差的绝对值都不大于1。
高度差定义为平衡因子（BF）:
2. AVL的调整
当插入元素后破坏了二叉平衡树的平衡时，需要对其进行调整。
视频中，对不平衡的元素起了特称：
引起不平衡的元素是麻烦结点,
被破坏平衡的元素是发现者，
2.1 AVL调整分类与策略
以下分类是从“麻烦结点”在“发现者”的方位为依据：
1. RR
当然，所谓的右边也不是绝对的：
2. LL
3. LR
【视频中没有给出这种旋转的具体分解步骤，但是我这里自己推理了一下：这种情况下类似于先把B和C左旋，然后再A，B，C做右旋？】
4. RL
【视频中没有给出这种旋转的具体分解步骤，但是我这里自己推理了一下：这种情况下类似于先把B和C右旋，然后再A，B，C做左旋？】
2.2 代码实现
代码实现见《大话数据结构版本》