BST

二叉查找树（Binary Search Tree，简称BST）是一颗二叉树，它的左子节点的值比父节点的值要小，右节点的值要比父节点的值大。它的高度决定了它的查找效率。

在理想情况下，二叉查找树增删改查的时间复杂度为o(logN)（其中N为节点数），最坏的情况下为o(N)。当它的高度为log(N) + 1时，我们就说二叉查找树是平衡的。

BST的查找操作

// T key = a search key
// Node root = point to the root of a BST

while (true) {
  if (root == null) {
    break;
  }
  if (root.value.equals(key)) {
    return root;
  } else if (key.compareTo(root.value) < 0) {
    root = root.left;
  } else {
    root = root.right;
  }
}
return null;

从程序中可以看出，当BST查找的时候，先与当前节点进行比较：

• 如果相等的话就返回当前节点
• 如果小于当前节点则继续查找当前节点的左节点
• 如果大于当前节点则继续查找当前节点的右节点

直到当前节点指针为空或者查找到对应的节点，程序查找结束

BST的插入操作

// Node node = create a new node with specify value
// Node root = point the root node of a BST
// Node parent = null

// find the parent node to append the new node
while (true) {
  if (root == null) {
    break;
  }
  parent = root;
  if (node.value.compareTo(root.value) <= 0) {
    root = root.left;
  } else {
    root = root.right;
  }
}

if (parent != null) {
  if (node.value.compareTo(parent.value) <= 0) {
    parent.left = node;
  } else {
    parent.right = node;
  }
}

插入操作先通过循环查找到待插入的节点的父节点，和查找父节点的逻辑一样，都是比大小，小的往左，大的往右。找到父节点后，对比父节点，小的就插入到父节点的左节点，大就插入到父节点的右节点上

BST的删除操作

删除操作的步骤如下：

• 查找到要删除的节点
• 如果待删除的节点是叶子节点，则直接删除
• 如果待删除的节点不是叶子节点，则先找到待删除的节点的中序遍历的后继节点，用该后继节点的值替换待删除的节点的值，然后删除后续节点

BST存在的问题

BST存在的主要问题是，在插入的时候会导致树倾斜，不同的插入顺序会导致树的高度不一样，而树的高度直接地影响了树的查找效率。理想的高度是logN，最坏的情况是所有的节点都在一条斜线上，这样的树的高度是N

RBTree

基于BST存在的问题，一种新的树——平衡二叉查找树(Balanced BST)产生了。平衡树在插入和删除的时候，会通过旋转操作将高度保持在logN。其中两款具有代表性的平衡树分别为AVL树和红黑树。AVL树由于实现比较复杂，而且插入和删除性能差，在实际环境下的应用不如红黑树。

红黑树（Red-Black Tree，以下简称RBTree）的实际应用非常广泛，比如Linux内核中的完全公平调度器、高精度计时器、ext3文件系统等等，各种语言的函数库如Java的TreeMap和TreeSet，C++ STL的map、multimap、multiset等。

RBTree也是函数式语言中最常用的持久数据结构之一，在计算几何中也有重要作用。值得一提的是，Java 8中HashMap的实现也因为用RBTree取代链表，性能有所提升。

AVL树

• 简介：AVL树是带有平衡条件的二叉查找树，一般使用平衡因子差值判断是否平衡，平衡因子为左右子树高度之差，绝对值不能大于1，失衡时通过旋转来实现平衡，与红黑树相比，AVL树是严格的平衡二叉树，旋转是十分耗时的，因此AVL树适合用于插入删除次数较少，但查找较多的情况（中序遍历为有序序列，时间复杂度为o(n*logn)）

• 局限性：由于维护了这种高度平衡所付出的代价比从中获得的效益收益还大，故而实际的应用不多，更多的地方是用追求局部而不是非常严格整体平衡的红黑树。当然，如果应用场景中对插入删除不频繁，只是对查找要求较高，那么AVL还是较优于红黑树

