红黑树的节点结构

红黑树是一种自平衡二叉搜索树，它通过一系列规则来保证其高度接近于最小值，从而在平均情况下提供对数时间复杂度的操作。每个红黑树节点包含以下信息：

• 键（Key）：用于存储数据的关键字。
• 颜色（Color）：每个节点被标记为红色或黑色。

节点结构

为了实现上述功能，红黑树的节点通常定义如下：

struct Node {
    int key;           // 键值
    struct Node *left; // 左子节点指针
    struct Node *right;  // 右子节点指针
    bool color;         // 节点颜色，true表示红色，false表示黑色
};

规则

红黑树通过五条规则来保持其平衡性和有效性：

1. 每个节点：要么是红色，要么是黑色。
2. 根节点：必须为黑色。这一点对于确保整个树的最短路径长度是有必要的。
3. 叶子节点（null/空节点）：所有叶子节点都标为黑色。虽然它们没有数据键值，但被视作平衡树的一部分。
4. 红色连接规则：从任一节点到其后代的所有简单路径上包含相同数目的黑节点。这确保了红黑树的高度接近最小可能高度。
5. 红色节点限制：一个节点不能有两个红色的孩子。

节点插入与调整

在插入操作中，新节点初始被标记为红色，并通过一系列旋转和颜色翻转来维持上述规则。具体步骤如下：

1. 将新节点作为叶子节点插入（默认标记为红色）。
2. 如果父节点是黑色，则不需要进一步处理。
3. 否则，检查叔祖父节点的状态并进行相应的调整：
   • LL 或 RR：旋转以重新平衡树。
   • LR 或 RL：调整颜色和执行旋转。

通过这些步骤，可以确保红黑树的结构保持平衡，从而维持其对数时间复杂度的操作性能。