# TreeMap 源码分析（上）

## 简介

`TreeMap  ` 最早出现在 `JDK 1.2` 中，是 Java 集合框架中比较重要一个的实现。TreeMap 底层基于 `红黑树` 实现，可保证在 `log(n)` 时间复杂度内完成 containsKey、get、put 和 remove 操作，效率很高。另一方面，由于 TreeMap 基于红黑树实现，这为 TreeMap 保持键的有序性打下了基础。

总的来说，TreeMap 的核心是红黑树，其很多方法也是对红黑树增删查基础操作的一个包装。所以只要弄懂了红黑树，TreeMap 就没什么秘密了。

TreeMap 常用操作如下：

```java
TreeMap<String, String> treeMap = new TreeMap<>();
treeMap.put("test","test"); // 添加数据
String value = treeMap.get("test"); // 根据 key 获取
treeMap.remove("test"); // 根据 key 移除
treeMap.clear(); // 清空
```

## 红黑树

红黑树（英语：Red–black tree）是一种自平衡二叉查找树，它在 1972 年由鲁道夫·贝尔发明，被称为「对称二叉 B 树」。

红黑树作为二叉查找树的一种，满足二叉查找树的一般性质，下面来了解下二叉查找树的一般性质。

### 二叉查找树

二叉查找树，也称有序二叉树（ordered binary tree），或已排序二叉树（sorted binary tree），是指一棵空树或者具有下列性质的二叉树：

- 若左子树不空，则左子树上所有节点的值均小于它的根节点的值；
- 若右子树不空，则右子树上所有节点的值均大于它的根节点的值；
- 左、右子树也分别为二叉排序树；
- 没有键值相等的节点。

