一、原理

R-B Tree，全称是Red-Black Tree，又称为“红黑树”，它一种特殊的二叉查找树。红黑树的每个节点上都有存储位表示节点的颜色，可以是红(Red)或黑(Black)。

红黑树的特性:

（1）每个结点要么是红的要么是黑的。  
（2）根结点是黑的。  
（3）每个叶结点（叶结点即指树尾端NIL指针或NULL结点）都是黑的。  
（4）如果一个结点是红的，那么它的两个儿子都是黑的。  
（5）对于任意结点而言，其到叶结点树尾端NIL指针的每条路径都包含相同数目的黑结点。 

注意：
(01) 特性(3)中的叶子节点，是只为空(NIL或null)的节点。
(02) 特性(5)，确保没有一条路径会比其他路径长出俩倍。因而，红黑树是相对是接近平衡的二叉树。

二、性能

三、应用

Java集合中的TreeSet和TreeMap，C++ STL中的set、map，以及Linux虚拟内存的管理，都是通过红黑树去实现的。

四、参考

1、教你初步了解红黑树

2、红黑树(一)之 原理和算法详细介绍

3、平衡二叉树和红黑树最差情况性能分析

关键字：左旋、右旋