红黑树的定义：
- 每个节点要么是红色，要么是黑色；
- 根节点永远是黑色的；
- 所有的叶节点都是是黑色的（注意这里说叶子节点其实是上图中的 NIL 节点）；
- 每个红色节点的两个子节点一定都是黑色；
- 从任一节点到其子树中每个叶子节点的路径都包含相同数量的黑色节点；
性质 3 中指定红黑树的每个叶子节点都是空节点，而且并叶子节点都是黑色。但 Java 实现的红黑树将使用 null 来代表空节点，因此遍历红黑树时将看不到黑色的叶子节点，反而看到每个叶子节点都是红色的。
性质 4 的意思是：从每个根到节点的路径上不会有两个连续的红色节点，但黑色节点是可以连续的。 因此若给定黑色节点的个数 N，最短路径的情况是连续的 N 个黑色，树的高度为 N - 1（此次树高度的基数从0开始）;最长路径的情况为节点红黑相间，树的高度为 2(N - 1) 。
性质 5 是成为红黑树最主要的条件，后序的插入、删除操作都是为了遵守这个规定。红黑树并不是标准平衡二叉树，它以性质 5 作为一种平衡方法，使自己的性能得到了提升。
BST（二分查找数）存在的主要问题是，数在插入的时候会导致树倾斜，不同的插入顺序会导致树的高度不一样，而树的高度直接的影响了树的查找效率。理想的高度是logN，最坏的情况是所有的节点都在一条斜线上，这样的树的高度为N。
红黑树的定义中的这些约束确保了红黑树的关键特性：从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。结果是这个树大致上是平衡的(平衡的复杂度为O(lgN)，简略可以说红黑树也是O(lgN))，严格的所需要数学证明。因为操作比如插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例，这个在高度上的理论上限允许红黑树在最坏情况下都是高效的，而不同于普通的二叉查找树。