二叉查找树  (Binary Search Tree)：

查找最好时间复杂度O(logN)，最坏时间复杂度O(N)。

插入删除操作算法简单，时间复杂度与查找差不多

平衡二叉查找树 ( Balanced Binary Search Tree ) 

查找的时间复杂度维持在O(logN)，不会出现最差情况

AVL树在执行每个插入操作时最多需要1次旋转，其时间复杂度在O(logN)左右。

AVL树在执行删除时代价稍大，执行每个删除操作的时间复杂度需要O(2logN)。

红黑树（Red-Black Tree）

查找 效率最好情况下时间复杂度为O(logN)，但在最坏情况下比AVL要差一些，但也远远好于BST。

插入和删除操作改变树的平衡性的概率要远远小于AVL（RBT不是高度平衡的）。因此需要的旋转操作的可能性要小，而且一旦需要旋转，插入一个结点最多只需要旋转2次，删除最多只需要旋转3次(小于AVL的删除操作所需要的旋转次数)。虽然变色操作的时间复杂度在O(logN)，但是实际上，这种操作由于简单所需要的代价很小。

红黑树的几个特性：

(1) 每个节点或者是黑色，或者是红色。
(2) 根节点是黑色。
(3) 每个叶子节点是黑色。 [注意：这里叶子节点，是指子节点为空的节点！]
(4) 如果一个节点是红色的，则它的子节点必须是黑色的。
(5) 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。

ref: http://hxraid.iteye.com/blog/614070

常用的数据结构