红黑树学习

欢迎关注： Lvshen’s Blog

什么是TreeMap

首先我们来先说说HashMap与LinkedHashMap，它们保证了以$O(1)$的时间复杂度进行增、删、改、查，从存储角度考虑，这两种数据结构是非常优秀的。另外，LinkedHashMap还额外地保证了Map的遍历顺序可以与put顺序一致，解决了HashMap本身无序的问题。

尽管如此，HashMap与LinkedHashMap还是有自己的局限性—-它们不具备统计性能，或者说它们的统计性能时间复杂度并不是很好才更准确，所有的统计必须遍历所有Entry，因此时间复杂度为$O(N)$。比如Map的Key有1、2、3、4、5、6、7，我现在要统计：

1. 所有Key比3大的键值对有哪些
2. Key最小的和Key最大的是哪两个

就类似这些操作，HashMap和LinkedHashMap做得比较差，此时我们可以使用TreeMap。TreeMap的Key按照自然顺序进行排序或者根据创建映射时提供的Comparator接口进行排序。TreeMap为增、删、改、查这些操作提供了$log(N)$的时间开销，从存储角度而言，这比HashMap与LinkedHashMap的$O(1)$时间复杂度要差些；但是在统计性能上，TreeMap同样可以保证$log(N)$的时间开销，这又比HashMap与LinkedHashMap的$O(N)$时间复杂度好不少。

因此总结而言：如果只需要存储功能，使用HashMap与LinkedHashMap是一种更好的选择；如果还需要保证统计性能或者需要对Key按照一定规则进行排序，那么使用TreeMap是一种更好的选择。

认识红黑树

在讲TreeMap前还是先说一下红黑树的一些基本概念，这样可以更好地理解之后TreeMap的源代码。

二叉查找树是在生成的时候是非常容易失衡的，造成的最坏情况就是一边倒（即只有左子树/右子树），这样会导致树检索的效率大大降低。

红黑树是为了维护二叉查找树的平衡而产生的一种树，根据维基百科的定义，红黑树有五个特性，但我觉得讲得不太易懂，我自己总结一下，红黑树的特性大致有三个（换句话说，插入、删除节点后整个红黑树也必须满足下面的三个性质，如果不满足则必须进行旋转）：

1. 根节点与叶节点都是黑色节点，其中叶节点为Null节点
2. 每个红色节点的两个子节点都是黑色节点，换句话说就是不能有连续两个红色节点
3. 从根节点到所有叶子节点上的黑色节点数量是相同的

上述的性质约束了红黑树的关键：从根到叶子的最长可能路径不多于最短可能路径的两倍长。得到这个结论的理由是：

1. 红黑树中最短的可能路径是全部为黑色节点的路径
2. 红黑树中最长的可能路径是红黑相间的路径

此时（2）正好是（1）的两倍长。结果就是这个树大致上是平衡的，因为比如插入、删除和查找某个值这样的操作最坏情况都要求与树的高度成比例，这个高度的理论上限允许红黑树在最坏情况下都是高效的，而不同于普通的二叉查找树，最终保证了红黑树能够以$O(log_2 n)$ 的时间复杂度进行搜索、插入、删除。

下面展示一张红黑树的实例图：

可以看到根节点到所有NULL LEAF节点（即叶子节点）所经过的黑色节点都是2个。

另外从这张图上我们还能得到一个结论：红黑树并不是高度的平衡树。所谓平衡树指的是一棵空树或它的左右两个子树的高度差的绝对值不超过1，但是我们看：

• 最左边的路径$0026–>0017–>0012–>0010–>0003–>NULL LEAF$，它的高度为5
• 最后边的路径$0026–>0041–>0047–>NULL LEAF$，它的高度为3

左右子树的高度差值为2，因此红黑树并不是高度平衡的，它放弃了高度平衡的特性而只追求部分平衡，这种特性降低了插入、删除时对树旋转的要求，从而提升了树的整体性能。而其他平衡树比如AVL树虽然查找性能为性能是$O(logn)$，但是为了维护其平衡特性，可能要在插入、删除操作时进行多次的旋转，产生比较大的消耗。

