红黑树
红黑树五个性质：
（1）节点是红色或者黑色
（2）根节点为黑色
（3）每个叶子节点为黑色
（4）每个红色节点的两个子节点均为黑色
（5）从任意节点到每个叶子节点的所有路径均包含相同数目的黑色节点。
红黑树最重要的性质：
从根到叶子节点的最长可能路径不多于最短可能路径的两倍长。红黑树大致上是平衡的，因此插入、删除和查找操作的最坏情况时间与树的高度成比例，因此其时间复杂度为O（logn），因此红黑树最坏情况下的插入、删除和查找操作的效率优于普通的二叉查找树。
原文：http://www.cnblogs.com/cyjsegull/p/4426117.html