红黑树

红黑树（Red-Black Tree）是一种自平衡的二叉搜索树，它在每个节点上增加了一个存储位来表示节点的颜色，可以是红色或黑色。红黑树的每个节点都有以下特性：

• 每个节点是红色或黑色。
• 根节点是黑色。
• 每个叶子节点（NIL节点，空节点）是黑色的。
• 如果一个节点是红色的，则它的子节点必须是黑色的。
• 从任意节点到其每个叶子节点的所有路径都包含相同数目的黑色节点。

这些规则确保了红黑树的关键特性：从根到任何节点的最长路径不会超过最短路径的两倍。这使得红黑树在插入和删除时自动保持平衡，以便始终能够保持对数时间复杂度。

以下是一个简单的C语言实现红黑树的代码：

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

typedef enum {
    RED,
    BLACK
} color;

typedef struct node {
    int value;
    color node_color;
    struct node *parent;
    struct node *left;
    struct node *right;
} node;

node *create_node(int value) {
    node *new_node = (node *)malloc(sizeof(node));
    new_node->value = value;
    new_node->node_color = RED;
    new_node->parent = NULL;
    new_node->left = NULL;
    new_node->right = NULL;
    return new_node;
}

void destroy_tree(node *root) {
    if (root == NULL) {
        return;
    }
    destroy_tree(root->left);
    destroy_tree(root->right);
    free(root);
}

int main() {
    node *root = create_node(10);
    root->node_color = BLACK;
    root->left = create_node(5);
    root->left->parent = root;
    root->right = create_node(15);
    root->right->parent = root;
    destroy_tree(root);
    return 0;
}

这个代码创建了一个红黑树，并在销毁时递归地释放了所有节点的内存。在创建时，我们使用 create_node 函数来创建节点，该函数会分配一块新的内存并返回指向该内存的指针。我们使用 destroy_tree 函数来销毁整个红黑树，该函数首先递归地销毁左子树和右子树，然后释放节点的内存。

在红黑树的实现中，我们添加了一个额外的颜色属性来表示每个节点的颜色，并使用 color 枚举类型来定义红色和黑色。我们还为每个节点添加了一个指向父节点的指针，以便在插入和删除操作中方便地进行旋转和颜色更改。