#数据结构 #算法 #C
❗红黑树属于较难的数据结构，知识相对深奥。需要反复阅读几编。
红黑树（英语：Red–black tree）是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型用途是实现关联数组（例如C++中的map）。它在1972年由鲁道夫·贝尔发明，被称为“对称二叉B树”。
| BST | AVL Tree | Red–black tree | |
|---|---|---|---|
| 发现时间 | 1960 | 1962 | 1972 |
| 查找的时间复杂度 | |||
| 插入的时间复杂度 | |||
| 删除的时间复杂度 |
在对平衡二叉树进行操作的时候，例如插入和删除，会破坏原本树的平衡性，此时需要重新计算平衡因子，找到最小不平衡树，重新调整，消耗时间开销较大。而红黑树（RBT）在插入和删除操作的时候，一般不会破坏“红黑”特征，无需频繁调整树的形态，即使需要调整，也是在常数级时间内可以完成。
对于平衡二叉树来说，主要是以查找为主，较少实现插入和删除，而红黑树适应频繁插入删除，因此红黑树的应用比平衡二叉树的应用更加广泛。
首先红黑树是一种二叉排序树（BST），符合：左子树的结点值 ≤ 根结点值 ≤ 右子树的结点值，这样的二叉排序树的基本特点。 相对比普通的二叉树，红黑树还需要满足以下五个基本性质。
- 任意一结点是红色或黑色。
- 根结点是黑色。
- 所有叶子结点都是黑色（叶子是NIL结点）。
- 每个红色结点必须有两个黑色的子结点。
- 或者说，不存在两个相邻的红色结点，相邻指两个结点是父子关系。
- 或者说，从每个叶子到根的所有路径上不能有两个连续的红色结点。
- 或者说，红色结点的父结点和子结点均是黑色的。
- 从任一结点到其每个叶子的所有简单路径都包含相同数目的黑色结点。
红黑树的结点定义如下:
// 红黑树结点定义
typedef struct RBNode {
int key;
RBNode *parent; // 父结点
RBNode *leftTree, *rightTree; // 左右孩子结点
int color; // 表示颜色
// 通常使用 0/1 表示 红/黑
} node;这些约束确保了红黑树的关键特性：
从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。
所以，这个树大致上是平衡的。常见的基本操作比如插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例，这个在高度上的理论上限允许红黑树在最坏情况下都是高效的，而不同于普通的二叉查找树。
为什么会有这样的性质？以下给出大致证明：
- 因为性质4，路径不能有两个相邻的红色结点，
- 而最短的可能路径都是黑色结点，最长的可能路径有交替的红色和黑色结点。
- 又因为性质5所有最长的路径都有相同数目的黑色结点，
- 所以，没有路径能多于任何其他路径的两倍长。
对于有
根据性质5，对于每一个红黑树结点，都有一个属性：黑高（Black Height）。
黑高表示，在一棵红黑树中，从某个结点x出发（不包含该结点）到达一个叶结点的任意一条简单路径上包含的黑色结点（包含叶子结点）的数目，记为bh(x) 。
值得注意的是，在很多树数据结构的表示中，一个结点有可能只有一个子结点，而叶子结点包含数据。用这种范例表示红黑树是可能的，但是这会改变一些性质并使算法复杂。为此，本文中我们使用“NIL叶子”，如上图所示，它不包含数据而只充当树在此结束的指示。这些结点在绘图中经常被省略，导致了这些树好像同上述原则相矛盾，而实际上不是这样。与此有关的结论是所有结点都有两个子结点，尽管其中的一个或两个可能是空叶子。
对于平衡二叉树（AVL）而言，需要首先通过查的方式，找到插入的位置，新结点的插入会导致平衡性破环，这个时候需要通过LL、RR、LR、RL四种方式的判别，分别进行右旋、左旋、先左旋再右旋、先右旋再左旋的方式，恢复成AVL树。红黑树的插入，跟平衡二叉树也有类似的地方。
红黑树也是一个特化的二叉查找树，因此红黑树上的只读操作与普通二叉查找树上的只读操作相同。在插入过程中，首先，以二叉查找树的方法增加结点并标记它为红色。
问题来了，为什么对于新插入的结点，一定要标记成红色（除了空树插入根结点）？
因为如果设为黑色，就会导致根到叶子的路径上有一条路上，多一个额外的黑结点，这样的话，将会违反性质5——从任一结点到其每个叶子的所有简单路径都包含相同数目的黑色结点。
标记为红色后，依然可能产生冲突，这里需要进行颜色变更（color flips）、树旋转的的方式进行调整。这里，我们使用同人类的家族树中一样，我们将使用术语：叔父结点，来指一个结点的父结点的兄弟结点。
插入过程中，注意：
- 性质1和性质3总是保持着。
- 性质4只在增加红色结点、重绘黑色结点为红色，或做旋转时可能会变化，从而不符合。
- 性质5只在增加黑色结点、重绘红色结点为黑色，或做旋转时可能会变化，从而不符合。 在下面的示意图中，将要插入的结点标为N，N的父结点标为P，N的祖父结点标为G，N的叔父结点标为U。
首先增加接口，可以直接获取某一结点的叔父结点和祖父结点。可以通过下列函数：
// 获取祖父结点
node* grandparent(node *n)
{
if (n == NULL || n->parent == NULL) {
return NULL;
}
return n->parent->parent;
}
// 获取叔父结点
node* uncle(node *n)
{
if (n == NULL || grandparent(n) == NULL) {
return NULL;
}
if (n->parent == grandparent(n)->left) {
return grandparent(n)->right;
} else {
return grandparent(n)->left;
}
}新结点N位于树的根上，没有父结点。在这种情形下，我们把它重绘为黑色以满足性质2。因为它在每个路径上对黑结点数目增加一，性质5符合。
void insert_case1(node *n)
{
if (n != NULL && n->parent == NULL) {
n->color = BLACK;
}
return;
}性质4没有失效（新结点是红色的）。在这种情形下，树仍是有效的。性质5也未受到威胁，尽管新结点N有两个黑色叶子子结点；但由于新结点N是红色，通过它的每个子结点的路径就都有同通过它所取代的黑色的叶子的路径同样数目的黑色结点，所以依然满足这个性质。
void insert_case2(node *n)
{
/* 树仍旧有效，不需要做整改 */
if (n != NULL && n->parent->color == BLACK) {
return;
}
return;
}除了以上的场景外，插入的新结点的父结点必须为红色，所以它一定有祖父结点。这一点可以使用反证法，因为如果父结点是根结点，那父结点就应当是黑色。因此，新结点总有一个叔父结点，对于这个叔父结点，并不确定其是否是空结点，在情形4和5下它可能是空叶子结点（NIL）。
此时新插入结点N，为P的左孩子结点或右孩子结点都属于情形3，这里图仅显示N做为P左子树的情形。
如何使得这个二叉树重新恢复成红黑树，我们可以将它们父结点和叔父结点两个重绘为黑色，并重绘祖父结点G为红色（用来保持性质5）。现在我们的新结点N有了一个黑色的父结点P。因为通过父结点P或叔父结点U的任何路径都必定通过祖父结点G，在这些路径上的黑结点数目没有改变。
但是，红色的祖父结点G可能是根结点，这就违反了性质2。也有可能祖父结点G的父结点是红色的，这就违反了性质4。
为了解决这个问题，我们在祖父结点G上递归地进行情形1的整个过程（也就是，把G当成是新加入的结点进行各种情形的检查）。
void insert_case3(node *n)
{
if (uncle(n) != NULL && uncle (n)->color == RED && n->parent->color == RED) {
// 叔父结点、父结点、祖父结点反色
n->parent->color = BLACK;
uncle (n)->color = BLACK;
// 情形3必有祖父结点
grandparent (n)->color = RED;
// 递归调用情形1
insert_case1(grandparent(n));
}
}在余下的情形下，我们假定父结点P是其祖父G的左子结点。如果它是右子结点，情形4和情形5中的左和右应当对调。
插入结点的父结点P是红色而叔父结点U是黑色或空叶子，新结点N是其父结点的左孩子结点（右孩子结点），而父结点P又是其父结点G的左孩子结点（右孩子结点）。这个时候，简称为LL型、RR型插入。
在这种情形下，我们进行针对祖父结点G的一次右（左）旋转；在旋转产生的树中，以前的父结点P现在是新结点N和以前的祖父结点G的父结点。我们知道以前的祖父结点G是黑色，否则父结点P就不可能是红色（如果P和G都是红色就违反了性质4，所以G必须是黑色）。
我们切换以前的父结点P和祖父结点G的颜色，结果的树满足性质4。性质5也仍然保持满足，因为通过这三个结点中任何一个的所有路径以前都通过祖父结点G，现在它们都通过以前的父结点P。在各自的情形下，这都是三个结点中唯一的黑色结点。
void insert_case4(node *n)
{
// 父亲和祖父结点染色
n->parent->color = BLACK;
grandparent (n)->color = RED;
// 结点是左孩子，父结点是祖父结点的左孩子
if (n == n->parent->left && n->parent == grandparent(n)->left) {
rotate_right(n->parent);
} else {
// 结点是右孩子，父结点是祖父结点的右孩子
// Here, n == n->parent->right && n->parent == grandparent (n)->right
rotate_left(n->parent);
}
}父结点P是红色而叔父结点U是黑色或空叶子，并且新结点N是其父结点P的右孩子（或者左孩子）结点,而父结点P又是祖父结点的左孩子（或者右孩子）结点。这个时候，简称为LR型、RL型插入。
那么，我们需要再进行一次左旋(右旋转)转调换新结点和其父结点的角色，调整一次后，并没有符合红黑树的条件。接着，我们按情形4处理父结点P，以解决失效的性质4——不能有两个连续的红色结点。
在这种情形下，此时的场景演变成了，在LL型插入，即插入结点的父结点P是红色而叔父结点U是黑色或空叶子，新结点N是其父结点的左孩子结点（右孩子结点），而父结点P又是其父结点G的左孩子结点（右孩子结点）。此时，我们按照场景四处理，再次进行右旋（左旋）后染色。
void insert_case5(node *n)
{
// 结点是右孩子，父结点是祖父结点的左孩子,LR型
if (n == n->parent->right && n->parent == grandparent(n)->left) {
rotate_left(n);
n = n->left;
// 结点是左孩子，父结点是祖父结点的右孩子
} else if (n == n->parent->left && n->parent == grandparent(n)->right) {
rotate_right(n);
n = n->right;
}
insert_case4 (n);
}
对于LL、RR、LR、RL类型插入的再调整，此处不做过多的解释，因为在AVL的再平衡过程中，已经进行了非常详细的阐述。
左旋和右旋是树的基本旋转操作，理解树旋转过程的关键，在于理解其中不变的约束。
树的旋转操作，不会导致叶结点顺序的改变（可以理解为旋转操作前后，树的中序遍历结果是一致的），旋转过程中也始终受二叉搜索树的主要性质约束：右子结点比父结点大、左子结点比父结点小。
但是，尤其需要注意的是，进行右旋转时，旋转前根的左孩子结点的右孩子结点（例如上图中以A为父结点的β结点）会变成根的左结点（根结点B的左孩子结点），根本身则在旋转后会变成新的根的右孩子结点（B变成了A的右孩子结点），而在这一过程中，整棵树一直遵守着前面提到的二叉排序树的约束。相反的左旋转操作亦然。至于左旋和右旋的基本操作可以如下代码实现：
右旋是一种“辈分”的上升，所谓子替代父：
struct Node {
int value;
bool color;
Node *leftTree, *rightTree, *parent;
};
// 这里的p就是需要右旋的结点A
void rotate_right(Node *p)
{
Node *gp = grandparent(p);
Node *fa = p->parent;
Node *y = p->rightTree;
// p结点的右子树变成了父结点的左子树
fa->leftTree = y;
if (y != NULL) {
y->parent = fa;
}
// p结点的父结点变成了它的右孩子，父子逆置
p->rightTree = fa;
fa->parent = p;
// 根结点重定义
if (root == fa) {
root = p;
}
// 祖父结点变成了其父结点，因为p顶替了它的父结点，让原来的父结点变成了孩子
p->parent = gp;
if (gp != NULL) {
// p变成了祖父结点的孩子结点，具体左右，根据其父结点的原本位置
if (gp->leftTree == fa) {
gp->leftTree = p;
} else {
gp->rightTree = p;
}
}
}右旋过程，同理也是一种“辈分上升”，是子变成父。同理：
// 这里的p就是需要左旋的结点B
void rotate_left(Node *p)
{
// 根结点无法左旋，但是可以右旋
if (p->parent == NULL) {
root = p;
return;
}
Node *gp = grandparent(p);
Node *fa = p->parent;
Node *y = p->leftTree;
// 左子树变成了父结点的右子树，
fa->rightTree = y;
if (y != NULL) {
y->parent = fa;
}
// 父结点变成自己的左子树
p->leftTree = fa;
fa->parent = p;
if (root == fa) {
root = p;
}
// 子代替父结点，成为祖父结点的子结点
p->parent = gp;
if (gp != NULL) {
if (gp->leftTree == fa) {
gp->leftTree = p;
} else {
gp->rightTree = p;
}
}
}与平衡二叉树的删除类似，红黑树的删除也会破坏原本的性质，所以，需要重新调整。关于删除结点，可能会有以下的特点：
- 删除操作的时间复杂度：
$O(log_2{N})$ 。 - 删除结点的处理方式，与二叉排序树的删除一样。
- 删除操作可能会破坏红黑树的结点颜色、位置，使其再次满足红黑树性质。 红黑树的删除操作非常复杂，暂时不作详细陈述。 #未完待续