红黑树是一种自平衡二叉查找树。它是在1972年由Rudolf Bayer发明的，当时被称为平衡二叉B树，在1978年被Leo J. Guibas和Robert Sedgewick改称为“红黑树”。[1]
红黑树的特点如下：每个节点非红即黑。黑色决定平衡，红色不决定平衡。这对应了2至3树中一个节点内可以存放1至2个节点。根节点总是黑色的。每个叶子节点都是黑色的空节点（NIL节点）。这里指的是红黑树都会有一个空的叶子节点，是红黑树自己的规则。如果节点是红色的，则它的子节点必须是黑色的（反之不一定）。通常这条规则也叫不会有连续的红色节点。一个节点最多临时会有3个节点，中间是黑色节点，左右是红色节点。从根节点到叶节点或空子节点的每条路径，必须包含相同数目的黑色节点（即相同的黑色高度）。每一层都只是有一个节点贡献了树高决定平衡性，也就是对应红黑树中的黑色节点。[1] 在Java集合框架中，很多部分（HashMap，TreeMap，TreeSet 等）都有红黑树的应用。[2]
数据结构
它的统计性能要好于平衡二叉树(有些书籍根据作者姓名，Adelson-Velskii和Landis，将其称为AVL-树)，因此，红黑树在很多地方都有应用。在C++ STL中，很多部分(包括set, multiset,map, multimap)应用了红黑树的变体(SGI STL中的红黑树有一些变化，这些修改提供了更好的性能，以及对set操作的支持)。其他平衡树还有：AVL，SBT，伸展树，TREAP 等等。