• 应用：Windows NT内核中广泛存在

2-3树

2-3树是一种绝对平衡树。它的节点元素个数可以为1个或者2个。如图，下面就是一个2-3树：

2-3树中的2代表一个节点有两个孩子，3代表一个节点有三个孩子

2-3树的操作

插入

这里结合一个例子来查看2-3树是如何实现绝对平衡的。例如，现在我们要依次增加1、2、3、4、5、6、7这7个元素，如图

如果所示，下面一个步骤一个步骤分析：

• 插入1，判断无根节点，直接将1封装为节点并设置为根节点
• 插入2，这是因为1节点没有孩子节点并且只有1节点，所有直接将2加入到节点1中
• 插入3，和2节点一样，将3节点放入到根节点中，这是根节点有3个元素了，就需要变化为步骤4的样子。可以理解为将1、2、3的中间元素提取到根节点，也就是将2提出来，1作为左孩子，3作为右孩子
• 插入4，4比2大，增加到节点3
• 插入5，5比2大，增加到节点3、4中，这是节点3、4变为节点3、4、5，节点3、4、5按照第三步中将中间元素提取为双亲节点，而4提取出来的4回去找双亲节点2，2节点只有一个元素，所以4加入到2节点中
• 插入6，6大于根节点的2和4，进入最右边，5没有孩子只有一个元素，加入6到5节点
• 插入7，这时5、6、7将6提取出放入6的双亲节点，6的双亲节点（根节点）变为2、4、6。2、4、6提取出4变成最后的样子

总的来说，插入方法和二分搜索相似。但是每个节点可以有1-2个元素，当节点元素个数为3时，就会分成3个节点并向上合并，直到合并完成。

查找

2-3树的查找和二分搜索树类似，不过因为一个节点可能有2个元素，需要对这两个元素进行比较，分别前往这两个节点的左、中、右孩子继续比较

删除

2-3树的删除稍微复杂一点儿，删除可分为两大情况，就是删除叶子节点和非叶子节点

这里只说理论情况，不结合代码实现，实际上代码实现会变得复杂也只是因为考虑的东西更多，代码实现会变得复杂

删除叶子节点（不太懂）

• 当前节点是3节点，直接删除
• 当前节点是2节点：删除并判断
  • 双亲是2节点，判断兄弟节点
    • 兄弟节点是3节点，将兄弟节点移到双亲节点，再将双亲节点的另一个元素移到当前节点
    • 兄弟节点是2节点，先通过移动兄弟节点的中序遍历直接后驱到兄弟节点，以使兄弟节点变为3节点，再进行删除
  • 双亲节点是3节点，拆分双亲节点使其变成2节点，再将双亲节点中最接近的一个拆分key与中孩子合并，将合并后的节点作为当前节点
• 若2-3树是棵满二叉树，删除节点，将2-3树层树减少，并将兄弟节点合并到双亲节点中，同时将双亲节点的所有兄弟节点合并到双亲节点的双亲节点中，如果变为4节点，就做分解操作

删除非叶子节点

使用中序遍历下的直接后继节点key来覆盖当前节点key，再删除用来覆盖的后继节点key

RBTree定义

在开始红黑树之前，我们要知道红黑树并非只有2-3树这一种实现方式，虽然2-3树实现红黑树比较方便。RBTree的定义如下：

• 任何一个节点都有颜色，黑色或者红色
• 根节点是黑色的
• 父子节点之间不能出现两个连续的红色节点
• 任何一个节点向下遍历到其子孙节点的叶子节点，所经过的黑色节点个数必须相等
• 空节点被认为是黑色的，即每一个叶子节点是黑色

2-3树与红黑树的关系

如图，我们可以看到，可以将2-3树中的3节点中的左元素弄成一个新节点，这个节点就是红黑树中的红节点，并且将红节点统一进行左偏向，得出右图的红黑树，这样的红黑树也叫左倾红黑树。

