用C实现一个红黑树

以下是一个简单的红黑树实现示例：

#include <stdio.h>
#include <stdlib.h>

enum Color {RED, BLACK};

typedef struct Node {
    int key;
    enum Color color;
    struct Node *left, *right, *parent;
} Node;

Node *root = NULL;

Node *createNode(int key) {
    Node *newNode = (Node*)malloc(sizeof(Node));
    newNode->key = key;
    newNode->color = RED;
    newNode->left = newNode->right = newNode->parent = NULL;
    return newNode;
}

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

void fixViolation(Node *newNode) {
    Node *parent, *grandparent;
    while (newNode != root && newNode->color != BLACK && newNode->parent->color == RED) {
        parent = newNode->parent;
        grandparent = newNode->parent->parent;
        if (parent == grandparent->left) {
            Node *uncle = grandparent->right;
            if (uncle != NULL && uncle->color == RED) {
                grandparent->color = RED;
                parent->color = BLACK;
                uncle->color = BLACK;
                newNode = grandparent;
            } else {
                if (newNode == parent->right) {
                    leftRotate(parent);
                    newNode = parent;
                    parent = newNode->parent;
                }
                rightRotate(grandparent);
                int temp = parent->color;
                parent->color = grandparent->color;
                grandparent->color = temp;
                newNode = parent;
            }
        } else {
            Node *uncle = grandparent->left;
            if (uncle != NULL && uncle->color == RED) {
                grandparent->color = RED;
                parent->color = BLACK;
                uncle->color = BLACK;
                newNode = grandparent;
            } else {
                if (newNode == parent->left) {
                    rightRotate(parent);
                    newNode = parent;
                    parent = newNode->parent;
                }
                leftRotate(grandparent);
                int temp = parent->color;
                parent->color = grandparent->color;
                grandparent->color = temp;
                newNode = parent;
            }
        }
    }
    root->color = BLACK;
}

void insert(int key) {
    Node *newNode = createNode(key);
    Node *current = root;
    Node *parent = NULL;
    while (current != NULL) {
        parent = current;
        if (newNode->key < current->key) {
            current = current->left;
        } else {
            current = current->right;
        }
    }
    newNode->parent = parent;
    if (parent == NULL) {
        root = newNode;
    } else if (newNode->key < parent->key) {
        parent->left = newNode;
    } else {
        parent->right = newNode;
    }
    fixViolation(newNode);
}

void inorderTraversal(Node *node) {
    if (node != NULL) {
        inorderTraversal(node->left);
        printf("%d ", node->key);
        inorderTraversal(node->right);
    }
}

int main() {
    insert(7);
    insert(3);
    insert(18);
    insert(10);
    insert(22);
    insert(8);
    insert(11);
    insert(26);
    inorderTraversal(root);
    return 0;
}

红黑树的插入操作包括两个部分：插入节点和修复违规（violation）。插入节点与二叉搜索树类似，但需要将节点的颜色设置为红色。修复违规分为两种情况，一种是父节点和叔节点都是红色，需要将父节点和叔节点都变为黑色，祖父节点变为红色，然后继续向上修复；另一种是父节点为红色，叔节点为黑色（或者为NULL），需要通过旋转将父节点和祖父节点的颜色交换，然后向上修复。最后需要将根节点的颜色设置为黑色。

以上红黑树实现中还包括左旋和右旋操作，用于修复第二种违规情况。左旋操作将x节点向左旋转，使得其右子节点y成为x的父节点，x成为y的左子节点；右旋操作将x节点向右旋转，使得其左子节点y成为x的父节点，x成为y的右子节点。

此外，红黑树的删除操作也需要进行修复违规操作，但比插入操作更为复杂，这里不再详细讨论