面试题：C++ 实现红黑树的插入调整算法

红黑树节点结构（示例）

enum Color {RED, BLACK};

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

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

插入节点后可能破坏的红黑树性质
- 性质2：根节点是黑色：如果插入的节点是根节点，且插入时设置为红色，会破坏此性质。
- 性质4：每个红色节点的两个子节点都是黑色：当插入节点的父节点是红色时，会破坏此性质。
调整算法（恢复红黑树性质）

void insertFixup(RBNode*& root, RBNode* z) {
    while (z != root && z->parent->color == RED) {
        if (z->parent == z->parent->parent->left) {
            RBNode* y = z->parent->parent->right;
            if (y && y->color == RED) {
                z->parent->color = BLACK;
                y->color = BLACK;
                z->parent->parent->color = RED;
                z = z->parent->parent;
            } else {
                if (z == z->parent->right) {
                    z = z->parent;
                    leftRotate(root, z);
                }
                z->parent->color = BLACK;
                z->parent->parent->color = RED;
                rightRotate(root, z->parent->parent);
            }
        } else {
            RBNode* y = z->parent->parent->left;
            if (y && y->color == RED) {
                z->parent->color = BLACK;
                y->color = BLACK;
                z->parent->parent->color = RED;
                z = z->parent->parent;
            } else {
                if (z == z->parent->left) {
                    z = z->parent;
                    rightRotate(root, z);
                }
                z->parent->color = BLACK;
                z->parent->parent->color = RED;
                leftRotate(root, z->parent->parent);
            }
        }
    }
    root->color = BLACK;
}

左旋和右旋辅助函数

void leftRotate(RBNode*& root, RBNode* x) {
    RBNode* y = x->right;
    x->right = y->left;
    if (y->left) {
        y->left->parent = x;
    }
    y->parent = x->parent;
    if (!x->parent) {
        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(RBNode*& root, RBNode* y) {
    RBNode* x = y->left;
    y->left = x->right;
    if (x->right) {
        x->right->parent = y;
    }
    x->parent = y->parent;
    if (!y->parent) {
        root = x;
    } else if (y == y->parent->right) {
        y->parent->right = x;
    } else {
        y->parent->left = x;
    }
    x->right = y;
    y->parent = x;
}

插入函数（调用插入调整）

void insert(RBNode*& root, int key) {
    RBNode* z = new RBNode(key);
    RBNode* y = nullptr;
    RBNode* x = root;
    while (x) {
        y = x;
        if (z->key < x->key) {
            x = x->left;
        } else {
            x = x->right;
        }
    }
    z->parent = y;
    if (!y) {
        root = z;
    } else if (z->key < y->key) {
        y->left = z;
    } else {
        y->right = z;
    }
    insertFixup(root, z);
}

总结：插入节点后，通过insertFixup函数，结合左旋和右旋操作，能够恢复红黑树被破坏的性质。左旋和右旋操作改变树的结构，而节点颜色的调整保证红黑树的颜色性质得以维持。

面试题：C++ 实现红黑树的插入调整算法

知识考点

面试题答案