数据结构表示如下：

private class Node {
  // 排序也是通过key进行排序
  public K key;
  public V value;
  public Node left, right;
  // 红为true，黑为false，默认节点为红
  public boolean color;
}

RBTree在理论上还是一颗BST树，但是它在对BST的插入和删除操作时会维持树的平衡，即保证树的高度在[logN, logN + 1]（理论上，极端情况下可以出现RBTree的高度达到2*logN，但实际上很难遇到）。这样RBTree的查找时间复杂度始终保持在o(logN)从而接近于理想的BST。RBTree的删除和插入操作的时间复杂度也是o(logN)。RBTree的查找操作就是BST的查找操作

RBTree的旋转操作

旋转操作（Rotate）的目的是使节点的颜色符合定义，让RBTree的高度达到平衡。

Rotate分为left-rotate（左旋）和right-notate（右旋），区分左旋和右旋的方法是：待旋转的节点从左边上升到父节点就是右旋，待旋转节点从右边上升到父节点就是左旋。

左旋转

//   node                     x
//  /   \     左旋转         /  \
// T1   x   --------->   node   T3
//     / \              /   \
//    T2 T3            T1   T2
private Node leftRotate(Node node) {
  Node x = node.right;
  // 左旋转
  node.right = x.left;
  x.left = node;
  x.color = node.color;
  node.color = RED;
  return x;
}

右旋转

//     node                   x
//    /   \     右旋转       /  \
//   x    T2   ------->   y   node
//  / \                       /  \
// y  T1                     T1  T2
private Node rightRotate(Node node) {
  Node x = node.left;
  // 右旋转
  node.left = x.right;
  x.right = node;
  x.color = node.color;
  node.color = RED;
  return x;
}

颜色翻转

// 颜色翻转
private void flipColors(Node node) {
  node.color = RED;
  node.left.color = BLACK;
  node.right.color = BLACK;
}

左旋和右旋总结

树的旋转，能保持不变的只有树的二叉查找性质，而原树的红黑性质则不能保持，在红黑树的数据插入和删除后，可利用旋转和颜色翻转来恢复树的红黑性质

RBTree的查找操作

RBTree的查找操作和BST的查找操作是一样的。请参考BST的查找操作代码。

BTree的插入操作介绍一

向一颗含有n个节点的红黑树插入一个新的节点的操作可以在o(logn)时间完成

在插入操作分析之前，再复习下红黑树的性质：

1、每个节点要么是红色，要么是黑色
2、根节点是黑色
3、所有叶子节点是黑色，即空节点（NIL）
4、如果一个节点是红色的，则它的两个子节点必须是黑色的，也就是父子节点不能都为红色
5、从一个节点到其所有叶子节点的所有路径上包含相同数目的黑节点

规则预定

1. 在红黑树中插入节点，节点的初始颜色都是红色，因为这样可以在插入过程中尽量避免对树的结构进行调整（参考第5点性质）
2. 初始插入按照二叉查找树的性质插入，即找到合适大小的节点，在其左边或者右边插入子节点

我们在插入一个节点后，会使树的那些性质改变呢？

1. 由于是以二叉查找树的性质插入，因此节点的查找性质不会被破坏
2. 如果插入空树中，成为根节点，则性质2会被破坏，需要重新涂色
3. 如果插入节点的父节点是红色，则性质4会被破坏，需要以插入的当前节点为中心进行旋转或重新涂色来恢复红黑树的性质。执行旋转或重新涂色后有可能红黑树仍然不满足性质，则需要将当前节点变换回溯到其父节点或祖父节点，以父节点或祖父节点为中心继续旋转或重新涂色，如此循环到根节点直到满足红黑树的性质。

恢复红黑树性质的策略

根据上面说到的性质改变，对应的恢复策略其实就简单很多

