平衡二叉查找树中“平衡”的意思，其实就是让整棵树左右看起来比较“对称”、比较“平衡”，不要出现左子树很高、右子树很矮的情况。这样就能让整棵树的高度相对来说低一些，相应的插入、删除、查找等操作的效率高一些。
所以，如果设计一个新的平衡二叉查找树，只要树的高度不比 log2n 大很多（比如树的高度仍然是对数量级的），尽管不符合严格的平衡二叉查找树的定义，但仍可说，这是一个合格的平衡二叉查找树。
AVL、 红黑树
Splay Tree（伸展树）、Treap（树堆）
B+ 树，二三树
①从7位置打折，34567， 8912
②相应的每个左右子树也类似的做下去。 这样就可以让整个树变得平衡。
但是不会等到它真正的自平衡二叉树里面（AVL、红黑树） 不会等到这个树病入膏肓了，再去平衡。而是在每一步进行插入或者删除的时候，都去判断它是否平衡，以及将它维护成二叉平衡树的状态。
5. AVL树 1. 发明者 G. M. Adelson-Velsky 和 Evgenii Landis
2. Balance Factor（平衡因子）：
是它的左子树的高度减去它的右子树的高度（有时相反）。 （因为二叉搜索树查询效率只与高度有关，和它节点的个数是没关的）
balance factor = {-1, 0, 1}
3. 通过旋转操作来进行平衡（四种）
Self-balancing binary search tree
5.1 平衡因子所有叶子节点高度都是0，根结点J （平衡因子 = 右子树高度 - 左子树高度 4 - 3 = +1），
上图这颗树是一个严格的平衡AVL，它的平衡因子在 -1 0 1之间。保持平衡因子不超过绝对值 1就变成了一颗二叉搜索树。
开始最直观也是最自然的一种维护方式：
最开始最经典的AVL树，它始终要保证任何一个结点它的平衡因子都只在 0 -1 1 ，这样就可以维护它的效率。
这时它的平衡因子的范围不在是1的范围了，变成-2了。接下来就要进行旋转操作：
5.2 旋转操作1. 左旋
2. 右旋
3. 左右旋
4. 右左旋
1. 左旋
2. 右旋
3. 左右旋
其中C > B < A，它的左旋是B拉上来，C顶上去，这样它还是符合二叉树的性质，就变成了左左子树的情况如下：