来源

对于一般的搜索二叉树而言，如果数据恰好是按照从小到大的顺序或者从大到小的顺序插入的，那么搜索二叉树就对退化成链表，这个时候查找，插入和删除的时间都会上升到O(n)，而这对于海量数据而言，是我们无法忍受的。即使是一颗由完全随机的数据构造成的搜索二叉树，从统计角度去分析，在进行若甘次的插入和删除操作，这个搜索二叉树的高度也不能令人满意。这个时候大家就希望能有一种二叉树解决上述问题。这个时候就出现平衡搜索二叉树，它的基本原理就是在插入和删除的时候，根据情况进行调整，以降低二叉树的高度。平衡搜索二叉树典型代表就是AVL树和红黑树。

特点

AVL树是最先发明的自平衡二叉查找树，是最原始典型的平衡二叉树。
AVL树的查找、插入和删除在平均和最坏情况下都是O(logn)。

条件

它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

平衡因子

某结点的左子树与右子树的高度(深度)差即为该结点的平衡因子（BF,Balance Factor）。平衡二叉树上所有结点的平衡因子只可能是 -1，0 或 1。如果某一结点的平衡因子绝对值大于1则说明此树不是平衡二叉树。为了方便计算每一结点的平衡因子我们可以为每个节点赋予height这一属性，表示此节点的高度。

AVL插入操作

往AVL树中添加节点很可能会导致二叉树失去平衡，所以我们需要在每次插入节点后进行平衡的维护操作。
AVL树的插入操作首先会按照普通搜索二叉树的插入操作进行，当插入一个数据后，我们会沿着插入数据时所经过的的节点回溯，回溯的过程中会判回溯路径中的每个节点的左子支高度与右子支高度之差的绝对值是否超过1，如果超过1我们就进行调整，调整的目的是使得该节点满足AVL树的定义。调整的情况可以分为以下四旋转操作，旋转操作可以降低树的高度，同时不改变搜索二叉树的性质（即任何一个节点左子支中的全部节点小于该节点，右子支的全部节点大于该节点）。
插入节点破坏平衡性有如下四种情况：

LL（右旋）

RR（左旋）

LR（右左旋）

RL（左右旋）

AVL删除操作

AVL树的删除操作和插入操作一样，首先会按照普通搜索二叉树的删除操作进行，当删除一个数据后，和插入操作一样，我们通常采取的策略是沿着删除数据时所经过的的节点回溯，回溯的过程中会判断该节点的左子支高度与右子支高度之差的绝对值是否超过1（或者说大2），如果超过1，我们就进行调整，调整的目的是使得该节点满足AVL树的定义。调整的情况可以分为四种，和插入过程完全一样，这里不在赘述。