二叉搜索树的缺陷

二叉搜索树作为数据存储的结构有重要的优势：

• 可以快速的找到给定关键字的数据项，并且可以快速的插入和删除数据项。

但是 二叉搜索树有一个很麻烦的问题：

如果插入的数据是有序的数据，比如下面情况：有一颗初始化为 9 8 12 的二叉树，插入下面的数据： 7 6 5 4 3

非平衡树

比较好的二叉搜索树应该是左右均匀分布的。但是插入连续数据后，分布的不均匀，称这种树为非平衡树。

对于一颗平衡二叉树来说，插入/查找等操作的效率是O(logN)

对于一颗非平衡二叉树，相当于编写了一个链表，查找效率变成了O(N)

树的平衡性

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

至少大部分是平衡的，那么时间复杂度也是接近O(logN)的。

常见的平衡树有哪些呢？

• AVL树
• 红黑树