二叉查找树（Binary Search Tree）擅长数据的查找。它的特点是：

对于任意节点，它的左子树上的所有节点的值都小于它，而它的右子树上的所有节点的值都大于它。

红黑树（Red-Black Tree）本质上也是二叉查找树，但它额外引入了5个条件：

1. 节点只能是黑色或红色；
2. 根节点必须是黑色；
3. 所有NIL节点都是黑色；
4. 一条路径上不能出现相邻的两个红色节点；
5. 在任何递归子树内，根节点到叶子节点的所有路径上包含相同数目的黑色节点。

NIL即Nothing In Leaf，它是一种虚拟节点，出现于任何实际子节点不足2个的节点上：

条件5提到的黑色节点，包括NIL节点。当插入的节点是黑色时，红黑树必定不满足条件5。而当插入的节点是红色时，红黑树反而仍有可能满足条件5。

因此，新插入红黑树的节点默认是红色。

在Java中，TreeMap实现了基于红黑树（Red-Black Tree）的NavigableMap接口。此映射根据其键的自然顺序进行排序，或者根据创建映射时提供的Comparator进行排序，具体取决于使用的构造方法。

在TreeMap类中，put、delete方法分别依赖私有方法fixAfterInsertion和fixAfterDeletion。前者用于对插入的节点进行调整，后者用于对删除的节点进行调整。

本文以fixAfterInsertion为例。以下是此方法的部分源码。

private void fixAfterInsertion(Entry<K,V> x) {
    x.color = RED;
    // 如果x不为空，也不是根节点，并且x的父节点的颜色是红色
    while (x != null && x != root && x.parent.color == RED) {
        // 如果x的父节点是x的祖父节点的左子节点
        if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
            // 节点y是x的祖父节点的右子节点
            Entry<K,V> y = rightOf(parentOf(parentOf(x)));
            // 如果y的颜色是红色
            if (colorOf(y) == RED) {
                // 设置x的父节点为黑色
                setColor(parentOf(x), BLACK);
                // 设置y的颜色为黑色
                setColor(y, BLACK);
                // 设置x的祖父节点为红色
                setColor(parentOf(parentOf(x)), RED);
                // 以x的祖父节点作为x，再次执行循环判断
                x = parentOf(parentOf(x));
                // 如果y的颜色是黑色
            } else {
                // 如果x是父节点的右子节点
                if (x == rightOf(parentO8f(x))) {
                    // 以x的父节点作为x
                    x = parentOf(x);
                    // 将x左旋
                    rotateLeft(x);
                }
                // 设置x的父节点为黑色
                setColor(parentOf(x), BLACK);
                // 设置x的祖父节点为红色
                setColor(parentOf(parentOf(x)), RED);
                // 将x的祖父节点右旋
                rotateRight(parentOf(parentOf(x)));
            }
            // 如果x的父节点是祖父节点的右子节点
        } else {
            ...
        }
    }
    root.color = BLACK;
}
// 此处不再给出rotateLeft、rotateRight方法的源码

当新插入节点a的父节点b也是红色时，有两种情形：

1）b的兄弟节点是黑色。

当a是b的右子节点，而b是a的祖父节点的左子节点时，红黑树的变化如图所示：

上图中的红黑树发生了两次旋转：

第一次，b向左旋转，成为a的左子节点。此时的情形与首次插入的a位于b的左侧的情形完全相同。

第二次，当前位置的a的父节点向右旋转，成为a的右子节点。

当a是b的左子节点，而b是a的祖父节点的右子节点时，红黑树的变化如图所示：

上图中的红黑树发生了两次旋转：

第一次，b向右旋转，成为a的右子节点。此时的情形与首次插入的a位于b的右侧的情形完全相同。

第二次，当前位置的a的父节点向左旋转，成为a的左子节点。

2）b的兄弟节点是红色。

此时，a、b、b的兄弟节点都是红色，红黑树的变化如图所示：

这种情形比较简单，将b、b的兄弟节点置为黑色，同时将a的祖父节点c置为红色，即可保持两分支的黑色节点数量相同。

由于c是红色，当c不是根节点并且c的父节点的颜色也是红色时，须继续依照以上两种情形向上判断并执行相应操作。