红黑树是带有颜色属性的自平衡二叉查找树。对红黑树的操作在最坏情形下花费O(logN)时间，红黑树的高度最多是2log(N+1)。
红黑树是具有下列着色性质的二叉查找树： 1、每一个节点或者着成红色，或者着成黑色； 2、根是黑色的； 3、如果一个节点是红色的，那么它的子节点必须是黑色的； 4、从一个节点到一个NULL指针的每一条路径必须包含相同数目的黑色节点。
参考文献： 《数据结构与算法分析—C语言描述》
