红黑树-数字星空

概述

红黑树（Red-Black Tree，R-BTree）是一种自平衡的二叉查找树，在红黑树的每个节点都多出一个存储位表示节点的颜色，颜色只能是红（Red）或者黑（Black）。

红黑树的特性如下：

每个节点或者是黑色的，或者是红色的
根节点是黑色的
每个叶子节点都是黑色的，这里的叶子节点指的是最底层的空节点，即图中值为 null 的节点，讨论时一般将其省略，值为 null 的根节点在红黑树中不看作叶子节点
如果一个节点是红色的，则它的子节点必须是黑色的
从任一个节点到叶子节点的所有路径下都包含相同数量的黑色节点

有了上面的几个性质作为限制，即可避免二叉查找树退化成单链表的情况。而有了性质 4 和性质 5，可保证任意节点到其每个叶子节点路径最长不会超过最短路径的 2 倍，因为当某条路径最短时，这条路径必然都由黑色节点构成。当某条路径长度最长时，这条路径必然由红色和黑色节点相间构成（性质 4）。而性质 5 又限定了任一节点到其每个叶子节点的所有路径必须包含相同数量的黑色节点。因此，最长路径长度等于最短路径长度的 2 倍

红黑树的旋转

红黑树的左旋：以 a 节点为支点左旋，指将 a 节点的右子节点（b）设为 a 节点的父节点，则 a 节点变为 b 节点的左节点，b 节点原本的左子节点 d 则按照平衡二叉树的规则重新分配位置

红黑树的右旋也是同理

红黑树的添加

红黑树的添加分为三步：

将红黑树看作一颗二叉查找树，并以二叉查找树的规则插入新节点，此时新节点一定位于树的末端，即是叶子节点（不考虑值为 null 的黑色节点）
将插入的节点涂成红色（如果涂成是黑色，那么这个节点所在路径比其他路径多出一个黑色节点，调整起来比较麻烦；如果涂成红色，此时所有路径上的黑色节点数量不变，仅可能会出现两个连续的红色节点的情况，通过变色和旋转进行调整即可）
通过左旋、右旋或着色操作，使之重新成为一颗红黑树

根据被插入的节点的父节点的情况，可以将具体的插入分为三种情况来处理

第一种：如果被插入的节点是根节点，则直接把此节点涂成黑色

第二种：如果被插入的节点的父节点是黑色的，没有破坏二叉树的性质，不需要调整

第三种：如果被插入的节点的父节点是红色的，则被插入的节点一定存在非空祖父节点（黑色），即被插入的节点也一定存在叔叔节点，即使叔叔节点（当前节点的祖父节点的另一个子节点）为空，我们也视之为存在，空节点本身就是黑色节点。然后根据叔叔节点的颜色，进一步分为三种情况来处理：

叔叔节点是红色的，则将父节点和叔叔节点设为黑色，祖父节点设为红色。需要注意的是祖父节点设为红色后，可能会和它的父节点形成连续的红色节点，此时需要将当前节点设为祖父节点，递归向上调整
叔叔节点是黑色的，当前节点是父节点的右子节点，则将父节点设为当前节点，以当前节点为支点左旋，再根据其他情况调整
叔叔节点是黑色的，当前节点是父节点的左子节点，则将父节点设为黑色，将祖父节点设为红色，以祖父节点为支点右旋

红黑树的删除

红黑树的删除分为两步：

将红黑树看作一颗二叉查找树，根据二叉查找树的删除规则删除节点
1. 如果被删除的节点没有子节点，那么直接将该节点删除
2. 如果被删除的节点只有一个子节点，那么直接删除该节点，并用该节点的唯一子节点替换该节点
3. 如果被删除的节点有两个子节点，那么先找出该节点的替换节点，然后把替换节点的数据覆盖该节点的数据，之后删除替换节点
因为红黑树在删除节点后可能会违背红黑树的特性，所以需要通过旋转和重新着色来修正，使之重新成为一棵红黑树
1. 如果当前节点的子节点是“红+黑”节点，则直接把当前节点设为黑色
2. 如果当前节点的子节点是“黑+黑”节点，且当前节点是根节点，则什么都不做
3. 如果当前节点的子节点是“黑+黑”节点，且当前节点不是根节点，则又可以分如下情况处理
  - 当前节点的兄弟节点是红色，则将当前节点的兄弟节点设置为黑色，将父节点设置为红色，对父节点进行左旋，重新设置当前节点的兄弟节点
  - 如果当前节点的子节点是“黑+黑”节点，且当前节点的兄弟节点是黑色，兄弟节点的两个子节点也都是黑色，则将当前节点的兄弟节点设置为红色，设置当前节点的父节点为新节点
  - 如果当前节点的子节点是“黑+黑”节点，且当前节点的兄弟节点是黑色，兄弟节点的左子节点是红色且右子节点是黑色，则将当前节点的左子节点设置为黑色，将兄弟节点设置为红色，对兄弟节点进行右旋，重新设置当前节点的兄弟节点
  - 如果当前节点的子节点是“黑+黑”节点，且当前节点的兄弟节点是黑色，兄弟节点的右子节点是红色且左子节点是任意颜色，则将当前节点的父节点的颜色赋值给兄弟节点，将父节点设置为黑色，将兄弟节点的右子节点设置为黑色，对父节点进行左旋，设置当前节点为根节点