二叉搜索树概要
#1.为什么要二叉搜索树？
顺序存储的排序数组可以支持如下的操作：
但是插入和删除的时候时间复杂度达到\(O(n)\),顺序存储结构不适于动态的情况。如果使用链表的话插入和删除就可以在常数时间内完成，但是链表的查找却需要\(O(n)\)；两种数据结构各有优点和缺点，使用场合不同。
二叉搜索树是结合了排序数组和排序链表二者优点的数据结构，二叉搜索树是满足：左孩子<=节点值<=右孩子 的二叉树，各种操作时间复杂度只平均要\(logn\)（平衡的二叉搜索树）：
二叉搜索树可以进行的操作相当多，但是如果只需要如查找、插入、删除，Hashtable可以做的更好，如果只需要最大/最小、插入、删除Heap更好，应更具不同情况下选择更适合的数据结构。
#2.平衡二叉搜索树
二叉搜索树的各种操作时间复杂度和树高相关，\(n\)个节点的满二叉搜索树高度为\(log_2n\)。因此要保证二叉搜索树的效率，就要尽可能的使二叉搜索树平衡，这样树高就会达到最小。如果二叉搜索树退化成链表，则树高就变成\(n\)，所有操作的时间复杂度就达到了\(O(n)\),那么给定节点的二叉搜索树有多少种？看这里。
为了让二叉搜索达到树平衡，提高二叉搜索树的效率，产生了很多方法。比较常见的有：AVL树、伸展树(Splay Tree)、Treap树、红黑树(RB Tree)等。
-
AVL树
AVL树是根据它的发明者G.M. Adelson-Velsky和E.M. Landis命名的。 它是最先发明的自平衡二叉查找树，也被称为高度平衡树。相比于”二叉查找树”，它的特点是：AVL树中任何节点的两个子树的高度最大差别为1。
AVL树中的每个结点都有一个平衡因子（balance factor，BF），它表示这个结点的左、右子树的高度差，也就是左子树的高度减去右子树的高度的结果值。AVL树上所有结点的BF值只能是-1、0、1。反之，只要二叉树上一个结点的BF的绝对值大于1，则该二叉树就不是平衡二叉树。在进行插入和删除的时候找出失去平衡的节点，进行必要的旋转操作保证树的平衡。
-
伸展树(Splay Tree)
AVL树为了保持严格的平衡，所以在数据插入上会呈现过多的旋转，影响了插入和删除的性能，此时AVL的一个变种伸展树（Splay）就应运而生了；伸展树的主要理念就是是“二八原则”，把每次访问的节点调整到跟节点，减少下次搜索时的时间复杂度。这样总体上伸展树的搜索效率较高。
-
堆树(Treap Tree)
Treap 树(tree-heap)树一种简单的优化策略，从名字也能看出它是树和堆的合体，原理比较简单，在树节点中增加一个域维护一个“优先级”，“优先级”采用随机数的方法，但是”优先级“必须满足根堆的性质，是“大根堆”或者“小根堆”无所谓，在进行插入和删除时，不仅要满足二叉搜索树的条件，同时维护堆的性质。而由于堆的优先级是随机赋值的，所以可以使搜索树的高度较为均衡。
-
红黑树(RB Tree)
红黑树是规定了如下特性的二叉搜索树: （1）每个节点或者是黑色，或者是红色。 （2）根节点是黑色。 （3）每个叶子节点（NIL）是黑色。 [注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点！] （4）如果一个节点是红色的，则它的子节点必须是黑色的。 （5）从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。 在对红黑树进行插入删除的时候进行必要的操作维护红黑树的性质，保持树高平衡性。
参考：
Tim Roughgarden: Algorithms: Design and Analysis, Part 1 一线码农博客
Haiyang Xu 05 May 2014