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

吐槽一下

不知道大家在面试中有没有被问到过红黑树，是不是会有一部分同行遇到这种情况，直接借尿遁一溜烟颠儿了呢？不是项目中用不到，是真不会…也许还会有一部分会直接洋洋洒洒Map map = new TreeMap();这种情况估计面试官也得懵比。

我去前面探探路！

谈及红黑树，我们需要先了解一下何为平衡二叉树——BST。BST是一种很好的数据结构，一旦给定关键字就能快速检索到目标，快速的插入、删除。

BST特点： 1.左子树上结点的值小于等于根节点 2.右子树上结点的值大于等于根节点 3.左、右子树也分别为二叉排序树

有图有真相

如果干巴巴的文字不好理解，那就放图吧：

这种结构的好处就是查找速度贼快。举个栗子，我想找12，先去右子树13，再去左子树11，再去右子树12。事实上，这种查找方式运用了二分查找的思想，最大次数 = 二叉查找树高度。同理，插入数据也只需要按照这个规则去找到合适的位置插入就好了。 当然了，世间万物皆系于一箭之上…咳咳，错了，是世间万物都有两面性。既然这种结构查找速度快，就肯定有它的弊端。

弊端，WTF？

很明显的缺点，体现在插入新节点的时候。当然了，如果要插入的是随机数据倒还好。一旦我插入的是有序数据，那就直接gg了…

这是什么鬼？成瘸子了，一条腿长、一条腿短，能买到裤子吗（卖裤子的高速你了，你还买裤子吗？）。言归正传，这样就导致一个活生生地树变成了链表，快速查找、插入、删除的优势不再，不平衡导致性能差劲了，于是才有了红黑树。

红黑树面世

红黑树除了拥有二叉查找树的规则之外，还有自己额外的规则（金克斯说:规则就是用来打破的。但是红黑树的规则必须得严格遵守！）。

规则： 1.结点是红色或黑色 2.根节点是黑色 3.每个叶子结点都是黑色空节点NIL 4.每个红色结点的两个子节点都是黑色 5.每个叶子到根节点的所有路径上，不允许出现两个连续的红色结点 6.任意一个结点到每个叶子的所有路径上都包含有相同数量的黑色结点 插入、删除结点，为了保持平衡，要做出适当调整。 比如我要插入14，按照规则只需要放在15的左子树位置上，并且再挂两个黑结点就可以了。15是黑，14为红。 插入21，只需要放在22的左子树位置。但是22是红，再挂红就违背规则了。这时候就得需要采取措施来保持平衡了。

维持平衡

变色

25不是根结点，21、22不能同为红。所以就把22变黑。但是22变黑打破了规则6，所以25就得变红。25、27连续两个红又犯规，27就得变黑。再往上17就得变黑？再继续变？不行，根节点必须黑！只能旋转了。

笔者在学习的时候有疑惑：插入的结点必须是红色？后来知道了，红黑树插入新节点之前，是遵循规则6的。若插入黑色节点就打破了，所以插入新节点是红色的。

左旋转

逆时针旋转红黑树上两个结点，使父节点被自己右孩子代替，爹变左孩子

如果看文字没明白，那就来看看gif：

右旋转

顺时针旋转红黑树上两个结点，父节点被自己左孩子代替，爹变右孩子

右旋gif： 继续分析刚才的变色问题： 经过旋转后： 根节点必须黑色，再变色： 没结束啊，17-8-6-nil黑结点4，其他的是3，还得继续右旋转，13为X，8为Y： 还没完呢，最后再变色： 贴图贴的好累，这里要感谢一下这些图的创作者！ 经历了变色——>坐旋转——>变色——>右旋转——>变色；到这，才算稳定了

应用场景

TreeMap、TreeSet、java8的HashMap、ConcurrentHashMap

源码分析

1.红黑树节点

红黑树是对二叉查找树的升级，在它的基础上加了一个boolean变量表示节点颜色

public class RBNode
   
    <="" span="">extends Comparable>{
       boolean color; //颜色    T key; //关键字(键值)    RBNodeleft;//左子节点    RBNoderight;//右子节点    RBNodeparent;//父节点    public RBNode(T key, boolean color, RBNodeparent,RBNodeleft,RBNoderight) {
           this.key = key;        this.color = color;        this.parent = parent;        this.left = left;        this.right = right;    }    public T getKey() {
           return key;    }    public String toString() {
           return "" + key + (this.color == RED? "R" : "B");    }}
   

2.左旋

