红黑树

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

性质：

每个节点要么是红色，要么是黑色。
根节点是黑色的。
每个叶子节点（NIL节点，空节点）是黑色的。
如果一个节点是红色的，则它的子节点必须是黑色的。
从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
这些性质保证了红黑树是平衡的，最长路径不会超过最短路径的两倍，因此在最坏情况下，红黑树的查找、插入和删除操作的时间复杂度都是O(log n)。

在C语言中实现红黑树，通常会定义节点结构体如下：

struct Node {
    int data;
    struct Node *parent;
    struct Node *left;
    struct Node *right;
    int color;  // 0代表红色，1代表黑色
};

然后实现红黑树的插入、删除、旋转等操作，确保在每次操作后保持红黑树的性质。

红黑树在很多编程语言的标准库中都有应用，用于实现映射（Map）和集合（Set）等数据结构，因为它能够在保持平衡的同时提供较高的查找、插入和删除效率。