平衡二叉树(AVL树）

平衡二叉树

平衡二叉树（Balanced Binary Tree）又称平衡二叉搜索树

首先引入一个变量，叫做平衡因子（r），节点X的r就表示x的左子树的深度-右子树的深度。然后我们要保证一棵树平衡，就是要保证左右子树的深度差小于等于1.所以r的取值能且仅能取0，-1，1.

平衡二叉树它或者是一棵空二叉树树，或者是具有下列性质的二叉树：

最小二叉平衡树的节点的公式如下 F(n)=F(n-1)+F(n-2)+1 这个类似于一个递归的数列，可以参考Fibonacci数列，1是根节点，F(n-1)是左子树的节点数量，F(n-2)是右子树的节点数量。

先来理解一下旋转
二叉左旋
一棵二叉平衡树的子树，根是Root，左子树是x，右子树的根为RootR，右子树的两个孩子树分别为RLeftChild和RRightChild。则左旋后，该子树的根为RootR，右子树为RRightChild，左子树的根为Root，Root的两个孩子树分别为x（左）和RLeftChild（右）。

而右旋就是反过来，将节点的左支往右拉，左子节点变成了父节点，并把晋升之后多余的右子节点出让给降级节点的左子节点。

即左旋就是往左变换，右旋就是往右变换。不管是左旋还是右旋，旋转的目的都是将节点多的一支出让节点给另一个节点少的一支。
这种规律的目的是保持二叉平衡树的结构，不是随便乱旋转。

二叉平衡树插入结点的操作过程
1.单向右旋（LL型左左）
下面两个图中红色结点为新插入结点，没插入红色结点时，树是平衡的，差如红色结点后，a结点的平衡因子为2.
4和9结点的插入位置都为根节点12的左结点10的左结点8的子结点（“两个左结点”的子结点，所以叫左左）。

新插入结点为18或者15（18或者15为根结点12的右结点14的右节点16的子结点，所以叫RR右右）