TreeMap相关特性

关 注 点	结 论
TreeMap是否允许键值对为空	Key不允许为空，Value允许为空
TreeMap是否允许重复数据	Key重复会覆盖，Value允许重复
TreeMap是否有序	按照Key的自然顺序排序或者Comparator接口指定的排序算法进行排序
TreeMap是否线程安全	非线程安全

TreeMap基本数据结构

TreeMap基于红黑树实现，既然是红黑树，那么每个节点中除了Key–>Value映射之外，必然存储了红黑树节点特有的一些内容，它们是：

1. 父节点引用
2. 左子节点引用
3. 右子节点引用
4. 节点颜色

TreeMap的节点Java代码定义为：

static final class Entry<K,V> implements Map.Entry<K,V> {

    K key;
    V value;
    Entry<K,V> left = null;
    Entry<K,V> right = null;
    Entry<K,V> parent;
    boolean color = BLACK;
    ...

}

由于颜色只有红色和黑色两种，因此颜色可以使用布尔类型（boolean）来表示，黑色表示为true，红色为false。

TreeMap添加数据流程

public class MapTest {
  @Test
  public void testTreeMap() {
      TreeMap<Integer, String> treeMap = new TreeMap<Integer, String>();
      treeMap.put(10, "10");
      treeMap.put(85, "85");
      treeMap.put(15, "15");
      treeMap.put(70, "70");
      treeMap.put(20, "20");
      treeMap.put(60, "60");
      treeMap.put(30, "30");
      treeMap.put(50, "50");

      for (Map.Entry<Integer, String> entry : treeMap.entrySet()) {
          System.out.println(entry.getKey() + ":" + entry.getValue());
      }
  }
}

本文接下来的内容会给出插入每条数据之后红黑树的数据结构是什么样子的。首先看一下treeMap的put方法的代码实现：

public V put(K key, V value) {
  Entry<K,V> t = root;
  if (t == null) {
      compare(key, key); // type (and possibly null) check

      root = new Entry<>(key, value, null);
      size = 1;
      modCount++;
      return null;
  }
  int cmp;
  Entry<K,V> parent;
  // split comparator and comparable paths
  Comparator<? super K> cpr = comparator;
  if (cpr != null) {
      do {
          parent = t;
          cmp = cpr.compare(key, t.key);
          if (cmp < 0)
              t = t.left;
          else if (cmp > 0)
              t = t.right;
          else
              return t.setValue(value);
      } while (t != null);
  }
  else {
      if (key == null)
          throw new NullPointerException();
      Comparable<? super K> k = (Comparable<? super K>) key;
      do {
          parent = t;
          cmp = k.compareTo(t.key);
          if (cmp < 0)
              t = t.left;
          else if (cmp > 0)
              t = t.right;
          else
              return t.setValue(value);
      } while (t != null);
  }
  Entry<K,V> e = new Entry<>(key, value, parent);
  if (cmp < 0)
      parent.left = e;
  else
      parent.right = e;
  fixAfterInsertion(e);
  size++;
  modCount++;
  return null;
}

从这段代码，先总结一下TreeMap添加数据的几个步骤：

1. 获取根节点，根节点为空，产生一个根节点，将其着色为黑色，退出余下流程
2. 获取比较器，如果传入的Comparator接口不为空，使用传入的Comparator接口实现类进行比较；如果传入的Comparator接口为空，将Key强转为Comparable接口进行比较
3. 从根节点开始逐一依照规定的排序算法进行比较，取比较值cmp，如果cmp=0，表示插入的Key已存在；如果cmp>0，取当前节点的右子节点；如果cmp<0，取当前节点的左子节点
4. 排除插入的Key已存在的情况，第（3）步的比较一直比较到当前节点t的左子节点或右子节点为null，此时t就是我们寻找到的节点，cmp>0则准备往t的右子节点插入新节点，cmp<0则准备往t的左子节点插入新节点
5. new出一个新节点，默认为黑色，根据cmp的值向t的左边或者右边进行插入
6. 插入之后进行修复，包括左旋、右旋、重新着色这些操作，让树保持平衡性

