c语言红黑树

下面是一个基于C语言实现的红黑树示例代码：

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

#define RED 0
#define BLACK 1

typedef struct Node {
    int value;
    int color;
    struct Node* left;
    struct Node* right;
    struct Node* parent;
} Node;

Node* root;

void insert(int value) {
    Node* node = (Node*) malloc(sizeof(Node));
    node->value = value;
    node->color = RED;
    node->left = NULL;
    node->right = NULL;
    node->parent = NULL;

    Node* parent = NULL;
    Node* current = root;
    while (current != NULL) {
        parent = current;
        if (value < current->value) {
            current = current->left;
        } else {
            current = current->right;
        }
    }
    node->parent = parent;
    if (parent == NULL) {
        root = node;
    } else if (value < parent->value) {
        parent->left = node;
    } else {
        parent->right = node;
    }

    fixup(node);
}

void fixup(Node* node) {
    while (node->parent != NULL && node->parent->color == RED) {
        if (node->parent == node->parent->parent->left) {
            Node* uncle = node->parent->parent->right;
            if (uncle != NULL && uncle->color == RED) {
                node->parent->color = BLACK;
                uncle->color = BLACK;
                node->parent->parent->color = RED;
                node = node->parent->parent;
            } else {
                if (node == node->parent->right) {
                    node = node->parent;
                    rotate_left(node);
                }
                node->parent->color = BLACK;
                node->parent->parent->color = RED;
                rotate_right(node->parent->parent);
            }
        } else {
            Node* uncle = node->parent->parent->left;
            if (uncle != NULL && uncle->color == RED) {
                node->parent->color = BLACK;
                uncle->color = BLACK;
                node->parent->parent->color = RED;
                node = node->parent->parent;
            } else {
                if (node == node->parent->left) {
                    node = node->parent;
                    rotate_right(node);
                }
                node->parent->color = BLACK;
                node->parent->parent->color = RED;
                rotate_left(node->parent->parent);
            }
        }
    }
    root->color = BLACK;
}

void rotate_left(Node* node) {
    Node* right = node->right;
    node->right = right->left;
    if (right->left != NULL) {
        right->left->parent = node;
    }
    right->parent = node->parent;
    if (node->parent == NULL) {
        root = right;
    } else if (node == node->parent->left) {
        node->parent->left = right;
    } else {
        node->parent->right = right;
    }
    right->left = node;
    node->parent = right;
}

void rotate_right(Node* node) {
    Node* left = node->left;
    node->left = left->right;
    if (left->right != NULL) {
        left->right->parent = node;
    }
    left->parent = node->parent;
    if (node->parent == NULL) {
        root = left;
    } else if (node == node->parent->left) {
        node->parent->left = left;
    } else {
        node->parent->right = left;
    }
    left->right = node;
    node->parent = left;
}

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

int main() {
    insert(10);
    insert(20);
    insert(30);
    insert(15);
    insert(18);
    insert(25);

    printf("Inorder traversal of the tree: ");
    inorder_traverse(root);
    printf("\n");

    return 0;
}

这个示例代码实现了红黑树的基本操作，包括插入、修正颜色、左旋和右旋。在主函数中插入了一些节点并进行了中序遍历输出，以验证红黑树的正确性。