![二叉树](https://raw.githubusercontent.com/jeanboydev/Android-ReadTheFuckingSourceCode/master/resources/images/java/basic/treemap/01.jpg)

相关术语：

- 节点
- 树根
- 树叶
- 高度、深度
- 路径
- 子节点、父节点、叔叔节点



因为一棵由 n 个节点随机构造的二叉查找树的高度为 `log(n)`，所以顺理成章，二叉查找树的一般操作的执行时间为 `O(log(n))`。但二叉查找树若退化成了一棵具有 n 个结点的线性链后，则这些操作最坏情况运行时间为 `O(n)`。

红黑树虽然本质上是一棵二叉查找树，但它在二叉查找树的基础上增加了着色和相关的性质使得红黑树相对平衡，从而保证了红黑树的查找、插入、删除的时间复杂度最坏为 `O(log(n))`。

### 红黑树的性质

但它是如何保证一棵 n 个节点的红黑树的高度始终保持在 `log(n)` 的呢？这就引出了红黑树的 5 个性质：

1. 节点是红色或黑色。
2. 根是黑色。
3. 所有叶子都是黑色（叶子是 NIL/NULL 节点）。
4. 每个红色节点必须有两个黑色的子节点。（从每个叶子到根的所有路径上不能有两个连续的红色节点。）
5. 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。

正是红黑树的这 5 条性质，使一棵 n 个结点的红黑树始终保持了 `log(n)` 的高度，从而也就解释了上面所说的「红黑树的查找、插入、删除的时间复杂度最坏为 `O(log(n))` 」这一结论成立的原因。

下面是一个具体的红黑树的图例：

![红黑树](https://raw.githubusercontent.com/jeanboydev/Android-ReadTheFuckingSourceCode/master/resources/images/java/basic/treemap/02.jpg)

### 树的旋转

红黑树的基本操作是添加、删除。在对红黑树进行添加或删除之后，都会用到旋转方法。

因为添加或删除红黑树中的节点之后，红黑树就发生了变化，可能不满足红黑树的 5 条性质，也就不再是一颗红黑树了，而是一颗普通的树。而通过旋转，可以使这颗树重新成为红黑树。

简单点说，旋转的目的是让树保持红黑树的特性。

旋转包括两种：「左旋」和「右旋」。下面分别对它们进行介绍。

#### 左旋

![左旋](https://raw.githubusercontent.com/jeanboydev/Android-ReadTheFuckingSourceCode/master/resources/images/java/basic/treemap/03.jpg)

对 x 进行左旋，意味「将 x 变成一个左节点」。伪代码如下：

```c
LEFT-ROTATE(T, x)
  // 前提：这里假设 x 的右孩子为 y。下面开始正式操作
	y = x.right
  // 将 “y 的左孩子” 设为 “x 的右孩子”，即将 β 设为 x 的右孩子
  x.right = y.left
  if y.left ≠ T.nil
  	// 将 “x” 设为 “y 的左孩子的父亲”，即将 β 的父亲设为 x
  	y.left.p = x
  // 将 “x 的父亲” 设为 “y 的父亲”
  y.p = x.p
  if x.p == T.nil // 情况 1：如果 “x 的父亲” 是空节点，
  	// 则将 y 设为根节点
		T.root = y
 	else if x == x.p.left // 情况 2：如果 x 是它父节点的左孩子，
 		// 则将 y 设为 “x 的父节点的左孩子”
		x.p.left = y
	else // 情况 3：(x 是它父节点的右孩子) 
		// 将 y 设为 “x 的父节点的右孩子”
		x.p.right = y
 y.left = x // 将 “x” 设为 “y 的左孩子”
 x.p = y // 将 “x 的父节点” 设为 “y”
```

#### 右旋

![右旋](https://raw.githubusercontent.com/jeanboydev/Android-ReadTheFuckingSourceCode/master/resources/images/java/basic/treemap/04.jpg)

对 x 进行左旋，意味着「将 x 变成一个左节点」。伪代码如下：

```c
RIGHT-ROTATE(T, y)
  // 前提：这里假设 y 的左孩子为 x。下面开始正式操作
  x = y.left
  // 将 “x 的右孩子” 设为 “y 的左孩子”，即将 β 设为 y 的左孩子
  y.left = x.right
  if x.right ≠ T.nil
  	// 将 “y” 设为 “x 的右孩子的父亲”，即将β 的父亲设为 y
  	x.right.p = y
  // 将 “y 的父亲” 设为 “x 的父亲”
  x.p = y.p
  if y.p == T.nil // 情况1：如果 “y 的父亲” 是空节点，
  	// 则将 x 设为根节点
		T.root = x
	else if y == y.p.right // 情况2：如果 y 是它父节点的右孩子，
		// 则将 x 设为“y 的父节点的左孩子”
		y.p.right = x
	else // 情况3：(y 是它父节点的左孩子) 
		// 将 x 设为“y 的父节点的左孩子”
		y.p.left = x
 x.right = y // 将 “y” 设为 “x 的右孩子”
 y.p = x // 将 “y 的父节点” 设为 “x”
```

## 红黑树的插入

将一个节点插入到红黑树中，需要执行哪些步骤呢？

首先，将红黑树当作一颗二叉查找树，将节点插入；然后，将节点着色为红色；最后，通过旋转和重新着色等方法来修正该树，使之重新成为一颗红黑树。详细描述如下：

### 第一步：将红黑树当作一颗二叉查找树，将节点插入。

红黑树本身就是一颗二叉查找树，将节点插入后，该树仍然是一颗二叉查找树。也就意味着，树的键值仍然是有序的。

此外，无论是左旋还是右旋，若旋转之前这棵树是二叉查找树，旋转之后它一定还是二叉查找树。这也就意味着，任何的旋转和重新着色操作，都不会改变它仍然是一颗二叉查找树的事实。

### 第二步：将插入的节点着色为「红色」。

为什么着色成红色，而不是黑色呢？为什么呢？在回答之前，我们需要重新温习一下红黑树的特性：

1. 节点是红色或黑色。
2. 根是黑色。
3. 所有叶子都是黑色（叶子是 NIL/NULL 节点）。
4. 每个红色节点必须有两个黑色的子节点。（从每个叶子到根的所有路径上不能有两个连续的红色节点。）
5. 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。

将插入的节点着色为红色，不会违背「特性 5」。少违背一条特性，就意味着我们需要处理的情况越少。接下来，就要努力的让这棵树满足其它性质即可；满足了的话，它就又是一颗红黑树了。

### 第三步：修正红黑树

通过一系列的旋转或着色等操作，使之重新成为一颗红黑树。

第二步中，将插入节点着色为「红色」之后，不会违背「特性 5」。那它到底会违背哪些特性呢？

- 对于「特性 1」，显然不会违背了。因为我们已经将它涂成红色了。

- 对于「特性 2」，显然也不会违背。在第一步中，我们是将红黑树当作二叉查找树，然后执行的插入操作。而根据二叉查找数的特点，插入操作不会改变根节点。所以，根节点仍然是黑色。

- 对于「特性 3」，显然不会违背了。这里的叶子节点是指的空叶子节点，插入非空节点并不会对它们造成影响。

- 对于「特性 4」，是有可能违背的！

那接下来，想办法使之「满足特性 4」，就可以将树重新构造成红黑树了。

下面看看代码到底是怎样实现这三步的，伪代码如下：

```c
RB-INSERT(T, z)
  // 新建节点 “y”，将 y 设为空节点。
  y = T.nil
  // 设 “红黑树 T” 的根节点为 “x”
  x = T.root
  // 找出要插入的节点 “z” 在二叉树T中的位置 “y”
  while x ≠ T.nil
		y = x                      
		if z.key < x.key  
			x = x.left
		else x = x.right
	z.p = y // 设置 “z 的父亲” 为 “y”
	if y == T.nil // 情况 1：若 y 是空节点，则将 z 设为根                  
    T.root = z
	else if z.key < y.key // 情况 2：若 “z 所包含的值” < “y 所包含的值”，
		y.left = z // 则将 z 设为 “y 的左孩子”
	else // 情况 3：(“z 所包含的值” >= “y 所包含的值”)
		y.right = z // 将 z 设为 “y 的右孩子”
	z.left = T.nil // z 的左孩子设为空
	// z 的右孩子设为空。至此，已经完成将 “节点 z 插入到二叉树” 中了。
	z.right = T.nil
	z.color = RED // 将 z 着色为“红色”
	// 通过 RB-INSERT-FIXUP 对红黑树的节点进行颜色修改以及旋转，
	// 让树T仍然是一颗红黑树
	RB-INSERT-FIXUP(T, z) 
```

根据被插入节点的父节点的情况，可以将当节点 z 被着色为红色节点，并插入二叉树"划分为三种情况来处理。

- 情况一：被插入的节点是根节点。

处理方法：直接把此节点涂为黑色。

- 情况二：被插入的节点的父节点是黑色。

处理方法：什么也不需要做。节点被插入后，仍然是红黑树。

- 情况三：被插入的节点的父节点是红色。

处理方法：那么，该情况与红黑树的「特性 5」相冲突。

这种情况下，被插入节点是一定存在非空祖父节点的；进一步的讲，被插入节点也一定存在叔叔节点（即使叔叔节点为空，我们也视之为存在，空节点本身就是黑色节点）。理解这点之后，我们依据「叔叔节点的情况」，将这种情况进一步划分为 3 种情况（Case）。

```c
RB-INSERT-FIXUP(T, z)
  // 若 “当前节点 z 的父节点是红色”，则进行以下处理。
  while z.p.color == RED
  	// 若 “z 的父节点” 是 “z 的祖父节点的左孩子”，则进行以下处理。
    if z.p == z.p.p.left
			// 将 y 设置为 “z 的叔叔节点（z 的祖父节点的右孩子）”
			y = z.p.p.right
      if y.color == RED // Case 1 条件：叔叔是红色
        z.p.color = BLACK // Case 1：(01) 将 “父节点” 设为黑色。
        y.color = BLACK // Case 1：(02) 将 “叔叔节点” 设为黑色。
        z.p.p.color = RED // Case 1：(03) 将 “祖父节点” 设为 “红色”。
        z = z.p.p // Case 1：(04) 将 “祖父节点” 设为 “当前节点” (红色节点)
			else
				if z == z.p.right // Case 2 条件：叔叔是黑色，且当前节点是右孩子
          z = z.p // Case 2：(01) 将 “父节点” 作为 “新的当前节点”。
          LEFT-ROTATE(T, z) // Case 2：(02) 以 “新的当前节点” 为支点进行左旋。
				// Case 3 条件：叔叔是黑色，且当前节点是左孩子。
        z.p.color = BLACK // Case 3：(01) 将 “父节点” 设为 “黑色”。
        z.p.p.color = RED // Case 3：(02) 将 “祖父节点” 设为 “红色”。
        RIGHT-ROTATE(T, z.p.p) // Case 3：(03) 以 “祖父节点” 为支点进行右旋。
		else // 若 “z 的父节点” 是 “z 的祖父节点的右孩子”，
      // 将上面的操作中 “right” 和 “left” 交换位置，然后依次执行。
      (same as then clause with "right" and "left" exchanged)      
	T.root.color = BLACK
```

上面三种情况（Case）处理问题的核心思路都是：将红色的节点移到根节点；然后，将根节点设为黑色。下面对它们详细进行介绍。

#### Case 1：叔叔是红色

如下如，当前节点（即被插入节点）的父节点是红色，且当前节点的祖父节点的另一个子节点（叔叔节点）也是红色。

![Case 1](https://raw.githubusercontent.com/jeanboydev/Android-ReadTheFuckingSourceCode/master/resources/images/java/basic/treemap/05.jpg)

处理策略：

1. 将「父节点」设为黑色。
2. 将「叔叔节点」设为黑色。
3. 将「祖父节点」设为「红色」。
4. 将「祖父节点」设为「当前节点」；然后再对当前节点进行操作。

下面说明谈谈为什么这么处理？

首先，「当前节点」和「父节点」都是红色，违背「特征 4」。所以将「父节点」设为「黑色」以解决这个问题。

但是，将「父节点」由「红色」变成「黑色」之后，违背了「特征 5」。因为包含「父节点」的分支黑色节点的总数增加了 1。解决这个问题的方法就是将「祖父节点」由「黑色」变成「红色」，同时将「叔叔节点」由「红色」变成「黑色」。

这里会有几个疑问：

- 第一，为什么「祖父节点」之前是黑色的？

这个应该很容易想明白，因为在变换操作之前，该树是红黑树，「父节点」是红色，那么「祖父节点」一定是黑色。

- 第二，为什么将「祖父节点」由「黑色」变成「红色」，同时，将「叔叔节点」由「红色」变成「黑色」；能解决「包含父节点的分支的黑色节点的总数增加了1 」的问题？

这个道理也很简单。「包含父节点的分支的黑色节点的总数增加了 1」同时也意味着「包含祖父节点的分支的黑色节点的总数增加了 1」。

既然这样，我们通过将「祖父节点」由「黑色」变成「红色」以解决“包含「包含父节点的分支的黑色节点的总数增加了 1」的问题；但是，这样处理之后又会引起另一个问题「包含叔叔节点的分支的黑色节点的总数减少了 1」。

现在我们已知「叔叔节点」是「红色」，将「叔叔节点」设为「黑色」就能解决这个问题。 所以，将「祖父节点」由“黑色”变成红色，同时，将「叔叔节」由「红色」变成「黑色」；就解决了该问题。

按照上面的步骤处理之后：当前节点、父节点、叔叔节点之间都不会违背红黑树特性，但祖父节点却不一定。若此时，祖父节点是根节点，直接将祖父节点设为「黑色」，那就完全解决这个问题了；若祖父节点不是根节点，那我们需要将「祖父节点」设为「新的当前节点」，接着对「新的当前节点」进行分析。

#### Case 2：叔叔是黑色，且当前节点是右孩子

如下图，当前节点（即被插入节点）的父节点是红色，叔叔节点是黑色，且当前节点是其父节点的右孩子。

![Case 2](https://raw.githubusercontent.com/jeanboydev/Android-ReadTheFuckingSourceCode/master/resources/images/java/basic/treemap/06.jpg)

处理策略：

1. 将「父节点」作为「新的当前节点」。
2. 以「新的当前节点」为支点进行左旋。

下面说明谈谈为什么这么处理？

首先，将「父节点」作为「新的当前节点」；接着，以「新的当前节点」为支点进行左旋。 为了便于理解，我们先说明第 2 步，再说明第 1 步；为了便于说明，我们设置「父节点」的代号为 F（Father），「当前节点」的代号为 S（Son）。

为什么要以 F 为支点进行左旋呢？根据已知条件可知：S 是 F 的右孩子。而之前我们说过，我们处理红黑树的核心思想：将红色的节点移到根节点；然后，将根节点设为黑色。

既然是「将红色的节点移到根节点」，那就是说要不断的将破坏红黑树特性的红色节点上移(即向根方向移动)。 而 S 又是一个右孩子，因此，我们可以通过「左旋」来将 S 上移。 

按照上面的步骤（以 F 为支点进行左旋）处理之后：若 S 变成了根节点，那么直接将其设为「黑色」，就完全解决问题了。若 S 不是根节点，那我们需要执行步骤 1，即「将 F 设为新的当前节点」。

那为什么不继续以 S 为新的当前节点继续处理，而需要以 F 为新的当前节点来进行处理呢？这是因为「左旋」之后，F 变成了 S 的「子节点」，即 S 变成了 F 的父节点；而我们处理问题的时候，需要从下至上「由叶到根」方向进行处理；也就是说，必须先解决「孩子」的问题，再解决「父亲」的问题；所以，我们执行步骤 1：将「父节点」作为「新的当前节点」。

#### Case 3：叔叔是黑色，且当前节点是左孩子

如下图，当前节点（即，被插入节点）的父节点是红色，叔叔节点是黑色，且当前节点是其父节点的左孩子。

![Case 3](https://raw.githubusercontent.com/jeanboydev/Android-ReadTheFuckingSourceCode/master/resources/images/java/basic/treemap/07.jpg)

处理策略：

1. 将「父节点」设为「黑色」。
2. 将「祖父节点」设为「红色」。
3.  以「祖父节点」为支点进行右旋。

下面说明谈谈为什么这么处理？

为了便于说明，我们设置「当前节点」为 S（Original Son），「兄弟节点」为 B（Brother），「叔叔节点」为 U（Uncle），「父节点」为 F（Father），祖父节点为 G（Grand-Father）。

S 和 F 都是红色，违背了红黑树的「特性 4」，我们可以将 F 由「红色」变为「黑色」，就解决了违背「特性 4」的问题；但却引起了其它问题：违背「特性 5」，因为将 F 由红色改为黑色之后，所有经过 F 的分支的黑色节点的个数增加了 1。

那我们如何解决「所有经过 F 的分支的黑色节点的个数增加了 1」的问题呢？ 我们可以通过「将 G 由黑色变成红色」，同时「以 G 为支点进行右旋」来解决。

进行 Case 3 处理之后，再将节点「120」当作当前节点，就变成了 Case 2 的情况。

## 小结

好了到这里我们已经分析完了红黑树插入数据的操作，本文就到这里了。删除数据的操作我们下一篇继续分析。