第1~第5步都没有什么问题，红黑树最核心的应当是第6步插入数据之后进行的修复工作，对应的Java代码是TreeMap中的fixAfterInsertion()方法，下面看一下put每个数据之后TreeMap都做了什么操作，借此来理清TreeMap的实现原理。

put(10, “10”)

首先是put(10, “10”)，由于此时TreeMap中没有任何节点，因此10为根且根节点为黑色节点，put(10, “10”)之后的数据结构为：

put(85, “85”)

接着是put(85, “85”)，这一步也不难，85比10大，因此在10的右节点上，但是由于85不是根节点，因此会执行fixAfterInsertion()方法进行数据修正，看一下fixAfterInsertion()方法代码实现：

private void fixAfterInsertion(Entry<K,V> x) {

  x.color = RED;
  while (x != null && x != root && x.parent.color == RED) {
      if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
          Entry<K,V> y = rightOf(parentOf(parentOf(x)));
          if (colorOf(y) == RED) {
              setColor(parentOf(x), BLACK);
              setColor(y, BLACK);
              setColor(parentOf(parentOf(x)), RED);
              x = parentOf(parentOf(x));
          } else {
              if (x == rightOf(parentOf(x))) {
                  x = parentOf(x);
                  rotateLeft(x);
              }
              setColor(parentOf(x), BLACK);
              setColor(parentOf(parentOf(x)), RED);
              rotateRight(parentOf(parentOf(x)));
          }
      } else {
          Entry<K,V> y = leftOf(parentOf(parentOf(x)));
          if (colorOf(y) == RED) {
              setColor(parentOf(x), BLACK);
              setColor(y, BLACK);
              setColor(parentOf(parentOf(x)), RED);
              x = parentOf(parentOf(x));
          } else {
              if (x == leftOf(parentOf(x))) {
                  x = parentOf(x);
                  rotateRight(x);
              }
              setColor(parentOf(x), BLACK);
              setColor(parentOf(parentOf(x)), RED);
              rotateLeft(parentOf(parentOf(x)));
          }
      }
  }
  root.color = BLACK;
}

我们看第2行的代码，它将默认的插入的那个节点着色成为红色，这很好理解：

根据红黑树的性质（3），红黑树要求从根节点到叶子所有叶子节点上经过的黑色节点个数是相同的，因此如果插入的节点着色为黑色，那必然有可能导致某条路径上的黑色节点数量大于其他路径上的黑色节点数量，因此默认插入的节点必须是红色的，以此来维持红黑树的性质（3）

当然插入节点着色为红色节点后，有可能导致的问题是违反性质（2），即出现连续两个红色节点，这就需要通过旋转操作去改变树的结构，解决这个问题。

接着看第4行的判断，前两个条件都满足，但是因为85这个节点的父节点是根节点的，根节点是黑色节点，因此这个条件不满足，while循环不进去，直接执行一次30行的代码给根节点着色为黑色（因为在旋转过程中有可能导致根节点为红色，而红黑树的根节点必须是黑色，因此最后不管根节点是不是黑色，都要重新着色确保根节点是黑色的）。

那么put(85, “85”)之后，整个树的结构变为：

fixAfterInsertion方法流程

在看put(15, “15”)之前，必须要先过一下fixAfterInsertion()方法。第5行～第21行的代码和第21行~第38行的代码是一样的，无非一个是操作左子树另一个是操作右子树而已，因此就看前一半：

