本文共 8170 字，大约阅读时间需要 27 分钟。

线程不安全，但是因为需要排序，进行key的compareTo方法，所以key是不能null中，value是可以的。

首先庖丁解牛,类似于如何把大象装入冰箱,分三步走:

1. 以排序二叉树的方式新增节点
   因为红黑树首先本身就是一个排序二叉树
2. 标记它为红色
   如果设为黑色，就会导致根到叶的路径上有一条路上，多一个额外的黑节点，打破性质 5,这个很难调整
   但设为红色节点后，可能会导致出现两个连续红色节点的冲突，那么可以通过
3. 颜色调换（color flips）和树旋转
   调整

之后再要进行什么操作就取决于其他临近节点的颜色

注意到:

• 性质1/2/3总是保持
• 性质4只在增加红色节点、重绘黑色节点为红色，或做旋转时受到威胁
• 性质5只在增加黑色节点、重绘红色节点为黑色，或做旋转时受到威胁

在下面的示意图中，

• 要插入的节点标为N
• N的父节点标为P
• N的祖节点标为G
• N的叔节点标为U

图中展示的任何颜色要么是由它所处情形这些所作的假定，要么就是由假定所自然推出的

插入情境分类

1 N 位于树的根,即无父节点

直接将新插入节点设置为根即可.

2 P 是黑色

直接将N插入即可，不会破坏性质4(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的右孩子

这个改变会导致某些路径通过它们以前不通过的N（比如图中的1号叶节点）或不通过P（比如图中3号叶节点），但由于这两个节点都是红色，性质5仍有效

但P和N还是连续的两个红色节点，破坏性质 4还，怎么办?看情境5

5 P是红色,U是黑色或缺少，N是P的左子节点

右旋G，将P设为黑色，G设为红色，达到平衡.此时P是黑色，不用担心P的父节点是红色.

图解完毕,我们来看源码吧!

public V put(K key, V value) {
       	// 根节点        Entry
   
     t = root;        // 若根为空        if (t == null) {
               compare(key, key); // 类型校验(可能是 null)			// 创建一个根            root = new Entry<>(key, value, null);            // 有一个根元素了            size = 1;            // 修改计数器勿忘加一            modCount++;            // 返回            return null;        }        // 记录比较结果        int cmp;        Entry
    
      parent;        // split comparator and comparable paths        // 当前使用的比较器        Comparator
      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
      k = (Comparable
     ) 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
     
       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
   
     x) {
           // 将新插入节点的颜色设置为红色        x.color = RED;        // 循环保证新插入节点x不是根或其父节点不是红色(这两种情况无需调整)        while (x != null && x != root && x. parent.color == RED) {
               // 若x的父节点是祖节点的左孩子            if (parentOf(x) == leftOf(parentOf (parentOf(x)))) {
                   // 获取x的叔节点                Entry
    
      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
     
       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
   
     p) {
           if (p != null) {
               //  获取p的右孩子            Entry
    
      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
   
     p) {
           if (p != null) {
               // 获取p的左孩子            Entry
    
      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;        }    }
    
   

转载地址：https://javaedge.blog.csdn.net/article/details/105443666 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！