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

简介：红黑树是为了平衡二叉树而存在的一种树，二叉树在生成的时候，是非常容易失衡的，造成最坏的情况就是一边倒（左子树，或者右子树），这样会造成检索效率降低。

    红黑树是满足以下条件：

    1、每个节点要么是红色，要么是黑色

    2、根节点必须是黑色

    3、红色节点不能连续（与红色节点相连的节点都不能是红色）

    4、对于每个节点，从该节点到叶子节点（null）的任何路径，所包含的黑色节点数量必须相同

因此对于红黑树的添加，删除操作，都会造成树结构的改变，这时候就需要重新对树进行调整，可能是节点颜色的修改，也可能是整个结构的修改，而对于结构的修改，最常用到的就是对于节点的左旋和右旋

左旋

    左旋定义：将当前节点（x）的右子树(y），按照逆时针方向进行旋转，使y子树成为x节点的父节点，而y节点的左子树是x节点。（需要反复理解透彻）

    

TreeMap中关于左旋的代码处理

 

/** From CLR */private void rotateLeft(Entry
   
     p) {    if (p != null) { //p=3        Entry
    
      r = p.right; //① r=10        p.right = r.left; //② 3.right = 6 指定了3 的右子节点为6        if (r.left != null)            r.left.parent = p; //③ 将6的父节点指向 3        r.parent = p.parent; // ④ 将3的父节点 指向10        if (p.parent == null) // ⑤            root = r;        else if (p.parent.left == p)            p.parent.left = r;        else            p.parent.right = r;        r.left = p; // ⑥        p.parent = r; // ⑦    }}
    
   

① 记录需要左旋的右子节点

② 将右子节点的左子节点父给当前需要左旋操作的节点的右节点（有点绕）

③如果当前节点的右子节点的左子节点不为null（本图中是6），将6的父节点指向3 （这个地方一开始好长时间我是理解不了的，在②的时候只是单向的将3的右子节点指向了6，而这个操作是将6这个节点中维护的父节点由原来的是10指向了3）

④ 当前节点的父节点指向左旋后元素的父节点（也就是原来3的父节点指向了10）

⑤ 判断父节点的类型，如果父节点是null, 那就把旋转后的节点作为根节点，如果3是其父节点的左子节点，那么10就赋给原父节点的左子节点，如果3原来是其父节点的右子节点，那么左旋之后10就是其父子节点的右子节点

⑥将原来右子节点的左子节点指向被旋转的节点

⑦将右子节点指向被旋转的父节点

第⑥和第⑦是左旋的关键，中间关于旋转后的所有节点的指向，左旋和右旋比较类似。最关键的就是左旋操作，将需要旋转的右节点，作为该节点的父节点，而该父节点的左子节点是被旋转对象。

右旋

    右旋是将该节点（x）的左子节点，顺时针旋转，使得x的父节点是x的左子节点（y）,y的右子节点是x,

 

private void rotateRight(Entry
   
     p) {    if (p != null) {        Entry
    
      l = p.left; //获取当前分支左子树        p.left = l.right; //将左子树的右子节点指向 p的左子节点，即将10的左子节点指向6        if (l.right != null) l.right.parent = p;  // 将6的父节点指向10         l.parent = p.parent;  //将原来10 的父节点指向3        if (p.parent == null)             root = l;  //如果10的父节点为null        else if (p.parent.right == p) // 如果原来的 10 是其父节点的右子树，那么将 3 也任然赋给其父节点的右子树            p.parent.right = l;        else p.parent.left = l; //否则的话，就是将3 指向其父节点的左子树        l.right = p; // 3的右子树是 10        p.parent = l; // 10的父节点是3    }}
    
   

以上就是右旋操作，关于左旋和右旋，是每次调整红黑树的基础，一定要自己在纸上多联系，多思考。

红黑树添加元素操作put(k,v)

public V put(K key, V value) {    Entry
   
     t = root;    if (t == null) {        compare(key, key); // type (and possibly null) check        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) {        do {            parent = t;            cmp = cpr.compare(key, t.key);            if (cmp < 0)                t = t.left;            else if (cmp > 0)                t = t.right;            else                return t.setValue(value);        } while (t != null);    }    else {        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);    if (cmp < 0)        parent.left = e;    else        parent.right = e;    fixAfterInsertion(e);    size++;    modCount++;    return null;
     
    
   

以上，如果当前添加时，没有根节点，将当前元素作为根节点，然后返回

1、如果当前对象中是有比较器的话，判断加入元素的key和根节点的key大小比较，如果大于根节点，往根节点的右子树移动，接着判断根节点的右子树与添加元素的key, 如果小于，转向左子树，直到t的值为null, 而parent为t的父节点，非null

2、如果当前比较器不存在，将key强制转化为比较器，其他操作同上

3、如果是比较器结果小于0，将添加的元素放在左子节点处，否则放在右子节点处

4、调整红黑树，这个部分是最复杂且关键的地方。

我们先看下插入时代码部分

private void fixAfterInsertion(Entry
   
     x) {    x.color = RED;    while (x != null && x != root && x.parent.color == RED) {        if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {            Entry
    
      y = rightOf(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 == rightOf(parentOf(x))) {                    x = parentOf(x);                    rotateLeft(x);                }                setColor(parentOf(x), BLACK);                setColor(parentOf(parentOf(x)), RED);                rotateRight(parentOf(parentOf(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;}
     
    
   

对于新添加的节点，会将颜色设置成是红色，原因是红黑树上述中第四条，每个节点出发到期所有叶子节点经过的全部路径，黑色节点数相同。如果所有节点添加时，默认都为黑色，难以保证黑色节点数目都相同。

当前条件的条件基于：插入节点不是根节点，且插入节点的父节点的颜色不是红色

1、当前节点的父节点是其祖父节点的左子节点

2、获取到当前插入节点的叔父节点，2、1 如果其叔父节点的颜色是红色---》

                                                                 <1>将其节点的父节点，叔父节点的颜色设置成黑色，

                                                                 <2>将其祖父节点设置成红色，

                                                                 <3>将其祖父节点赋给x, 并进入while条件判断

                                                        2、2如果其叔父节点的颜色不是黑色

                                                              先判断，当前节点是左子树内插入，还是左子树外插入，如果是左子树，外插入，获                                                                取到当前节点父节点进行左旋操作。此时x是原来的父节点，

                                                              然后将x父节点设置成黑色，x的祖父节点设置成红色，将x的祖父节点进行右旋操作。

                                                               如果是左子树外侧插入，将x节点父节点设置成黑色，x祖父节点设置成红色

                                                                对x祖父节点进行右旋操作

左侧为左子树外侧，右图为左子树内侧

同样，如果是右子树，其逻辑判断与上述相同

总结：如果当前节点的叔父节点是红色，需要进行颜色调整，然后再次进入循环判断是否满足，如果当前节点的叔父节点不是红色，需要判断，当前插入节点是否为左子树内侧插入，如果是，需要比左子树外侧插入多一次旋转操作。最终满足while条件，退出循环，以上就是添加时，需要进行的节点调整操作。

remove()节点

    在了解remove操作之前，我们需要先了解下，红黑树中查找后继节点的方法

    如果当前节点的右子树不为空，那么其后继节点是右子树中最小的节点

    如果当前节点的右子树为空，那么其后继节点是第一个向左走的祖先

    

元素35 的后继节点就是 右子树中最小的元素45

元素30，他的祖先是21 ，但是21是向右走的，也即21的右节点是30，所以要理解第一个向左走的祖先指的是什么意思。

static 
   
     TreeMap.Entry
    
      successor(Entry
     
       t) {    if (t == null)        return null;    else if (t.right != null) {        Entry
      
        p = t.right;        while (p.left != null)            p = p.left;        return p;    } else {        Entry
       
         p = t.parent;        Entry
        
          ch = t; while (p != null && ch == p.right) { ch = p; p = p.parent; } return p; }}
        
       
      
     
    
   

1、如果当前元素的右子树不为null, 获取到右子树，然后遍历右子树的左子树，及左子树的左子树，直到其左子树为null, 返回左子树为null的节点，即为后继节点

2、如果右子树为null , 获取父节点，遍历直到当前元素不是其父节点的右节点，即第一个向左走的祖先，即为后继节点

了解过后继节点之后，我们来看下，关于删除节点操作。

1、删除的节点左右子节点都为空（处理方式：直接移除）

2、删除的节点有一个非空子树（处理方式：）

3、删除的节点两个子节点都不为空（处理方式：用当前元素的后继节点s代替当前元素，然后使用上述1或者2对s进行删除）