二叉树平衡

    首先定义下二叉树，每个节点都有两个子节点，称之为左节点和右节点，这样的数据结构称为二叉树；

    再往上升级，什么是排序二叉树，即每个节点的根节点都大于左节点，每个根节点都小于右节点，这样的结构称之为二叉排序树；

    再往上升级，什么是平衡二叉树，即每个根节点的左子树高度与右子树的高度最多相差为1，称为平衡二叉树。

    平衡二叉树具有最佳搜索特性，论证如下：

    加入树的高度是N，最多节点数为 2的N次方 -1；最少节点数为 2的（N-1）次方 -1 + 1 ，故为[2的N-1次方， 2的N次方]，检索2的N次方-1个数据，最多需要减N次；假设N=32，可检索21亿数据至42亿数据，32次比较就可检索到。10亿～21亿数据量级则需要最多检索31次。

    二叉树很简单，但满足平衡二叉树就稍微复杂。

    由排序二叉树调整成平衡二叉树可归纳为四种情况：LL，RR，LR，RL；即节点加在右子树的右子节点上，左子树的左子节点上，左子树的右子节点上，右子树的左子节点的；分别对应不同的自旋方式

    1、LL旋转，右子树的右子节点上

LL旋转

    2、RR旋转，左子树的左子节点上

RR旋转

    3、RL旋转，右子树的左子节点上（先对右子树进行右旋转，再对根节点进行左旋转）

RL旋转

    4、LR旋转，左子树的右子节点上（先对左子树进行左旋转，再对根节点进行右旋转）

LR旋转

理解巧记法：

    1、对于RR自旋 和 LL自旋，适用场景是 左节点的左子节点 和 右节点的右子节点；往左左侧加，导致左侧偏“重”，根节点向右旋转，往右右侧加，导致右侧偏“重”，根节点向左旋转

    2、对于LR自选 和 RL自旋，适用场景是 左节点的右节点 和 右节点的左节点；left/right顺序是一致的；往左节点右子节点加，，左节点右侧偏“重”，对左节点左旋，达到平衡，对根节点而言先往左侧加，导致左侧偏重，根节点向右侧自旋；