C++如何实现红黑树节点的颜色修正与旋转平衡算法

红黑树通过节点颜色和旋转操作维持近似平衡，从而保证查找、插入、删除在最坏情况下都能保持对数时间复杂度。理解颜色修正与旋转平衡是掌握底层搜索树算法的关键。

红黑树节点与基本结构

在C++中通常用枚举表示颜色，用结构体或类定义节点。每个节点包含键值、颜色标记以及左右子节点和父节点指针。

#include <iostream>

enum Color { RED, BLACK };

struct Node {
    int key;
    Color color;
    Node* left;
    Node* right;
    Node* parent;

    Node(int k) : key(k), color(RED), left(nullptr), right(nullptr), parent(nullptr) {}
};

左旋操作实现

左旋用于将以x为根的子树向左倾斜，使x的右子节点y成为新的根，x变为y的左子节点。下面是典型的左旋代码。

// 假设root为树根引用，x为要旋转的节点
void leftRotate(Node*& root, Node* x) {
    Node* y = x->right;
    x->right = y->left;
    if (y->left != nullptr) {
        y->left->parent = x;
    }
    y->parent = x->parent;
    if (x->parent == nullptr) {
        root = y;
    } else if (x == x->parent->left) {
        x->parent->left = y;
    } else {
        x->parent->right = y;
    }
    y->left = x;
    x->parent = y;
}

右旋操作实现

右旋是左旋的对称操作，将左子节点提升为子树根。

void rightRotate(Node*& root, Node* y) {
    Node* x = y->left;
    y->left = x->right;
    if (x->right != nullptr) {
        x->right->parent = y;
    }
    x->parent = y->parent;
    if (y->parent == nullptr) {
        root = x;
    } else if (y == y->parent->left) {
        y->parent->left = x;
    } else {
        y->parent->right = x;
    }
    x->right = y;
    y->parent = x;
}

颜色修正规则

插入新节点时默认染红，若父节点也为红则违反性质，需要进行修正。常见情况包括叔节点为红时的颜色翻转，以及叔节点为黑时的旋转加染色。

• 父红叔红：将父、叔变黑，祖父变红，向上递归
• 父红叔黑且呈直线：对祖父反向旋转并交换颜色
• 父红叔黑且呈折线：先对父同侧旋转，再按直线情况处理

简单的颜色翻转示例

// 处理父红叔红的情况
void fixRecolor(Node* parent, Node* uncle, Node* grand) {
    parent->color = BLACK;
    uncle->color = BLACK;
    grand->color = RED;
}

修正流程整合

实际插入修正函数会循环判断上述情形，结合leftRotate与rightRotate完成平衡。核心逻辑是先处理红红冲突，再通过旋转降低黑高差异。

小结

红黑树的颜色修正与旋转平衡是保障底层搜索树性能的基础。掌握C++中节点结构和左右旋实现，再理解不同冲突下的修正策略，就能写出稳定的自平衡树。更多细节可在具体插入删除函数中逐步完善。

C++红黑树旋转平衡修改时间：2026-07-31 07:33:21