【数据结构】红黑树

1. 红黑树的定义

红黑树（RBT）是二叉排序树，即满足左子树结点值<根节点值<右子树结点值。同时，与普通BST相比，需满足：

1. 每个结点都是红色，或是黑色的。
2. 根结点是黑色的。
3. 叶结点（外部结点、NULL结点、失败结点）均是黑色的。
4. 不存在两个相邻的红结点（即红结点的父结点和孩子结点均是黑色的）。
5. 对每个结点，从该结点到任一叶结点的简单路径上，所含黑结点的数目相同。

口诀：左跟右，根叶黑，不红红，黑路同。

struct RBnode{  // 红黑树的结点定义
    int key;  // 关键字的值
    RBnode* parent;  // 父结点指针
    RBnode* lchild;  // 左孩子指针
    RBnode* rchild;  // 右孩子指针
    int color;  // 结点颜色。如：0/1 表示 黑/红
};

示例：

2. 结点的“黑高”

结点的黑高bh——从某结点出发（不含该结点）到达任一空叶结点的路径上黑结点的总数。

3. 红黑树的性质

性质1：

从根结点到叶结点的最长路径不大于最短路径的2倍。

性质2：

4. 红黑树的查找

与BST、AVL相同，从根出发，左小右大，若查找到一个空叶结点，则查找失败。

查找效率与AVL树同等数量级。

5. 红黑树的插入

动画演示（文章最下方点击阅读原文）： https://www.cs.usfca.edu/~galles/visualization/RedBlack.html

1. 先查找，确定插入位置（原理同二叉排序树），插入新结点。
2. 新结点是根——染为黑色。
3. 新结点非根——染为红色。

• 若插入新结点后依然满足红黑色定义，则插入结束
• 若插入新结点后不满足红黑树定义，则需调整，使其重新满足红黑树定义。调整方法依据叔叔结点。

黑叔：旋转+染色

LL型：右单旋，父换爷+染色。

RR型：左单旋，父换爷+染色。

LR型：左、右单旋，儿换爷+染色。

RL型：右、左单旋，儿换爷+染色。

红叔：染色+变新

叔父爷染色，爷变为新结点。

示例：从一棵空的红黑树开始，插入：20,10,5,30,40

6. 红黑树删除

在红黑树中删除结点的处理方式和“二叉排序树的删除”一样。

删除完后，可能破坏“红黑树特性”，此时需要调整结点颜色、位置，使其再次满足“红黑树特性”。

7. 小结