平衡树

二叉搜索树作为数据存储的结构有重要的优势：可以快速的找到给定关键字的数据项，并且可以快速的插入和删除数据项

但是，二叉搜索树有一个麻烦的问题
如果插入的数据是有序的数据，比如下面的情况
有一棵初始化为 9 8 12的二叉树

/*
     9 
    / \ 
   8  12
*/

插入下面的数据: 7 6 5

/*
     9 
    / \ 
   8  12
   /
   7
   /
   6
   /
   5
   ...
*/

非平衡树

比较好的二叉搜索树数据应该是作用分布均匀的
但是插入连续数据后，分布的不均匀，我称这种树为非平衡树
对于一个平衡二叉树来说，插入/查找等操作的效率是O(logN)
对于一棵非平衡二叉树来说，相当于编写了一个链表，查找效率变成了O(N)

树的平衡性

为了能较快的时间O(logN)来操作一棵树，我们需要保证树总是平衡的：

• 至少大部分是平衡的，那么时间复杂度也是接近O(logN)
• 也就是说树中每个节点左边的子孙节点的个数，应该尽可能的等于右边的子孙节点的个数
• 常见的平衡树有哪些呢？

AVL树

AVL树是最早的一种平衡树，他总有办法保持树的平衡(每个节点多存储一个额外的数据)
因为AVL树是平衡的，所有时间复杂度也是O(logN)
但是，每次插入/删除操作相对于红黑树效率都不高，所以整体效率不如红黑树

红黑树

红黑树也通过一些特性来保持树的平衡
因为是平衡树，所以时间复杂度也是在O(logN)
另外插入/删除等操作，红黑树的性能要优于AVL树，所以现在平衡树的应用基本都是红黑树