1. 把出现违背红黑树性质的结点向上移（通过旋转操作或变换当前节点到父节点或祖父节点后再旋转达到向上移动的目的），如果能移到根结点，那么很容易就能通过直接修改根结点的颜色，或旋转根节点来恢复红黑树的性质

2. 旋转或涂色处理可分5种情况进行处理

   情况1：空树中插入根节点
   情况2：插入节点的父节点是黑色
   情况3：当前节点的父节点是红色，且叔叔节点（祖父节点的另一个子节点）也是红色
   情况4：当前节点的父节点是红色，叔叔节点是黑色，当前节点是右子节点
   情况5：当前节点的父节点是红色，叔叔节点是黑色，当前节点是左子节点

情况1：空树中插入根节点
违反：性质2
恢复策略：初始插入的节点均为红色，因此简单将红色重涂为黑色即可。

情况2：插入节点的父节点是黑色
违反：插入的红色节点，未违反任何性质。
恢复策略：什么也不做，无需调整。

情况3：当前节点的父节点是红色，且叔叔节点也是红色
违反：性质4
此时祖父节点一定存在，否则插入前就已不是红黑树。
与此同时，又分为父节点是祖父节点的左子还是右子，由于对称性，我们只要解开一个方向就可以了。在此，我们只考虑父节点为祖父左子的情况。
同时，还可以分为当前结点是其父结点的左子还是右子，但是处理方式是一样的。我们将此归为同一类。
恢复策略：将当前节点的父节点和叔叔节点涂黑，祖父结点涂红，把当前结点指向祖父节点，以祖父节点为中心重新开始新一轮的旋转或涂色。
以插入节点4为例，按照恢复策略，做如下图的涂色：

以插入节点4为当前节点，判断父节点和叔叔节点是否都为红色，如果为红色，则将祖父节点7的颜色改为红色，父节点5和叔叔节点8的颜色改为黑色。同时当前节点移动到祖父节点7。此时，当前节点7的父节点也为红色，出现父子节点都为红色的情况，且叔叔节点为黑色，因此适用于情况4：当前节点的父节点是红色，叔叔节点是黑色，当前节点是右子节点，那么按照情况4的恢复策略，进行新一轮的旋转或涂色，如下看情况4如何进行调整。

情况4：当前节点的父节点是红色，叔叔节点是黑色，当前节点是右子节点
违反：性质4
恢复策略：以当前节点的父节点作为新的当前节点，以新的当前节点为支撑，进行左旋操作。旋转操作后再按新的情况进行旋转或涂色。

这里作的操作为：当前节点由原来的7变换为其父节点2，以新的当前节点2，作左旋操作，如上图。操作完成后，发现父子节点仍都是红色，继续进行旋转或涂色。这里适用于情况5：当前节点的父节点是红色，叔叔节点是黑色，当前节点是左子节点来进行再次调整，请看下面的情况5如何进行调整。

情况5：当前节点的父节点是红色，叔叔节点是黑色，当前节点是左子节点
违反：性质4
恢复策略：父节点改变为黑色，祖父节点改变为红色，然后再以祖父节点为新的当前节点，做右旋操作。

此时，树已经满足红黑树的性质，如果仍不满足，则仍按照情况1——情况5的方式进行旋转和重新涂色。

RBTree的插入操作介绍二

RBTree的插入与BST的插入方式是一致的，只不过是在插入过后，可能会导致树的不平衡，这是就需要对树进行旋转操作的颜色修复（这里简称插入修复），使得它符合RBTree的定义。

新插入的节点是红色的，插入修复操作如果遇到父节点的颜色为黑则修复结束。也就是说，只有在父节点为红色节点的时候是需要插入修复操作的。

插入修复操作分为以下三种情况，而且新插入的节点的父节点都是红色的：

• 叔叔节点也是红色
• 叔叔节点为空，且祖父节点、父节点和新节点处于一条斜线上
• 叔叔节点为空，且祖父节点、父节点和新节点不处于一条斜线上

插入操作——case1

