2.常用数据结构-AVL树
AVL树是带有平衡条件的查找二叉树。这个平衡条件要容易保持，而且他要保证树的深度为O(logN)
原文地址：http://blog.****.net/qq_25806863/article/details/74755131
平衡条件
一个最理想的平衡条件是左右两个子树的高度完全相等，但只有节点数量为2^n-1的树才满足这个条件（n是层数，2层要3个，3层要7个）。这个条件太严格，不好用。
如果只要求根节点平衡的话，上面的条件可能会容易实现一点，但是会出现下面这样坏的二叉树：
因此一颗AVL树的条件是，对于每个节点来说，这个节点的左右子树的高度最多差1.
简单示例
AVL树：
非AVL二叉树：
旋转
在每一次插入数值之后，树的平衡性都可能被破坏，这时可以通过一个简单的操作来矫正平衡–旋转。
旋转的目的就是减少高度，通过降低整棵树的高度来平衡。哪边的树高，就把那边的树向上旋转。
通过旋转可以降低高度。
- 所谓的左旋和右旋都是以子树为原点的：如b是a的子树，那么旋转就围绕b来进行。
- 如果b是a的左子树，那么就围绕b将a向右旋转，看着就像是a直接掉下来了，掉成了b的右子树。
- 如果b是a的右子树，那么就围绕b将a向左旋转，看着就像是a直接掉下来了，掉成了b的左子树。
插入节点时分四种情况，四种情况对应的旋转方法是不同的：
例如对于被破坏平衡的节点 a 来说：
| 插入方式 | 描述 | 旋转方式 |
|---|---|---|
| LL | 在a的左子树根节点的左子树上插入节点而破坏平衡 | 右旋转 |
| RR | 在a的右子树根节点的右子树上插入节点而破坏平衡 | 左旋转 |
| LR | 在a的左子树根节点的右子树上插入节点而破坏平衡 | 先左旋后右旋 |
| RL | 在a的右子树根节点的左子树上插入节点而破坏平衡 | 先右旋后左旋 |