human 帮我写一个红黑树的算法要求带上注释; AI AI 红黑树是一种自平衡的二叉搜索树它保证了在最坏情况下基本动态集合操作的时间复杂度为 Olog n。下面是一个带注释的红黑树算法：python# 红黑树节点类class Node def __init__self key selfkey = key selfparent = None sel

AI: 好的，下面是使用 C/C++ 完整的红黑树实现代码，带有注释：

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

// 红黑树节点结构体
struct Node {
    int key;
    struct Node* left;
    struct Node* right;
    struct Node* parent;
    int color;  // 0表示黑色，1表示红色
};

// 红黑树结构体
struct RedBlackTree {
    struct Node* nil;   // 定义一个空节点
    struct Node* root;  // 根节点
};

// 创建一个新节点
struct Node* create_node(int key) {
    struct Node* node = (struct Node*)malloc(sizeof(struct Node));
    node->key = key;
    node->left = NULL;
    node->right = NULL;
    node->parent = NULL;
    node->color = 1;  // 新节点默认为红色
    return node;
}

// 初始化红黑树
void initialize(struct RedBlackTree* rbt) {
    rbt->nil = create_node(-1);  // 空节点默认值为-1
    rbt->nil->color = 0;         // 空节点默认为黑色
    rbt->root = rbt->nil;        // 根节点默认为nil节点
}

// 左旋操作
void left_rotate(struct RedBlackTree* rbt, struct Node* x) {
    struct Node* y = x->right;
    x->right = y->left;
    if (y->left != rbt->nil) {
        y->left->parent = x;
    }
    y->parent = x->parent;
    if (x->parent == rbt->nil) {
        rbt->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(struct RedBlackTree* rbt, struct Node* x) {
    struct Node* y = x->left;
    x->left = y->right;
    if (y->right != rbt->nil) {
        y->right->parent = x;
    }
    y->parent = x->parent;
    if (x->parent == rbt->nil) {
        rbt->root = y;
    } else if (x == x->parent->right) {
        x->parent->right = y;
    } else {
        x->parent->left = y;
    }
    y->right = x;
    x->parent = y;
}

// 插入节点操作
void insert(struct RedBlackTree* rbt, int key) {
    struct Node* node = create_node(key);
    struct Node* y = rbt->nil;
    struct Node* x = rbt->root;
    while (x != rbt->nil) {
        y = x;
        if (node->key < x->key) {
            x = x->left;
        } else {
            x = x->right;
        }
    }
    node->parent = y;
    if (y == rbt->nil) {
        rbt->root = node;
    } else if (node->key < y->key) {
        y->left = node;
    } else {
        y->right = node;
    }
    node->left = rbt->nil;
    node->right = rbt->nil;
    node->color = 1;
    fix_insert(rbt, node);
}

// 插入后调整操作
void fix_insert(struct RedBlackTree* rbt, struct Node* node) {
    while (node->parent->color == 1) {
        if (node->parent == node->parent->parent->left) {
            struct 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(rbt, node);
                }
                node->parent->color = 0;
                node->parent->parent->color = 1;
                right_rotate(rbt, node->parent->parent);
            }
        } else {
            struct 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(rbt, node);
                }
                node->parent->color = 0;
                node->parent->parent->color = 1;
                left_rotate(rbt, node->parent->parent);
            }
        }
        if (node == rbt->root) {
            break;
        }
    }
    rbt->root->color = 0;
}

// 中序遍历红黑树
void inorder_traversal(struct RedBlackTree* rbt, struct Node* node) {
    if (node != rbt->nil) {
        inorder_traversal(rbt, node->left);
        printf("%d ", node->key);
        inorder_traversal(rbt, node->right);
    }
}

// 测试
int main() {
    struct RedBlackTree rbt;
    initialize(&rbt);
    insert(&rbt, 10);
    insert(&rbt, 20);
    insert(&rbt, 30);
    insert(&rbt, 100);
    insert(&rbt, 90);
    insert(&rbt, 40);
    printf("红黑树中序遍历结果：");
    inorder_traversal(&rbt, rbt.root);
    return 0;
}

希望这份代码对你有帮助