while (x != null && x != root && x.parent.color == RED) {
  if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
      Entry<K,V> y = rightOf(parentOf(parentOf(x)));
      if (colorOf(y) == RED) {
          setColor(parentOf(x), BLACK);
          setColor(y, BLACK);
          setColor(parentOf(parentOf(x)), RED);
          x = parentOf(parentOf(x));
      } else {
          if (x == rightOf(parentOf(x))) {
              x = parentOf(x);
              rotateLeft(x);
          }
          setColor(parentOf(x), BLACK);
          setColor(parentOf(parentOf(x)), RED);
          rotateRight(parentOf(parentOf(x)));
      }
  }
  ....
}

第2行的判断注意一下，用语言描述出来就是：判断当前节点的父节点与当前节点的父节点的父节点的左子节点是否同一个节点。翻译一下就是：当前节点是否左子节点插入，关于这个不明白的我就不解释了，可以自己多思考一下。对这整段代码流程如下：

1. 新插入节点命名为x，将x着色为红色
2. x不是根节点且x的父节点颜色为红色
3. x是否左子节点插入
4. 否，走左子节点插入流程
5. 是，获取x的叔父节点
6. x的叔父节点是否为红色
7. 是，a、x的父节点着色为黑色；b、x的叔父节点着色为黑色；c、x的祖父节点着色为黑色；b、x赋值为其祖父节点用于while条件重新判断，保证不会连续出现两个红色节点。
8. 否，x是否为左子树内侧插入
9. 是，对x的父节点进行一次左旋
10. 否，a、x的父节点着色为黑色；b、x的祖父节点着色为红色；c、对x的祖父节点进行一次右旋；
11. 一次修正结果

这里有一个左子树内侧插入与左子树点外侧插入的概念，我用图表示一下：

其中左边的是左子树外侧插入，右边的是左子树内侧插入，可以从上面的流程图上看到，对于这两种插入方式的处理是不同的，区别是后者也就是左子树内侧插入多一步左旋操作。

能看出，红黑树的插入最多只需要进行两次旋转，至于红黑树的旋转，后面结合代码进行讲解。

put(15, “15”)

看完fixAfterInsertion方法流程之后，继续添加数据，这次添加的是put(15, “15”)，15比10大且比85小，因此15最终应当是85的左子节点，默认插入的是红色节点，因此首先将15作为红色节点插入85的左子节点后的结构应当是：

但是显然这里违反了红黑树的性质（2），即连续出现了两个红色节点，因此此时必须进行旋转。回看前面fixAfterInsertion的流程，上面演示的是左子树插入流程，右子树一样，可以看到这是右子树内侧插入，需要进行两次旋转操作：

1. 对新插入节点的父节点进行一次右旋操作
2. 新插入节点的父节点着色为黑色，新插入节点的祖父节点着色为红色
3. 对新插入节点的祖父节点进行一次左旋操作

旋转是红黑树中最难理解也是最核心的操作，右旋和左旋是对称的操作，我个人的理解，以右旋为例，对某个节点x进行右旋，其实质是：

• 降低左子树的高度，增加右子树的高度
• 将x变为当前位置的右子节点

左旋是同样的道理，在旋转的时候一定要记住这两句话，这将会帮助我们清楚地知道在不同的场景下旋转如何进行。

先看一下（1）也就是”对新插入节点的父节点进行一次右旋操作”，源代码为rotateRight()方法：

private void rotateRight(Entry<K,V> p) {
  if (p != null) {
      Entry<K,V> l = p.left;
      p.left = l.right;
      if (l.right != null) l.right.parent = p;
      l.parent = p.parent;
      if (p.parent == null)
         root = l;
      else if (p.parent.right == p)
          p.parent.right = l;
      else p.parent.left = l;
      l.right = p;
      p.parent = l;
  }
}

右旋流程图：

对85这个节点进行右旋之后还有一次着色操作（2），分别是将x的父节点着色为黑色，将x的祖父节点着色为红色，那么此时的树形结构应当为：

然后对节点10进行一次左旋操作（3），左旋之后的结构为：

