摘要: 红黑树本质是二叉查找树的一种，它的性能高于普通的二叉查找树，即使是在最坏的情况下也能保证时间复杂度为O(lgn)。红黑树在每个结点上增加一个存储位表示结点的颜色（或红或黑，故称红黑树）。通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树可以保证没有一条路径会比其他路径长出两倍，因而是接近平衡的。
红黑树的每个结点至少包含五个域：color，key，left，right 和 parent（一般我们都会在结点中存储额外的数据 data，但前面的五个域是必不可少的），如果某个结点没有子结点或者结节点，则将相应的指针设置为空值（NIL，注意不是 NULL，NIL是一个特定的空结点对象，类似于Obj-C 中 Nil对象）。我们将这些 NIL 当作叶子结点（在实际处理过程中，往往将最底层的孩子结点和根结点的父亲都指向同一个 NIL 结点，以便于处理红黑树代码中的边界条件），而将其它结点当作内结点。
阅读全文