case1的操作是将父节点和叔叔节点与祖父节点的颜色互换，这样就符合了RBTree的定义。即维持了高度的平衡，修复后颜色也符合RBTree的定义的第三条和第四条。下图中，操作完成后A节点变成了新节点，如果A节点的父节点不是黑色的话，则继续做修复操作

插入操作——case2

case2的操作是将B节点进行右旋操作，并且和父节点A互换颜色。通过该修复操作RBTree的高度和颜色都符合红黑树的定义。如果B和C节点都是右节点的话，只要将操作变成左旋就可以

插入操作——case3

case3的操作是将C节点进行左旋，这样就从case3转换成case2，然后针对case 2进行操作处理就行了。case 2操作做了一个右旋操作和颜色互换来达到目的。如果树的结构是下图的镜像结构，则只需要将对应的左旋变成右旋，右旋变成左旋即可。

插入操作的总结

插入后的修复操作是一个从root节点回溯的操作，一旦牵扯的节点都符合了红黑树的定义，修复操作结束。之所以会向上回溯是由于case1操作会将父节点、叔叔节点和祖父节点进行颜色互换，有可能会导致祖父节点不平衡（红黑树定义3）。这个时候需要对祖父节点为起点进行调节（向上回溯）

祖父节点调节后如果还是遇到它的祖父节点颜色问题，操作就会继续向上回溯，直到root节点为止，根据定义root节点永远是黑色的。在向上的追溯的过程中，针对插入的情况3中情况进行调节。直到符合红黑树定义为止。知道牵扯的节点都符合了红黑树的定义，修复操作结束。

如果上面的3中情况如果对应的操作是在右子树上，做对应的镜像操作就是了。

RBTree的删除操作

删除操作首先需要做的也是BST的删除操作，删除操作会删除对应的节点，如果是叶子节点就直接删除，如果是非叶子节点，会用对应的中序遍历的后继节点来顶替要删除节点的位置。删除后就需要做删除修复操作，使得树符合红黑树的定义，符合定义的红黑树高度是平衡的。

删除修复操作在遇到被删除的节点是红色节点或者到达root节点后，修复操作完毕。

删除修复操作是针对删除黑色节点才有的，当黑色节点被删除后会让整个树不符合RBTree的定义的第四条。需要做的处理是从兄弟节点上借调黑色的节点过来，如果兄弟节点没有黑节点可以借调的话，就只能往上追溯，将每一级的黑节点数减去一个，使得整棵树符合红黑树的定义。

删除操作的总体思想是从兄弟节点借调黑色节点使树保持局部平衡，如果局部的平衡达到了，就看整体的树是否是平衡的，如果不平衡就接着向上追溯调整。

删除修复操作分为四种情况（删除黑节点后）：

• 待删除节点的兄弟节点是红色的节点
• 待删除的节点的兄弟节点是黑色的节点，且兄弟节点的子节点都是黑色的
• 待调整的节点的兄弟节点是黑色的节点，且兄弟节点的左子节点是红色的，右节点是黑色的（兄弟节点在右边），如果兄弟节点在左边的话，就是兄弟节点的右子节点是红色的，左节点是黑色的
• 待调整节点的兄弟节点是黑色的节点，且右子节点是红色的（兄弟节点在右边），如果兄弟节点在左边，则就是对应的就是左节点是红色的

删除操作——case1

由于兄弟节点是红色节点的时候，无法借调黑色节点，所以需要将兄弟节点提升到父节点，由于兄弟节点是红色的，根据RBTree的定义，兄弟节点的子节点是黑色的，就可以从它的子节点借调了。

case1这样转换之后就会变成后面的case2、case3，或者case4进行处理。上升操作需要对C做一个左旋操作，如果是镜像结构的树只需要做对应的右旋操作即可。

之所以要做case1操作是因为兄弟节点是红色的，无法借到一个黑节点来填补删除的黑节点。

删除操作——case2

