红黑树

我们知道二叉查找树是一种支持高效查询的数据结构。它的插入，删除，查询效率跟树的高度成正比;当这棵树是平衡二叉树是效率最高为O(logn);当这个退化成链表的时候效率最低为O(n)。所以说如果一棵树随着数据的插入删除变的不再是平衡二叉树（或者接近平衡二叉树），那么它也将别的没那么高效。而红黑树就是这样一棵树，它在动态的更新过程中保证了二叉树始终是平衡的。
下图是两颗省略了叶子节点的红黑树，大家先感受一下

image.png

红黑树具有下面的特点：

1. 根节点必须是黑色的；
2. 每个叶子节点都是黑色的空节点，即叶子节点不保存数据；

3. 红色节点不能相邻；
   4.每个节点到达其可达叶子节点的所有路径都包含相同数目的黑节点；
   红黑树中最关键的技术就是保持树的均衡，当因为插入数据或者删除数据导致树失去平衡的时候就要即使的调整。
   在调整的过程中这里涉及到两个重要操作，左旋（rotate left）,右旋(rotate right)
   如下图所示

   
   image.png
   

   举个例子来说，左旋，右旋就是我自愿降级，提拔我的下属来当领队，我自降一级；我提拔你当我的领队了，你也得够意思，不能让你的下属也当给我的领导吧，所以你的下属必须还是我的下属，即只有你提上去了，其他在我下面的还在我下面，最多平级。

插入操作

红黑树插入的节点都是红色，

• 要插入位置的父节点是黑色，则直接插入即可
• 插入的是根节点，则改成红颜色，插入即可

其他情况（插入节点的父节点是红色）都需要对红黑树进行调整，左右旋转，或者改变颜色。

CASE 1：如果关注节点是 a，它的叔叔节点 d 是红色，则依次执行下列操作：

• 将关注节点 a 的父节点 b、叔叔节点 d 的颜色都设置成黑；
• 将关注节点a的祖父节点c的颜色置成红色；
• 关注节点变成a的祖父节点c;
• 跳至case 2或者case 3;

image.png
这一步我们可以说是，把颜色调对

CASE2:如果关注节点是a，它的叔叔节点d是黑色的，关注节点a是其父节点b的右节点，则依次执行如下操作：

• 关注节点变成节点a的父节点b;
• 围绕新的关注节点b左旋;
• 跳至CASE 3;
  image.png
  将关注节点调成左节点
  CASE 3:如果关注节点是a,它的叔叔节点d是黑色的， 关注节点a是其父节点的左子树，则依次执行下列操作：
• 围绕关注节点a的祖父节点做右旋转；

• 将关注节点a的父节点b和兄弟节点c颜色互换；
  *调整结束。

  
  image.png

删除操作

删除操作比插入操作稍微复杂一些，分两步。
第一步：保证红黑树的特性4， 每个节点到达其可达叶子节点的所有路径都包含相同数目的黑节点；
第二步：保证红黑树的特性3，红色节点永不相邻。
我们先看第一步：

步骤一， 初步调整

也分以下几种情况：
case 1: 删除节点a只有一个子节点b, 则只需要用节点b替换节点a，并将节点b改成黑色。因为给家红黑树的特性4，节点b只可能是红色，节点a只可能是黑色；这种情况最简单不需要二次调整。

image.png

case 2: 要删除的节点a有两个子节点，并且它的右子节点c正好是它的后继节点，即它的右子节点没有左子树。
则直接用c节点代替a节点，并将c节点的颜色置成和a节一样；此时对于a节点的左子树来说黑节点和个数没有任何变化，而对于a节点的右节点来说，如果之前c是黑色，那么现在它将少一个黑色节点，需要在其子节点都标注一下，少了一个黑节点，然后将关注节点改为的，在第二步里面调整。

image.png

case 3: 要删除的节点a有两个子节点，并且它的右子节点c不是它的后继节点，即改节点有左子树。

• 找到后继节点d,将其删除，步骤如case 1;
• 将节点a替换成节点d,颜色改成a节点颜色；
• 如果d以前是黑色，则其右子树因为删了d而少了一个黑色，所以需要将其右子树标记为少一个黑色节点；
• 关注节点改为c；

• 进行步骤二。

  
  image.png

步骤二

分四种情况
case 1: 关注节点a的兄弟节点c是红色，进行如下操作

• 围绕关注节点a的父节点b进行旋转
• 将父节点b好祖父节点c颜色互换
• 继续调整
  image.png
  Case 2: 如果关注节点a的兄弟节点c是黑色，并且c的两个子节点都是黑色。
  则将c节点变成红色，这样c这边相比之前也少了一个黑色节点，两边扯平了；这是他们的父节点相比其兄弟节点少了一个黑色，我们将关注节点改成b，继续调整
  image.png

case 3:关注节点a的兄弟节点c是黑色，并且c的左子树是红色，右子树是黑色

• 围绕c节点右旋，节点c,d交换颜色
• 跳至case4 继续调整
  image.png
  case 4:关注节点a的兄弟节点c是黑色，并且c的右子树是红色
  *围绕节点a的父节点b左旋
  *b,c节点互换颜色，此时因为c成了a的祖父，即a这边多了一个黑色，a这边欠的黑色扯平了；
• 此时c的右子树少了一个黑色，所以将其右子树e设置为黑色

• 调整结束

  
  image.png

总结一下，删除的步骤一即保证数是平衡的，步骤二保证颜色是对的；