平衡二叉树和红黑树之间的差别，一直没有搞清楚，最近在网上找到了一些资料，整理如下。留作纪念吧
平衡二叉树的追求的是全局均衡，如在做插入，删除操作时，需要调整整棵树，显然这是费时的，因此希望在做调整时，是局部调整，因此提出了红黑树，这样一种高效的数据结构(也是最变态的一种数据结构)。
红黑树属于非严格意义上的平衡二叉树，说它不严格是因为它不是严格控制左、右子树高度或节点数之差小于等于1。但红黑树高度依然是平均log(n)，且最坏情况高度不会超过2log(n)，这有数学证明。所以它算平衡树，只是不严格。不过严格与否并不影响数据结构的复杂度。
“AVL trees are actually easier to implement than RB trees because there are fewer cases. And AVL trees require O(1) rotations on an insertion, whereas red-black trees require O(lg n).
In practice, the speed of AVL trees versus red-black trees will depend on the data that you‘re inserting. If your data is well distributed, so that an unbalanced binary tree would generally be acceptable (i.e. roughly in random order), but you want to
handle bad cases anyway, then red-black trees will be faster because they do less unnecessary rebalancing of already acceptable data.On the other hand, if a pathological insertion order (e.g. increasing order of key) is common, then AVL trees will be faster,
because the stricter balancing rule will reduce the tree‘s height.
Splay trees might be even faster than either RB or AVL trees,depending on your data access distribution. And if you can use a hash instead of a tree, then that‘ll be fastest of all. ”
AVL树 VS 红黑树,布布扣,bubuko.com
AVL树 VS 红黑树
原文：http://blog.csdn.net/pngynghay/article/details/22730899