case2的删除操作是由于兄弟节点可以消除一个黑色节点，因为兄弟节点和兄弟节点的子节点都是黑色的，所以可以将兄弟节点变红，这样就可以保证树的局部的颜色符合定义了。这个时候需要将父节点A变成新的节点，继续向上调整，直到整棵树的颜色符合RBTree的定义为止。

case2这种情况下之所以要将兄弟节点变红，是因为如果把兄弟节点借调过来，会导致兄弟的结构不符合RBTree的定义，这样的情况下只能是将兄弟节点也变成红色来达到颜色的平衡。当将兄弟节点也变红之后，达到局部的平衡了，但是对于祖父节点来说不符合定义4的。这样就需要回溯到父节点，接着进行修复操作。

删除操作——case3

case3的删除操作是一个中间状态，它的目的是将左边的红色节点借调过来，这样就可以转换成case4状态，在case4状态下可以将D、E节点借调过来，通过将两个节点变成黑色来保证红黑树的平衡。

之所以说case3是一个中间状态，是因为根据红黑树的定义来说，下图并不是平衡的，它是通过case 2操作完后向上回溯出现的状态。之所以会出现C。

删除操作——case4

case4操作是真正的节点借调操作，通过将兄弟节点以及兄弟节点的右节点借调过来，并将兄弟节点的右子节点变成红色来达到借调两个黑色节点的目的，这样的话，整棵树还是符合RBTree的定义。

case4这种情况的发生只有在待删除的节点的兄弟节点为黑，且子节点不全部为黑，才有可能借调到两个节点来做黑节点使用，从而保持整棵树都符合红黑树的定义

删除操作的总结

红黑树的删除操作是最复杂的操作，复制的地方在于当删除了黑色节点的时候，如何从兄弟节点去借调节点，以保证树的颜色符合定义。由于红色的兄弟节点是没法借调出黑节点的，这样只能通过选择操作让他上升到父节点，而由于它是红节点，所以它的子节点就是黑的，可以借调。

对于兄弟节点是黑色节点的可以分为三种情况来处理，当所有的兄弟节点的子节点都是黑色节点时，可以直接将兄弟节点变红，这样局部的红黑树颜色是符合定义的。但是整棵树不一定是符合红黑树定义的，需要往上追溯继续调整。

对于兄弟节点的子节点为左红右黑（全部为红，右红左黑）两种情况，可以先将前面的情况通过选择转换为后一种情况，在后一种情况下，因为兄弟节点为黑，兄弟节点的右节点为红，可以借调出两个节点出来做黑节点，这样就可以保证删除了黑节点，整棵树还是符合红黑树定义的，因为黑色节点的个数没有改变。

红黑树的删除操作是遇到删除的节点为红色，或者追溯调整到了root节点，这时删除的修复操作完毕。

三、RBTree的Java实现

public class RBTreeNode<T extends Comparable<T>> {
  // node value
  private T value;
  // left child pointer 
  private RBTreeNode<T> left;
  // right child pointer
  private RBTreeNode<T> right;
  // parent pointer
  private RBTreeNode<T> parent;
  // color is red or not red
  private boolean red;
  
  public RBTreeNode() {
    return value;
  }
  
  public RBTreeNode(T value) {
    this.value = value;
  }
  
  public RBTreeNode(T value, boolean isRed) {
    this.value = value;
    this.red = isRed;
  }
  
  public T getValue() {
    return value;
  }
  
  public void setValue(T value) {
    this.value = value;
  }
  
  public RBTreeNode<T> getLeft() {
    return left;
  }
  
  public void setLeft(RBTreeNode<T> left) {
    this.left = left;
  }
  
	public RBTreeNode<T> getRight() {
    return right;
  }
  
  public void setRight(RBTreeNode<T> right) {
    this.right = right;
  }
  
  public boolean isRed() {
    return red;
  }
  
  public boolean isBlack() {
    return !red;
  }
  
