线程不安全，但是因为需要排序，进行key的compareTo方法，所以key是不能null中，value是可以的。
首先庖丁解牛,类似于如何把大象装入冰箱,分三步走:
- 以排序二叉树的方式新增节点
因为红黑树首先本身就是一个排序二叉树 - 标记它为红色
如果设为黑色，就会导致根到叶的路径上有一条路上，多一个额外的黑节点，打破性质 5,这个很难调整
但设为红色节点后，可能会导致出现两个连续红色节点的冲突，那么可以通过 - 颜色调换（color flips）和树旋转
调整
之后再要进行什么操作就取决于其他临近节点的颜色
注意到:
- 性质1/2/3总是保持
- 性质4只在增加红色节点、重绘黑色节点为红色，或做旋转时受到威胁
- 性质5只在增加黑色节点、重绘红色节点为黑色，或做旋转时受到威胁
在下面的示意图中，
- 要插入的节点标为N
- N的父节点标为P
- N的祖节点标为G
- N的叔节点标为U
图中展示的任何颜色要么是由它所处情形这些所作的假定，要么就是由假定所自然推出的
插入情境分类
1 N 位于树的根,即无父节点
直接将新插入节点设置为根即可.
这种情形下，把它绘为黑色 - 满足性质2
它在每个路径上对黑节点数目加一 - 满足性质5
2 P 是黑色
直接将N插入即可，不会破坏性质4(N 是红色的).
在这种情形下,性质5未受到威胁，尽管N有两个黑色叶子子节点；但由于N是红色，通过它的每个子节点的路径就都有同通过它所取代的黑色的叶子的路径同样数目的黑色节点，所以依然满足这个性质。
在下面情境下,假定P为红色，所以它有祖节点G.
因为若P是根，则P就应是黑色。所以N总有一个叔节点，尽管在情形4和5下它可能是叶节点
这种情况下会破坏性质 4,所以又分为如下几种情境:
3 P 和 U都是红色
此时N做为P的左孩子或右孩子都属于本情境.
- 这里仅图解N做为P左孩子的情境
将G设为红色，P和U设为黑色 - 以保持性质5.
现在N有了一个黑色的父节点P。因为通过父节点P或叔节点U的任何路径都必定通过祖节点G，在这些路径上的黑节点数目没有改变.
But!
红色的祖节点G可能是根,破坏性质2
也可能祖节点G的父节点是红色的，破坏性质4
为了解决这个问题，在祖节点G递归进行情境1.
以下情境，假定P是G的左子节点
4 P是红色,U是黑色或缺少,N是P的右孩子
左旋P,调换 N 和 P 的角色
这个改变会导致某些路径通过它们以前不通过的N（比如图中的1号叶节点）或不通过P（比如图中3号叶节点），但由于这两个节点都是红色，性质5仍有效
但P和N还是连续的两个红色节点，破坏性质 4还，怎么办?看情境5
5 P是红色,U是黑色或缺少，N是P的左子节点
操作前G是黑色，否则P不可能是红色(如果P和G都是红色就破坏了性质4)
右旋G，将P设为黑色，G设为红色，达到平衡.此时P是黑色，不用担心P的父节点是红色.
图解完毕,我们来看源码吧!
public V put(K key, V value) { // 根节点 Entry<K,V> t = root; // 若根为空 if (t == null) { compare(key, key); // 类型校验(可能是 null) // 创建一个根 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) { // 循环查找key要插入的位置(也就是新节点的父节点) do { // 记录上次循环的节点t parent = t; // 比较当前节点key和新插入节点key的大小 cmp = cpr.compare(key, t.key); // 新key小，以当前节点的左孩子节点为新的比较节点 if (cmp < 0) t = t.left; // 新key大，则以当前节点的右孩子节点为新的比较节点 else if (cmp > 0) t = t.right; else // 当前节点key和新key相等，则覆盖value并返回 return t.setValue(value); // 当t为null，即没有要比较节点时，表已找到新节点要插入位置 } while (t != null); } // 比较器为空,使用 key 的比较器 else { // 因此要求key不能为null，并且须实现Comparable接口 if (key == null) throw new NullPointerException(); @SuppressWarnings("unchecked") 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); // 新节点key值小于父节点key if (cmp < 0) // 插在父节点左子处 parent.left = e; // 如果新节点key值大于父节点key else // 插在父节点的右子处 parent.right = e; // 插入新节点后，为维持平衡，调整红黑树 fixAfterInsertion(e); // 元素数量加一 size++; // 修改计数器加一 modCount++; return null; }
下面来看新增节点后对红黑树的调整方法
private void fixAfterInsertion(Entry<K,V> x) { // 将新插入节点的颜色设置为红色 x.color = RED; // 循环保证新插入节点x不是根或其父节点不是红色(这两种情况无需调整) while (x != null && x != root && x. parent.color == RED) { // 若x的父节点是祖节点的左孩子 if (parentOf(x) == leftOf(parentOf (parentOf(x)))) { // 获取x的叔节点 Entry<K,V> y = rightOf(parentOf (parentOf(x))); // 若x的父节点是红色 if (colorOf(y) == RED) { // 将x的父节点设为黑色 setColor(parentOf (x), BLACK); // 将x的叔叔节点设置为黑色 setColor(y, BLACK); // 将x的祖节点设为红色 setColor(parentOf (parentOf(x)), RED); // 将x指向祖节点 // 若x的祖节点的父节点是红色，按照之前流程继续循环 x = parentOf(parentOf (x)); } else { // 若x的叔节点是黑色或缺少，且x的父节点是祖节点的右孩子 if (x == rightOf( parentOf(x))) { // 左旋父节点 x = parentOf(x); rotateLeft(x); } // 若x的叔叔节点是黑色或缺少，且x的父节点是祖父节点的左孩子 // 将x的父节点设为黑色 setColor(parentOf (x), BLACK); // 将x的祖节点设为红色 setColor(parentOf (parentOf(x)), RED); // 右旋x的祖节点 rotateRight( parentOf(parentOf (x))); } // 若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; }
下面来看下左旋和右旋的代码
/** * 左旋示意图: * px px * / / * x y * / \ --(左旋)-- / \ * lx y x ry * / \ / \ * ly ry lx ly * */ private void rotateLeft(Entry<K,V> p) { if (p != null) { // 获取p的右孩子 Entry<K,V> r = p.right; // 将 r的左孩子 设为 p的右孩子 p.right = r.left ; // 若r的左孩子非空，将p设为r的左孩子的父 if (r.left != null) r.left.parent = p; // 将p的父设为y的父 r.parent = p.parent; // 若p的父为空，则将r设为根 if (p.parent == null) root = r; // 若p是其父的左孩子，则将r设为p的父节点的左孩子 else if (p.parent.left == p) p.parent.left = r; else // 若p是其父的右孩子，则将r设为p的父节点的右孩子 p.parent.right = r; // 将p设为r的左孩子 r.left = p; // 将p的父设为r p.parent = r; } }
/** * 右旋示意图(对节点y右旋)： * py py * / / * y x * / \ --(右旋)-- / \ * x ry lx y * / \ / \ * lx rx rx ry * */ private void rotateRight(Entry<K,V> p) { if (p != null) { // 获取p的左孩子 Entry<K,V> l = p. left; // 将l的右孩子设为p的左孩子 p.left = l.right ; // 若l的右孩子非空，将p设为l的右孩子的父 if (l.right != null) l. right.parent = p; // 将p的父设为l的父 l.parent = p.parent ; // 若p的父为空,则将l设为根 if (p.parent == null) root = l; // 若p是其父的右孩子，则将l设为p的父节点的右孩子 else if (p.parent.right == p) p.parent.right = l; // 若p是其父节点的左孩子,将l设为p的父节点的左孩子 else p.parent.left = l; // 将p设为l的右孩子 l.right = p; // 将l设为p父节点 p.parent = l; } }
