c语言红黑树初始化代码详解

红黑树是一种自平衡的二叉搜索树，它可以保证在最坏情况下，插入、删除和查找操作的时间复杂度都是 O(log n)。下面是一份C语言红黑树的初始化代码详解：

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

// 定义红黑树节点结构体
typedef struct rb_node {
    int data;             // 存储的数据
    int color;            // 节点颜色，0表示黑色，1表示红色
    struct rb_node *left; // 左子节点
    struct rb_node *right;// 右子节点
    struct rb_node *parent; // 父节点
} rb_node;

// 定义红黑树结构体
typedef struct rb_tree {
    rb_node *root; // 根节点
    rb_node *nil;  // 哨兵节点
} rb_tree;

// 初始化哨兵节点
void init_nil(rb_tree *tree) {
    tree->nil = (rb_node *) malloc(sizeof(rb_node));
    tree->nil->color = 0; // 哨兵节点为黑色
    tree->nil->parent = NULL;
    tree->nil->left = NULL;
    tree->nil->right = NULL;
}

// 初始化红黑树
void init_rb_tree(rb_tree *tree) {
    init_nil(tree);
    tree->root = tree->nil;
}

// 创建红黑树节点
rb_node *create_rb_node(int data) {
    rb_node *node = (rb_node *) malloc(sizeof(rb_node));
    node->data = data;
    node->color = 1; // 新节点为红色
    node->left = NULL;
    node->right = NULL;
    node->parent = NULL;
    return node;
}

// 插入节点
void insert_rb_node(rb_tree *tree, rb_node *node) {
    rb_node *x = tree->root;
    rb_node *y = tree->nil;
    while (x != tree->nil) {
        y = x;
        if (node->data < x->data) {
            x = x->left;
        } else {
            x = x->right;
        }
    }
    node->parent = y;
    if (y == tree->nil) {
        tree->root = node;
    } else if (node->data < y->data) {
        y->left = node;
    } else {
        y->right = node;
    }
    node->left = tree->nil;
    node->right = tree->nil;
    node->color = 1;
    insert_fixup(tree, node);
}

// 修复插入操作后的红黑树性质
void insert_fixup(rb_tree *tree, rb_node *node) {
    while (node->parent->color == 1) {
        if (node->parent == node->parent->parent->left) {
            rb_node *y = node->parent->parent->right;
            if (y->color == 1) {
                node->parent->color = 0;
                y->color = 0;
                node->parent->parent->color = 1;
                node = node->parent->parent;
            } else {
                if (node == node->parent->right) {
                    node = node->parent;
                    left_rotate(tree, node);
                }
                node->parent->color = 0;
                node->parent->parent->color = 1;
                right_rotate(tree, node->parent->parent);
            }
        } else {
            rb_node *y = node->parent->parent->left;
            if (y->color == 1) {
                node->parent->color = 0;
                y->color = 0;
                node->parent->parent->color = 1;
                node = node->parent->parent;
            } else {
                if (node == node->parent->left) {
                    node = node->parent;
                    right_rotate(tree, node);
                }
                node->parent->color = 0;
                node->parent->parent->color = 1;
                left_rotate(tree, node->parent->parent);
            }
        }
    }
    tree->root->color = 0;
}

// 左旋
void left_rotate(rb_tree *tree, rb_node *node) {
    rb_node *y = node->right;
    node->right = y->left;
    if (y->left != tree->nil) {
        y->left->parent = node;
    }
    y->parent = node->parent;
    if (node->parent == tree->nil) {
        tree->root = y;
    } else if (node == node->parent->left) {
        node->parent->left = y;
    } else {
        node->parent->right = y;
    }
    y->left = node;
    node->parent = y;
}

// 右旋
void right_rotate(rb_tree *tree, rb_node *node) {
    rb_node *y = node->left;
    node->left = y->right;
    if (y->right != tree->nil) {
        y->right->parent = node;
    }
    y->parent = node->parent;
    if (node->parent == tree->nil) {
        tree->root = y;
    } else if (node == node->parent->left) {
        node->parent->left = y;
    } else {
        node->parent->right = y;
    }
    y->right = node;
    node->parent = y;
}

// 中序遍历
void inorder_rb_tree(rb_node *node) {
    if (node != NULL) {
        inorder_rb_tree(node->left);
        printf("%d ", node->data);
        inorder_rb_tree(node->right);
    }
}

int main() {
    rb_tree tree;
    init_rb_tree(&tree);
    int arr[] = {11, 2, 14, 1, 7, 15, 5, 8, 4};
    int len = sizeof(arr) / sizeof(arr[0]);
    for (int i = 0; i < len; i++) {
        rb_node *node = create_rb_node(arr[i]);
        insert_rb_node(&tree, node);
    }
    printf("中序遍历红黑树：");
    inorder_rb_tree(tree.root);
    printf("\n");
    return 0;
}

以上是一份简单的红黑树初始化代码，其中包含了红黑树的初始化、节点插入、修复插入操作后的红黑树性质、左旋、右旋、中序遍历等基本操作。在使用时，需要注意初始化哨兵节点，以及在创建新节点时将其颜色设置为红色。