红黑树是一棵自平衡的二叉搜索树，每个节点都有一个color属性，代表红或者黑。通过对颜色的约束，从根到叶子节点的任何一条简单路径都不会比其他路径长2倍，红黑树是近似平衡的。
红黑树的特征
每个节点不是黑色就是红色
根节点的颜色是黑色
如果一个节点是红的的，他的子节点都是黑色的
叶子节点都是黑色的
对每一个节点，从该节点到所有叶子节点的简单路径上，均包含相同的黑色节点
从上面的特征看，对于n个节点的红黑树的最大高度最多为2lg(n+1)。
红黑树的例子
判断以下是否是红黑树？
（1）
（2）
（3）
红黑树和平衡二叉树
对于有N个节点高度为h的二叉排序树，其查询，插入和删除的时间复杂度为O(h)，最坏的情况可能为O(N)。此时有了平衡二叉树，对于平衡二叉树的查询，插入和删除的时间复杂的为O(lgn)，对于查询多的情况下是比较合适的，但是对于插入和删除比较频繁的情况下会频繁导致数的旋转操作。
红黑树和平衡二叉树对于频繁插入和删除的情况下是有优势的，但对于查询多情况下平衡二叉树比较有优势。
插入和删除操作，未完待续……
历史文章：
理解数据结构之平衡二叉树的删除操作
理解数据结构之二叉平衡树（AVL）
理解数据结构之二叉搜索树的插入和删除
理解数据结构之树（一）