使用C++写一份红黑树的基本实现代码

以下是一个基本的红黑树实现的C代码，包括插入、删除、查找和打印操作：

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

typedef enum { RED, BLACK } nodeColor;

typedef struct rbNode {
    int key;
    nodeColor color;
    struct rbNode *left, *right, *parent;
} rbNode;

rbNode *newNode(int key) {
    rbNode *node = (rbNode *)malloc(sizeof(rbNode));
    node->key = key;
    node->color = RED;
    node->left = node->right = node->parent = NULL;
    return node;
}

void rotateLeft(rbNode **root, rbNode *node) {
    rbNode *right = node->right;
    node->right = right->left;
    if (node->right != NULL) {
        node->right->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 rotateRight(rbNode **root, rbNode *node) {
    rbNode *left = node->left;
    node->left = left->right;
    if (node->left != NULL) {
        node->left->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 fixViolation(rbNode **root, rbNode *node) {
    rbNode *parent = NULL;
    rbNode *grandparent = NULL;
    while ((node != *root) && (node->color == RED) && (node->parent->color == RED)) {
        parent = node->parent;
        grandparent = parent->parent;
        if (parent == grandparent->left) {
            rbNode *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 {
            rbNode *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(rbNode **root, int key) {
    rbNode *node = newNode(key);
    rbNode *parent = NULL;
    rbNode *current = *root;
    while (current != NULL) {
        parent = current;
        if (node->key < current->key) {
            current = current->left;
        } else {
            current = current->right;
        }
    }
    node->parent = parent;
    if (parent == NULL) {
        *root = node;
    } else if (node->key < parent->key) {
        parent->left = node;
    } else {
        parent->right = node;
    }
    fixViolation(root, node);
}

rbNode *minValueNode(rbNode *node) {
    rbNode *current = node;
    while (current->left != NULL) {
        current = current->left;
    }
    return current;
}

void fixDoubleBlack(rbNode **root, rbNode *node) {
    if (node == *root) {
        return;
    }
    rbNode *sibling = NULL;
    rbNode *parent = node->parent;
    if (node == parent->left) {
        sibling = parent->right;
        if (sibling->color == RED) {
            sibling->color = BLACK;
            parent->color = RED;
            rotateLeft(root, parent);
            sibling = parent->right;
        }
        if ((sibling->left == NULL || sibling->left->color == BLACK) &&
            (sibling->right == NULL || sibling->right->color == BLACK)) {
            sibling->color = RED;
            if (parent->color == BLACK) {
                fixDoubleBlack(root, parent);
            } else {
                parent->color = BLACK;
            }
        } else {
            if (sibling->right == NULL || sibling->right->color == BLACK) {
                sibling->left->color = BLACK;
                sibling->color = RED;
                rotateRight(root, sibling);
                sibling = parent->right;
            }
            sibling->color = parent->color;
            parent->color = BLACK;
            sibling->right->color = BLACK;
            rotateLeft(root, parent);
        }
    } else {
        sibling = parent->left;
        if (sibling->color == RED) {
            sibling->color = BLACK;
            parent->color = RED;
            rotateRight(root, parent);
            sibling = parent->left;
        }
        if ((sibling->left == NULL || sibling->left->color == BLACK) &&
            (sibling->right == NULL || sibling->right->color == BLACK)) {
            sibling->color = RED;
            if (parent->color == BLACK) {
                fixDoubleBlack(root, parent);
            } else {
                parent->color = BLACK;
            }
        } else {
            if (sibling->left == NULL || sibling->left->color == BLACK) {
                sibling->right->color = BLACK;
                sibling->color = RED;
                rotateLeft(root, sibling);
                sibling = parent->left;
            }
            sibling->color = parent->color;
            parent->color = BLACK;
            sibling->left->color = BLACK;
            rotateRight(root, parent);
        }
    }
}

void delete(rbNode **root, int key) {
    rbNode *node = *root;
    while (node != NULL) {
        if (key < node->key) {
            node = node->left;
        } else if (key > node->key) {
            node = node->right;
        } else {
            if (node->left == NULL || node->right == NULL) {
                rbNode *child = node->left ? node->left : node->right;
                if (child == NULL) {
                    if (node->color == BLACK) {
                        fixDoubleBlack(root, node);
                    }
                    if (node == *root) {
                        *root = NULL;
                    } else {
                        if (node == node->parent->left) {
                            node->parent->left = NULL;
                        } else {
                            node->parent->right = NULL;
                        }
                    }
                    free(node);
                    node = NULL;
                } else {
                    *node = *child;
                    free(child);
                }
            } else {
                rbNode *successor = minValueNode(node->right);
                node->key = successor->key;
                delete(root, successor->key);
            }
            break;
        }
    }
}

rbNode *search(rbNode *root, int key) {
    if (root == NULL || root->key == key) {
        return root;
    }
    if (key < root->key) {
        return search(root->left, key);
    } else {
        return search(root->right, key);
    }
}

void inorderTraversal(rbNode *node) {
    if (node == NULL) {
        return;
    }
    inorderTraversal(node->left);
    printf("%d ", node->key);
    inorderTraversal(node->right);
}

int main() {
    rbNode *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 before deletion: ");
    inorderTraversal(root);
    printf("\n");
    delete(&root, 18);
    printf("Inorder traversal after deletion: ");
    inorderTraversal(root);
    printf("\n");
    return 0;
}

这份代码实现了基本的红黑树功能，包括插入、删除、查找和打印。你可以根据需要对其进行修改和扩展。