C语言用字符串做红黑树

红黑树是一种二叉搜索树，它有以下特点：

1. 每个节点是红色或黑色。
2. 根节点是黑色。
3. 每个叶子节点（NIL节点，空节点）是黑色的。
4. 如果一个节点是红色的，则它的子节点必须是黑色的。
5. 从任意一个节点到其每个叶子节点的所有路径都包含相同数目的黑色节点。
6. 在插入和删除节点时，必须保持以上五条性质不变。

对于C语言中的字符串，我们需要使用一个比较函数来比较两个字符串的大小。比较函数可以使用strcmp函数，该函数返回值为0表示两个字符串相等，小于0表示字符串1小于字符串2，大于0表示字符串1大于字符串2。

下面是使用C语言字符串实现红黑树的示例代码：

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

typedef struct node {
    char *key;
    int value;
    int color; // 0 for black, 1 for red
    struct node *left;
    struct node *right;
    struct node *parent;
} Node;

Node *root = NULL;

Node *create_node(char *key, int value) {
    Node *new_node = (Node *) malloc(sizeof(Node));
    new_node->key = key;
    new_node->value = value;
    new_node->color = 1; // new node is always red
    new_node->left = NULL;
    new_node->right = NULL;
    new_node->parent = NULL;
    return new_node;
}

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

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

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

void insert_node(char *key, int value) {
    Node *new_node = create_node(key, value);
    Node *parent = NULL;
    Node *current = root;
    while (current != NULL) {
        parent = current;
        if (strcmp(new_node->key, current->key) < 0) {
            current = current->left;
        } else {
            current = current->right;
        }
    }
    new_node->parent = parent;
    if (parent == NULL) {
        root = new_node;
    } else if (strcmp(new_node->key, parent->key) < 0) {
        parent->left = new_node;
    } else {
        parent->right = new_node;
    }
    insert_fixup(new_node);
}

void inorder_traversal(Node *node) {
    if (node != NULL) {
        inorder_traversal(node->left);
        printf("%s: %d\n", node->key, node->value);
        inorder_traversal(node->right);
    }
}

int main() {
    insert_node("c", 3);
    insert_node("a", 1);
    insert_node("b", 2);
    insert_node("e", 5);
    insert_node("d", 4);
    inorder_traversal(root);
    return 0;
}

该代码使用了字符串作为红黑树的键，并使用strcmp函数来比较两个字符串的大小。在插入节点时，使用insert_fixup函数来保持红黑树的性质不变。最后，使用inorder_traversal函数来遍历红黑树并输出节点的键和值。