使用c写出红黑树的算法

以下是使用 C 语言实现红黑树的算法（参考自《算法导论》）：

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

#define RED 0
#define BLACK 1

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

Node *NIL;

void left_rotate(Node **root, Node *x) {
    Node *y = x->right;
    x->right = y->left;

    if (y->left != NIL) {
        y->left->parent = x;
    }

    y->parent = x->parent;

    if (x->parent == NIL) {
        *root = y;
    } else if (x == x->parent->left) {
        x->parent->left = y;
    } else {
        x->parent->right = y;
    }

    y->left = x;
    x->parent = y;
}

void right_rotate(Node **root, Node *y) {
    Node *x = y->left;
    y->left = x->right;

    if (x->right != NIL) {
        x->right->parent = y;
    }

    x->parent = y->parent;

    if (y->parent == NIL) {
        *root = x;
    } else if (y == y->parent->left) {
        y->parent->left = x;
    } else {
        y->parent->right = x;
    }

    x->right = y;
    y->parent = x;
}

void insert_fixup(Node **root, Node *z) {
    while (z->parent->color == RED) {
        if (z->parent == z->parent->parent->left) {
            Node *y = z->parent->parent->right;

            if (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;
                    left_rotate(root, z);
                }

                z->parent->color = BLACK;
                z->parent->parent->color = RED;
                right_rotate(root, z->parent->parent);
            }
        } else {
            Node *y = z->parent->parent->left;

            if (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;
                    right_rotate(root, z);
                }

                z->parent->color = BLACK;
                z->parent->parent->color = RED;
                left_rotate(root, z->parent->parent);
            }
        }
    }

    (*root)->color = BLACK;
}

void insert(Node **root, int key) {
    Node *z = (Node *) malloc(sizeof(Node));
    z->key = key;
    z->left = NIL;
    z->right = NIL;
    z->color = RED;

    Node *y = NIL;
    Node *x = *root;

    while (x != NIL) {
        y = x;

        if (z->key < x->key) {
            x = x->left;
        } else {
            x = x->right;
        }
    }

    z->parent = y;

    if (y == NIL) {
        *root = z;
    } else if (z->key < y->key) {
        y->left = z;
    } else {
        y->right = z;
    }

    insert_fixup(root, z);
}

void inorder_traversal(Node *root) {
    if (root != NIL) {
        inorder_traversal(root->left);
        printf("%d ", root->key);
        inorder_traversal(root->right);
    }
}

int main() {
    NIL = (Node *) malloc(sizeof(Node));
    NIL->color = BLACK;

    Node *root = NIL;

    insert(&root, 6);
    insert(&root, 5);
    insert(&root, 4);
    insert(&root, 3);
    insert(&root, 2);
    insert(&root, 1);

    inorder_traversal(root);

    return 0;
}

以上代码实现了红黑树的插入和中序遍历，可以根据需要进行扩展。