红黑树的规则
- 节点颜色：每个节点要么是红色的，要么是黑色的。
- 根节点是黑色：树的根节点必须是黑色的。
- 红色节点的父节点是黑色的：不能有两个连续的红色节点（即红色节点不能相邻）。
- 每个叶子节点（NIL 节点）是黑色的：虽然叶子节点没有存储数据，但在树的表示中，它们被视为黑色节点。在红黑树（Red-Black Tree）中，NIL 节点指的是一种虚拟的'空'节点，它是树中的叶子节点。尽管这些节点本身并不存储数据，它们在红黑树的实现中非常重要，主要用来简化树的结构和算法。
- 从任何节点到其每个叶子节点的路径上，必须包含相同数量的黑色节点：这一规则确保了从根到叶子路径的平衡性。
- 插入时的修正操作：在插入新节点时，可能会破坏红黑树的性质，需要通过旋转和颜色变化来修复树。
红黑树的存储结构
红黑树的结构主要由节点和树的关系组成。每个节点包含了数据（键值对）、左右子节点指针、父节点指针和颜色。树通过这些指针将节点连接起来，形成一个具有平衡性质的二叉查找树。
- 树的基本结构：每个节点都连接着左右子节点和父节点，确保树可以通过这些指针进行遍历、插入和删除操作。
- 颜色：每个节点的颜色（红色或黑色）用于保证红黑树的平衡性。根据红黑树的性质，树的高度限制和搜索效率可以保持在 O(logn) 时间复杂度。
// 枚举值表示颜色
enum Colour { RED, BLACK };
// 这里我们默认按 key/value 结构实现
template<class K, class V>
struct RBTreeNode {
// 这里更新控制平衡也要加入 parent 指针
pair<K, V> _kv;
RBTreeNode<K, V>* _left;
RBTreeNode<K, V>* _right;
RBTreeNode<K, V>* _parent;
Colour _col;
RBTreeNode(const pair<K, V>& kv) : _kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr) {}
};
template<class K, class V>
class RBTree {
typedef RBTreeNode<K, V> Node;
public:
private:
Node* _root = nullptr;
};
红黑树插入一个值的大概过程以及代码实现
说明：下图中假设我们把新增结点标识为 c(cur)，c 的父亲标识为 p(parent)，p 的父亲标识为 g(grandfather)，p 的兄弟标识为 u（uncle）。