  public boolean isLeaf() {
    return left == null && right == null;
  }
  
  public void setRed(boolean red) {
    this.red = red;
  }
  
  public void makeRed() {
    red = true;
  }
  
  public void makeBlack() {
    red = false;
  }
  
  @Override
  public String toString() {
    return value.toString();
  }
}

public class RBTree<T extends Comparable<T>> {
  private final RBTreeNode<T> root;
  
  // node number
  private java.util.concurrent.atomic.AtomicLong size = 
    new java.util.concurrent.atomic.AtomicLong(0);
  
  // in overwrite mode, all node's value cannot has same value
  // in non-overwrite mode, node can have same value, suggest don't use non-overwrite mode
  private volatile boolean overrideMode = true;
  
  public RBTree() {
    this.root = new RBTreeNode<T>();
  }
  
  
}

ConcurrentHashMap二叉树的构造过程

对于ConcurrentHashMap，链表的长度超过8时，会调用treeifyBin()方法将链表结构转换为红黑树。

下面是ConcurrentHashMap中节点类型和继承关系

**注意点：**Node是链表中的元素，而TreeBin和TreeNode也继承自Node节点，也自然继承了next属性，同样拥有了链表的性质，其实真正在存储时，红黑树仍然是以链表形式存储的，只是逻辑上TreeBin和TreeNode多了支持红黑树的root、first、parent、left、right和red属性，在附加的属性上进行了逻辑上的引用和关联，也就造就了一棵树

所以理解了上面的红黑树其实也是一个链表，再来看源码就不难理解：

/**
 * Replaces all linked nodes in bin at given index unless table is
 * too small, in which case resizes instead.
 * @param tab table表
 * @param index 转换为红黑树的链表在table中的索引下标
*/
private final void treeifyBin(Node<K,V>[] tab, int index) {
  Node<K,V> b; int n, sc;
  if (tab != null) {
    // 一开始并非直接转换为红黑树，而是通过扩容table到2倍的方式
    // 只有table的长度大于64之后，才会将超过8个元素的链表转换为红黑树
    if ((n = tab.length) < MIN_TREEIFY_CAPACITY)
      tryPresize(n << 1);
    // b.hash >= 0 即为普通的Node链表节点
    else if ((b = tabAt(tab, index)) != null && b.hash >= 0) {
      // 锁住链表头
      synchronized (b) {
        if (tabAt(tab, index) == b) {
          TreeNode<K,V> hd = null, tl = null;
          // 将原Node链表转换成以TreeBin节点为元素的链表
          for (Node<K,V> e = b; e != null; e = e.next) {
            TreeNode<K,V> p =
              new TreeNode<K,V>(e.hash, e.key, e.val,
                                null, null);
            if ((p.prev = tl) == null)
              hd = p;
            else
              tl.next = p;
            tl = p;
          }
          // TreeBin的构造方法构造树，根据TreeBin链表构造
          setTabAt(tab, index, new TreeBin<K,V>(hd));
        }
      }
    }
  }
}

从源码可以看出，一开始并非直接转换为红黑树，而是通过扩容table到2倍的方式，只有table的长度大于64之后，才会将超过8个元素的链表转红黑树。红黑树的构造过程是在TreeBin的构造方法中完成的。

红黑树的构造过程

假设待构造的红黑树TreeNode链表如下，节点中的数值代表元素的hash值：

源码如下

