在看jdk的HashMap的代码的时候，看到了jdk8的实现方式用到了红黑树，然后，就看了一下。

废话少讲，开始红黑树的简介。

红黑树的特性

1.每个节点或者是黑色，或者是红色。

2.根节点是黑色。

3.每个叶子节点是黑色。 [注意：这里叶子节点，是指为空的叶子节点！

4.如果一个节点是红色的，则它的子节点必须是黑色的。

5.从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。

红黑树的添加：

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

第二步：将插入的节点着色为”红色”。

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

伪代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
RB-INSERT(T, z)  
01  y ← nil[T]                        // 新建节点“y”，将y设为空节点。
02  x ← root[T]                       // 设“红黑树T”的根节点为“x”
03  while x ≠ nil[T]                  // 找出要插入的节点“z”在二叉树T中的位置“y”
04      do y ← x                      
05         if key[z] < key[x]  
06            then x ← left[x]  
07            else x ← right[x]  
08  p[z] ← y                          // 设置 “z的父亲” 为 “y”
09  if y = nil[T]                     
10     then root[T] ← z               // 情况1：若y是空节点，则将z设为根
11     else if key[z] < key[y]        
12             then left[y] ← z       // 情况2：若“z所包含的值” < “y所包含的值”，则将z设为“y的左孩子”
13             else right[y] ← z      // 情况3：(“z所包含的值” >= “y所包含的值”)将z设为“y的右孩子” 
14  left[z] ← nil[T]                  // z的左孩子设为空
15  right[z] ← nil[T]                 // z的右孩子设为空。至此，已经完成将“节点z插入到二叉树”中了。
16  color[z] ← RED                    // 将z着色为“红色”
17  RB-INSERT-FIXUP(T, z)             // 通过RB-INSERT-FIXUP对红黑树的节点进行颜色修改以及旋转，让树T仍然是一颗红黑树