最后不管根节点是不是黑色，都将根节点着色为黑色，那么插入15之后的数据结构就变为了上图，满足红黑树的三条特性。

put(70, “70”)

put(70, “70”)就很简单了，70是85的左子节点，由于70的父节点以及叔父节点都是红色节点，因此直接将70的父节点85、将70的叔父节点10着色为黑色即可，70这个节点着色为红色，即满足红黑树的特性，插入70之后的结构图为：

put(20, “20”)

put(20, “20”)，插入的位置应当是70的左子节点，默认插入红色，插入之后的结构图为：

问题很明显，出现了连续两个红色节点，20的插入位置是一种左子树外侧插入的场景，因此只需要进行着色+对节点85进行一次右旋即可，着色+右旋之后数据结构变为：

put(60, “60”)

下面进行put(60, “60”)操作，节点60插入的位置是节点20的右子节点，由于节点60的父节点与叔父节点都是红色节点，因此只需要将节点60的父节点与叔父节点着色为黑色，将节点60的组父节点着色为红色即可。

那么put(60, “60”)之后的结构为：

put(30, “30”)

put(30, “30”)，节点30应当为节点60的左子节点，因此插入节点30之后应该是这样的：

显然这里违反了红黑树性质（2）即连续出现了两个红色节点，因此这里要进行旋转。

put(30, “30”)的操作和put(15, “15”)的操作类似，同样是右子树内侧插入的场景，那么需要进行两次旋转：

1. 对节点30的父节点节点60进行一次右旋
2. 右旋之后对节点60的祖父节点20进行一次左旋

右旋+着色+左旋之后，put(30, “30”)的结果应当为：

put(50, “50”)

下一个操作是put(50, “50”)，节点50是节点60的左子节点，由于节点50的父亲节点与叔父节点都是红色节点，因此只需要将节点50的父亲节点与叔父节点着色为黑色，将节点50的祖父节点着色为红色即可：

节点50的父节点与叔父节点都是红色节点（注意不要被上图迷糊了！上图是重新着色之后的结构而不是重新着色之前的结构，重新着色之前的结构为上上图），因此插入节点50只需要进行着色，本身这样的操作是没有任何问题的，但问题的关键在于，着色之后出现了连续的红色节点，即节点30与节点70。这就是为什么fixAfterInsertion方法的方法体是while循环的原因：

private void fixAfterInsertion(Entry<K,V> x) {

  x.color = RED;

  while (x != null && x != root && x.parent.color == RED) {
  ...
  }
}

因为这种着色方式是将插入节点的祖父节点着色为红色，因此着色之后必须将当前节点指向插入节点的祖父节点，判断祖父节点与父节点是否连续红色的节点，是就进行旋转，重新让红黑树平衡。

接下来的问题就是怎么旋转了。我们可以把节点15–>节点70–>节点30连起来看，是不是很熟悉？这就是上面重复了两次的右子树内侧插入的场景，那么首先对节点70进行右旋，右旋后的结果为：

下一步，节点70的父节点着色为黑色，节点70的祖父节点着色为红色（这一步不理解或者忘了为什么的，可以去看一下之前对于fixAfterInsertion方法的解读），重新着色后的结构为：

最后一步，对节点70的父节点节点15进行一次左旋，左旋之后的结构为：

重新恢复红黑树的性质：

1. 根节点为黑色节点
2. 没有连续红色节点
3. 根节点到所有叶子节点经过的黑色节点都是2个

后记

本文通过不断向红黑树的右子树插入数据，演示了红黑树右侧插入时可能出现的各种情况且应当如何处理这些情况，左侧插入同理。

红黑树还是有点难，因此我个人建议在学习红黑树的时候一定要多画（像我个人就画了3张A4纸）+多想，这样才能更好地理解红黑树的原理，尤其是旋转的原理。

TreeMap的插入操作和旋转操作已经讲完，后文会着眼于TreeMap的删除操作以及一些统计操作（比如找到节点比50大的所有节点）是如何实现的。