C语音实现红黑树的完整代码

红黑树是一种自平衡二叉查找树，它在插入和删除操作后能够自动调整以保持平衡。C语言实现红黑树的代码如下：

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

enum Color {
    RED,
    BLACK
};

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

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

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

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

void fixViolation(struct Node **root, struct Node *node) {
    struct Node *parent = NULL;
    struct Node *grandParent = NULL;

    while ((node != *root) && (node->color != BLACK) && (node->parent->color == RED)) {
        parent = node->parent;
        grandParent = node->parent->parent;

        if (parent == grandParent->left) {
            struct Node *uncle = grandParent->right;

            if (uncle != NULL && uncle->color == RED) {
                grandParent->color = RED;
                parent->color = BLACK;
                uncle->color = BLACK;
                node = grandParent;
            } else {
                if (node == parent->right) {
                    rotateLeft(root, parent);
                    node = parent;
                    parent = node->parent;
                }

                rotateRight(root, grandParent);
                int tempColor = parent->color;
                parent->color = grandParent->color;
                grandParent->color = tempColor;
                node = parent;
            }
        } else {
            struct Node *uncle = grandParent->left;

            if ((uncle != NULL) && (uncle->color == RED)) {
                grandParent->color = RED;
                parent->color = BLACK;
                uncle->color = BLACK;
                node = grandParent;
            } else {
                if (node == parent->left) {
                    rotateRight(root, parent);
                    node = parent;
                    parent = node->parent;
                }

                rotateLeft(root, grandParent);
                int tempColor = parent->color;
                parent->color = grandParent->color;
                grandParent->color = tempColor;
                node = parent;
            }
        }
    }

    (*root)->color = BLACK;
}

void insert(struct Node **root, int data) {
    struct Node *newNode = createNode(data);

    struct Node *currentNode = *root, *parentNode = NULL;

    while (currentNode != NULL) {
        parentNode = currentNode;

        if (newNode->data < currentNode->data)
            currentNode = currentNode->left;
        else
            currentNode = currentNode->right;
    }

    newNode->parent = parentNode;

    if (parentNode == NULL)
        *root = newNode;
    else if (newNode->data < parentNode->data)
        parentNode->left = newNode;
    else
        parentNode->right = newNode;

    fixViolation(root, newNode);
}

void inorderTraversal(struct Node *root) {
    if (root == NULL)
        return;

    inorderTraversal(root->left);

    printf("%d ", root->data);

    inorderTraversal(root->right);
}

int main() {
    struct Node *root = NULL;

    insert(&root, 7);
    insert(&root, 3);
    insert(&root, 18);
    insert(&root, 10);
    insert(&root, 22);
    insert(&root, 8);
    insert(&root, 11);
    insert(&root, 26);

    printf("Inorder traversal of the constructed tree: ");
    inorderTraversal(root);

    return 0;
}