1 名词说明
二叉树：每个结点最多含有两个子树的树
针对结点个数存在一些特殊的二叉树，如：
- 满二叉树：叶结点除外的所有结点均含有两个子树的树被称为满二叉树
- 完全二叉树：除最后一层外，所有层都是满结点，且最后一层缺右边连续结点的二叉树称为完全二叉树
另外对于二叉搜索树、平衡二叉树、红黑树在下文中进一步详细说明。
2 二叉搜索树
又叫做二叉查找树、二叉排序树
其具有以下性质：
- 若它的左子树不为空，则左子树上所有结点的值都小于根结点的值
- 若它的右子树不为空，则右子树上所有结点的值都大于根结点的值
- 它的左右子树也分别为二叉搜索树
特别说明：二叉搜索树中序遍历的结果是有序的
3 平衡二叉树【AVL】
3.1 定义
由前苏联的数学家 Adelse-Velskil 和 Landis 在 1962 年提出的高度平衡的二叉树，根据科学家的英文名也称为 AVL 树。
它具有如下几个性质：
- 可以是空树。
-
假如不是空树，任何一个结点的左子树与右子树都是平衡二叉树，并且高度之差的绝对值不超过 1。
image.png
3.2 平衡因子
某结点的左子树与右子树的高度(深度)差即为该结点的平衡因子BF（Balance Factor），平衡二叉树中不存在平衡因子大于 1 的结点。在一棵平衡二叉树中，结点的平衡因子只能取:
- 0：左右子树等高
- 1：左子树比较高
- -1：右子树比较高。
3.3 插入结点
插入失衡示例
在12结点下面插入15：
3.3.1 最小失衡子树
在新插入的结点向上查找，以第一个平衡因子的绝对值超过 1 的结点为根的子树称为最小不平衡子树。也就是说，一棵失衡的树，是有可能有多棵子树同时失衡的。而这个时候，我们只要调整最小的不平衡子树，就能够将不平衡的树调整为平衡的树。
【3.3.1 失衡示例】中以50为父结点的子树为最小失衡子树。
平衡二叉树的失衡调整主要是通过旋转最小失衡子树来实现的。根据旋转的方向有两种处理方式，左旋与右旋。
3.3.2 右旋
流程：
1.结点的左孩子替代此结点位置
2.左孩子的右子树变为该结点的左子树
3.结点本身变为左孩子的右子树
【3.3.1 失衡示例】中由于50父结点的左子树高度比右子树大2，故需要右旋，其流程如下：
3.3.3 左旋
流程：
1.结点的右孩子替代此结点位置
2.右孩子的左子树变为该结点的右子树
3.结点本身变为右孩子的左子树
3.4 四种结点插入方式
假设一颗 AVL 树的某个结点为 A，有四种操作会使 A 的左右子树高度差大于 1，从而破坏了原有 AVL 树的平衡性。平衡二叉树插入结点的情况分为以下四种：
| 插入方式 | 描述 | 旋转方式 |
|---|---|---|
| LL | 在A的左子树根结点的左子树上插入结点 | 右旋转 |
| RR | 在A的右子树根结点的右子树上插入结点 | 左旋转 |
| LR | 在A的左子树根结点的右子树上插入结点 | 先左旋后右旋 |
| RL | 在A的右子树根结点的左子树上插入结点 | 先右旋后左旋 |
3.4.1 LL
3.4.2 RR
3.4.3 LR
3.4.4 RL
所有不平衡情况下，先寻找最小不平衡树，判断其所属的不平衡类别，再根据上述4种类别进行固定化程序的操作。
LL , LR ，RR ，RL其实已经为我们提供了最后哪个结点作为新的根指明了方向。如 LR 型最后的根结点为原来的根的左孩子的右孩子，RL 型最后的根结点为原来的根的右孩子的左孩子。只要记住这四种情况，可以很快地推导出所有的情况。
3.5 删除结点
删除结点分为四种情况：
1.删除叶子结点
2.删除的结点只有左子树
3.删除的结点只有右子树
4.删除的结点既有左子树又有右子树
AVL 树在删除结点后需要重新检查平衡性并修正，插入操作后只需要对插入栈中的弹出的第一个非平衡结点进行修正，而删除操作需要修正栈中的所有非平衡结点。
对左或者右子树的删除操作相当于对右或者左子树的插入操作，然后再对应上插入的四种情况选择相应的旋转就好了。
3.5.1 删除叶子结点
操作：直接删除，然后依次向上调整为AVL树。
3.5.2 删除的结点只有左子树
操作：该节点的值替换为左孩子节点的值，然后删除左孩子节点。
3.5.3 删除的结点只有右子树
操作：该节点的值替换为右孩子节点的值，然后删除右孩子节点。
3.5.4 删除的结点既有左子树又有右子树
操作：该节点的值替换为该节点的前驱节点（或者后继节点），然后删除前驱节点（或者后继节点）
附录
平衡二叉树的实现：红黑树、AVL、替罪羊树、Treap、伸展树