/**
 * Creates bin with initial set of nodes headed by b.
*/
TreeBin(TreeNode<K,V> b) {
  super(TREEBIN, null, null, null);
  this.first = b;
  TreeNode<K,V> r = null;
  // 遍历TreeNode链表进行构造
  for (TreeNode<K,V> x = b, next; x != null; x = next) {
    next = (TreeNode<K,V>)x.next;
    x.left = x.right = null;
    if (r == null) {
      x.parent = null;
      x.red = false;
      r = x;
    }
    else {
      K k = x.key;
      int h = x.hash;
      Class<?> kc = null;
      for (TreeNode<K,V> p = r;;) {
        // 执行插入，dir为比对节点hash的大小的标识，决定插入时是左还是右
        int dir, ph;
        K pk = p.key;
        if ((ph = p.hash) > h)
          dir = -1;
        else if (ph < h)
          dir = 1;
        else if ((kc == null &&
                  (kc = comparableClassFor(k)) == null) ||
                 (dir = compareComparables(kc, k, pk)) == 0)
          dir = tieBreakOrder(k, pk);
        TreeNode<K,V> xp = p;
        if ((p = (dir <= 0) ? p.left : p.right) == null) {
          x.parent = xp;
          if (dir <= 0)
            xp.left = x;
          else
            xp.right = x;
          // 插入后，执行恢复操作，重新涂色或者旋转
          r = balanceInsertion(r, x);
          break;
        }
      }
    }
  }
  this.root = r;
  assert checkInvariants(root);
}

源码中，balanceInsertion方法为恢复操作。所以根据上述源码和红黑树的恢复策略，依次遍历链表节点插入到红黑树中，我们构造如下：

• 节点80

第一个节点80，插入到空树中，设置为根节点，并为黑色：

• 节点60

节点60按二叉树插入后，未违反任何红黑树的性质，不做任何动作

• 节点50

节点50插入后，违反了性质4，按照情况5：当前节点的父节点是红色，叔叔节点是黑色，当前节点是左子节点进行恢复。

按照情况5的恢复策略调整如下：
把当前节点的父节点变为黑色，祖父节点变为红色，将祖父节点更新为当前节点，以新的当前节点为支点进行右旋操作。

• 节点70

节点70插入后，违反红黑树性质5，按照情况3：当前节点的父节点是红色，且叔叔节点也是红色进行调整。

调整如下，需要经过两次涂色调整，将当前节点70的父节点和叔叔节点改为黑色，祖父节点改为红色。由于祖父节点为根节点，根节点只能为黑色，因此在此将根节点改为黑色，调整完成。

• 节点20

节点20插入后未违反任何特性，无需调整。

• 节点65

节点65插入后违反性质4，按照情况5：当前节点的父节点是红色，叔叔节点是黑色，当前节点是左子节点进行恢复。

恢复调整如下，需要经过两个步骤，当前节点65的父节点改为黑色，祖父节点改为红色，然后将祖父节点设为最新的当前节点。涂色后的新树违反了性质5，因此还要以最新的当前节点为支点进行右旋操作：

• 节点40

节点40插入后，违反红黑树性质4:父子节点不能都为红色，插入后的红黑树见下图：

根据前文的调整策略，此处当前节点为红色，叔叔节点NIL为黑色，且当前节点为右子节点，**按情况4进行调整恢复：
步骤一：以当前节点40的父节点20为新的当前节点（见下图1）；
步骤二：以图1中新的当前节点20为支点，左旋（见下图2）；

旋转完成后，发现当前节点20和父节点40都为红色，仍然违反了红黑树的性质4，需要继续回溯当前节点再次旋转或涂色。此时，当前节点是左子节点，**按情况5进行调整恢复：
步骤一：将当前节点的父节点40重涂为黑色，祖父节点50重涂为红色（见下图3）；得到的红黑树发现不满足红黑树的性质5：从一个节点到其所有叶子节点的所有路径上包含相同数目的黑节点，继续执行步骤二的调整。
步骤二：以当前节点20的祖父节点50为新的当前节点，进行右旋（见下图5）；

到此，成功将节点40插入红黑树，满足所有红黑树的性质.

• 节点10

节点10插入后违反性质4，按照情况3：当前节点的父节点是红色，且叔叔节点（祖父节点的另一个子节点）也是红色进行恢复。

恢复调整如下，当前节点10的父节点和叔叔节点改为黑色，祖父节点40重涂为红色，调整就完成了：

至此，红黑树的构造完成。