By

Contents
  1. 1. 红黑树的定义
  2. 2. 红黑树的应用
  3. 3. 红黑树基本操作——旋转
    1. 3.1. 左旋
    2. 3.2. 右旋
    3. 3.3. 区分左旋和右旋
  4. 4. 红黑树基本操作——添加
    1. 4.1. 红叔叔
    2. 4.2. 黑叔叔，右孩子
    3. 4.3. 黑叔叔，左孩子
  5. 5. 红黑树基本操作——删除
    1. 5.1. 黑黑，红兄弟
    2. 5.2. 黑黑，黑兄弟，两个黑侄子
    3. 5.3. 黑黑，黑兄弟，左红侄子，右黑侄子
    4. 5.4. 黑黑，黑兄弟，右红侄子
  6. 6. 参考资料

  在了解红黑树之前，首先你要了解二叉查找树。

红黑树的定义

  红黑树是一种二叉查找树，但在每个结点上增加一个存储位表示结点的颜色，可以是RED或者BLACK。通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出2倍，因而是接近平衡的。

  树中每个结点包含5个域：color，key，left，right和p。如果某结点没有一个子结点或父结点，则该结点相应的指针域（p）包含值NIL（即NULL）。我们将把这些NIL视为指向二叉查找树的外结点（叶子）的指针，而把关键字的结点视为树的内结点。

  一棵二叉查找树如果满足下面的性质，就是一棵红黑树：

  1. 每个结点或是红色，或是黑色；
  2. 根节点是黑色；
  3. 叶结点是黑色；
  4. 红结点的儿子是黑色；
  5. 对于每个结点，从该结点到其子孙叶结点的所有路径上包含相同数目的黑结点。

红黑树示意图如下：

红黑树示意图

红黑树的应用

  红黑树的应用比较广泛，主要是用它来存储有序的数据，它的时间复杂度是\(O(log_{2}n)\)，效率非常之高。

例如：

  • Java的集合中的TreeSet和TreeMap
  • C++的STL中的set、map
  • Linux中虚拟内存的管理
  • …

红黑树基本操作——旋转

左旋

右旋

区分左旋和右旋

红黑树基本操作——添加

红叔叔

黑叔叔，右孩子

黑叔叔，左孩子

红黑树基本操作——删除

黑黑，红兄弟

黑黑，黑兄弟，两个黑侄子

黑黑，黑兄弟，左红侄子，右黑侄子

黑黑，黑兄弟，右红侄子

参考资料

  1. 为什么STL和linux都使用红黑树作为平衡树的实现？
  2. 红黑树(一)之 原理和算法详细介绍
  3. 《算法导论》
Contents
  1. 1. 红黑树的定义
  2. 2. 红黑树的应用
  3. 3. 红黑树基本操作——旋转
    1. 3.1. 左旋
    2. 3.2. 右旋
    3. 3.3. 区分左旋和右旋
  4. 4. 红黑树基本操作——添加
    1. 4.1. 红叔叔
    2. 4.2. 黑叔叔，右孩子
    3. 4.3. 黑叔叔，左孩子
  5. 5. 红黑树基本操作——删除
    1. 5.1. 黑黑，红兄弟
    2. 5.2. 黑黑，黑兄弟，两个黑侄子
    3. 5.3. 黑黑，黑兄弟，左红侄子，右黑侄子
    4. 5.4. 黑黑，黑兄弟，右红侄子
  6. 6. 参考资料