。。。。
一、二叉搜索树的复杂度分析
如果是按照7、4、9、2、5、8、11的顺序添加节点，复杂度是O(h) == O(logn)，如下图：
如果是从小到大添加节点，二叉搜索树就会退化成链表，复杂度是O(h) == O(n)，如下图：
当n比较大时，两者的性能差异比较大，比如n = 1000000时，二叉搜索树的最低高度是20。
删除节点时也可能会导致二叉搜索树退化成链表。有没有办法防止二叉搜索树退化成链表，让添加、删除、搜索的复杂度维持在O(logn)？使用平衡。
二、平衡
平衡（balance）：当节点数量固定时，左右子树的高度越接近，这棵二叉树就越平衡（高度也越低）。
最理想的平衡，就是像完全二叉树、满二叉树那样，高度是最小的。
完全二叉树：
满二叉树：
如何改进二叉搜索树？
首先，节点的添加、删除顺序是无法限制的，可以认为是随机的。所以，改进方案是：在节点的添加、删除操作之后，想办法让二叉搜索树恢复平衡（减小树的高度）。
如果接着继续调整节点的位置，完全可以达到理想平衡，但是付出的代价可能会比较大，比如调整的次数会比较多，反而增加了时间复杂度。总结来说，比较合理的改进方案是：用尽量少的调整次数达到适度平衡。
三、平衡二叉搜索树
平衡二叉搜索树（Balanced Binary Search Tree，简称：BBST）：一棵达到适度平衡的二叉搜索树。
经典常见的平衡二叉搜索树有：
- AVL树
- Windows NT 内核中广泛使用
- 红黑树
- C++ STL（比如 map、set ）
- Java 的 TreeMap、TreeSet、HashMap、HashSet
- Linux 的进程调度
- Ngix 的 timer 管理
一般也称AVL树和红黑树为：自平衡的二叉搜索树（Self-balancing Binary Search Tree）。