/*************对红黑树节点x进行左旋操作 ******************//* * 左旋示意图：对节点x进行左旋 *     p                       p *    /                       / *   x                       y *  / \                     / \ * lx  y      ----->       x  ry *    / \                 / \ *   ly ry               lx ly * 左旋做了三件事： * 1. 将y的左子节点赋给x的右子节点,并将x赋给y左子节点的父节点(y左子节点非空时) * 2. 将x的父节点p(非空时)赋给y的父节点，同时更新p的子节点为y(左或右) * 3. 将y的左子节点设为x，将x的父节点设为y */private void leftRotate(RBNodex) {
       //1. 将y的左子节点赋给x的右子节点，并将x赋给y左子节点的父节点(y左子节点非空时)    RBNodey = x.right;    x.right = y.left;    if(y.left != null)         y.left.parent = x;    //2. 将x的父节点p(非空时)赋给y的父节点，同时更新p的子节点为y(左或右)    y.parent = x.parent;    if(x.parent == null) {
           this.root = y; //如果x的父节点为空，则将y设为父节点    } else {
           if(x == x.parent.left) //如果x是左子节点            x.parent.left = y; //则也将y设为左子节点        else            x.parent.right = y;//否则将y设为右子节点    }    //3. 将y的左子节点设为x，将x的父节点设为y    y.left = x;    x.parent = y;       }

3.右旋

/*************对红黑树节点y进行右旋操作 ******************//* * 左旋示意图：对节点y进行右旋 *        p                   p *       /                   / *      y                   x *     / \                 / \ *    x  ry   ----->      lx  y *   / \                     / \ * lx  rx                   rx ry * 右旋做了三件事： * 1. 将x的右子节点赋给y的左子节点,并将y赋给x右子节点的父节点(x右子节点非空时) * 2. 将y的父节点p(非空时)赋给x的父节点，同时更新p的子节点为x(左或右) * 3. 将x的右子节点设为y，将y的父节点设为x */private void rightRotate(RBNodey) {
       //1. 将y的左子节点赋给x的右子节点，并将x赋给y左子节点的父节点(y左子节点非空时)    RBNodex = y.left;    y.left = x.right;    if(x.right != null)         x.right.parent = y;    //2. 将x的父节点p(非空时)赋给y的父节点，同时更新p的子节点为y(左或右)    x.parent = y.parent;    if(y.parent == null) {
           this.root = x; //如果x的父节点为空，则将y设为父节点    } else {
           if(y == y.parent.right) //如果x是左子节点            y.parent.right = x; //则也将y设为左子节点        else            y.parent.left = x;//否则将y设为右子节点    }    //3. 将y的左子节点设为x，将x的父节点设为y    x.right = y;    y.parent = x;       }

4.插入

先找到待插入的位置，再插入

/*********************** 向红黑树中插入节点 **********************/public void insert(T key) {
       RBNodenode =new RBNode(key, RED,null, null, null);    if(node != null)         insert(node);}//将节点插入到红黑树中，这个过程与二叉搜索树是一样的private void insert(RBNodenode) {
       RBNodecurrent =null; //表示最后node的父节点    RBNodex =this.root; //用来向下搜索用的    //1. 找到插入的位置    while(x != null) {
           current = x;        int cmp = node.key.compareTo(x.key);        if(cmp < 0)             x = x.left;        else            x = x.right;    }    node.parent = current; //找到了位置，将当前current作为node的父节点    //2. 接下来判断node是插在左子节点还是右子节点    if(current != null) {
           int cmp = node.key.compareTo(current.key);        if(cmp < 0)            current.left = node;        else            current.right = node;    } else {
           this.root = node;    }    //3. 分情况讨论，分析何时是变色、左旋、右旋的最佳时机，将它重新修整为一颗红黑树    insertFixUp(node);}

insertFixUp方法

分析下insertFixUp(node)方法：第一次插入原树为空，作为根节点，只需涂黑就好；如果插入的节点的父节点是黑，就啥也不用做；但是碰见以下3中情况就要考虑平衡处理了：

a.插入节点的父节点和叔叔节点都是红色 b.插入节点的父亲是红的，叔叔是黑的，且插入的节点刚好位于父节点的右子树上 c.插入节点的父亲是红的，叔叔是黑的，且插入的节点刚好位于父节点的左子树上

private void insertFixUp(RBNodenode) {
         RBNodeparent, gparent;//定义父节点和祖父节点      //需要修整的条件：父节点存在，且父节点的颜色是红色      while(((parent = parentOf(node)) != null) && isRed(parent)) {
             gparent = parentOf(parent);//获得祖父节点          //若父节点是祖父节点的左子节点，下面else与其相反          if(parent == gparent.left) {
                                 RBNodeuncle = gparent.right;//获得叔叔节点              //case1: 叔叔节点也是红色              if(uncle != null && isRed(uncle)) {
                     setBlack(parent); //把父节点和叔叔节点涂黑                  setBlack(uncle);                  setRed(gparent); //把祖父节点涂红                  node = gparent; //将位置放到祖父节点处                  continue; //继续while，重新判断              }              //case2: 叔叔节点是黑色，且当前节点是右子节点              if(node == parent.right) {
                     leftRotate(parent); //从父节点处左旋                  RBNodetmp = parent;//然后将父节点和自己调换一下，为下面右旋做准备                  parent = node;                  node = tmp;              }              //case3: 叔叔节点是黑色，且当前节点是左子节点              setBlack(parent);              setRed(gparent);              rightRotate(gparent);          } else {
    //若父节点是祖父节点的右子节点,与上面的完全相反，本质一样的              RBNodeuncle = gparent.left;              //case1: 叔叔节点也是红色              if(uncle != null & isRed(uncle)) {
                     setBlack(parent);                  setBlack(uncle);                  setRed(gparent);                  node = gparent;                  continue;              }              //case2: 叔叔节点是黑色的，且当前节点是左子节点              if(node == parent.left) {
                     rightRotate(parent);                  RBNodetmp = parent;                  parent = node;                  node = tmp;              }              //case3: 叔叔节点是黑色的，且当前节点是右子节点              setBlack(parent);              setRed(gparent);              leftRotate(gparent);          }      }      //将根节点设置为黑色      setBlack(this.root);  }

最后说一下

红黑树的关键就在于如何根据那些规则去维持平衡，变色、左旋、右旋这些很重要，在TreeMap源码分析中，也会出现他们的身影…