红黑树是一种自平衡二叉查找树。它是在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 等等。