红黑树是一棵特殊的二叉查找树，是一种平衡二叉树。
二叉查找树的特点：

  1. 左子树上所有节点的值均小于或等于它的根节点的值
  2. 右子树上素有节点的值均大于或等于它的根节点的值
  3. 左右子树也分别为二叉排序树

但极端情况下会退化为线性查找。

1. 红黑树的特征

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

上述特征实现了红黑树的自平衡，红黑树从根到叶子的最长路径不会超过最短路径的2倍。

2. 红黑树的插入调整

向红黑树中插入的所有节点都是红色节点，当不符合红黑树的5条特征时需要进行调整。
调整有两种方法：变色和旋转
因为插入的节点是红色的，所以最先产生的问题会是出现两个连续红色节点，这种时候会进行**变色**；
叔红则变色，叔黑则变色+旋转
爷左父右、爷右父左转两次！
分四种情况讨论：

| while(x != null && x != root && x.parent.color == RED) {
1. x的父节点是x爷节点的左节点
1. x的爷节点的右节点是红色(叔红)
1. 父->黑
1. 叔->黑
1. 爷->红
1. x -> 爷
2. x的爷节点的右节点是黑色（叔黑）
1. 如果x为父节点的右节点{x->父 ；**右旋(x)**}
1. 父->黑
1. 爷->红
1. 右旋（爷）
2. x的父节点是x爷节点的右节点
1. x**的爷节点的左节点是红色
1. 父->黑
1. 叔->黑
1. 爷->红
1. x -> 爷
2. x的爷节点的左节点是黑色
1. 如果x为父节点的左节点{x->父 ；左旋(x)}
1. 父->黑
1. 爷->红
1. 左旋（爷）
}** | | —- |

image.png
image.png

3. TreeMap红黑树插入调整源码：

  1. private void fixAfterInsertion(Entry<K,V> x) {
  2.     x.color = RED;
  4.     //如果x的父节点为红色才会进行调整
  5.     while (x != null && x != root && x.parent.color == RED) {
  6.         if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
  7.             Entry<K,V> y = rightOf(parentOf(parentOf(x)));
  8.             if (colorOf(y) == RED) {
  9.                 setColor(parentOf(x), BLACK);
  10.                 setColor(y, BLACK);
  11.                 setColor(parentOf(parentOf(x)), RED);
  12.                 x = parentOf(parentOf(x));
  13.             } else {
  14.                 if (x == rightOf(parentOf(x))) {
  15.                     x = parentOf(x);
  16.                     rotateLeft(x);
  17.                 }
  18.                 setColor(parentOf(x), BLACK);
  19.                 setColor(parentOf(parentOf(x)), RED);
  20.                 rotateRight(parentOf(parentOf(x)));
  21.             }
  22.         } else {
  23.             Entry<K,V> y = leftOf(parentOf(parentOf(x)));
  24.             if (colorOf(y) == RED) {
  25.                 setColor(parentOf(x), BLACK);
  26.                 setColor(y, BLACK);
  27.                 setColor(parentOf(parentOf(x)), RED);
  28.                 x = parentOf(parentOf(x));
  29.             } else {
  30.                 if (x == leftOf(parentOf(x))) {
  31.                     x = parentOf(x);
  32.                     rotateRight(x);
  33.                 }
  34.                 setColor(parentOf(x), BLACK);
  35.                 setColor(parentOf(parentOf(x)), RED);
  36.                 rotateLeft(parentOf(parentOf(x)));
  37.             }
  38.         }
  39.     }
  40.     root.color = BLACK;
  41. }

4. 红黑树的应用场景

红黑树在JDK1.8中应用于 TreeMap 和 HashMap的底层结构。