C语言中如何实现红黑树 C语言平衡二叉树插入删除操作-C#.Net教程-PHP中文网

C语言中如何实现红黑树 C语言平衡二叉树插入删除操作

冰火之心

发布： 2025-07-22 12:17:01

原创

1020人浏览过

红黑树的实现核心在于通过颜色属性和旋转操作维持平衡。用c语言实现红黑树的插入操作时，首先按照二叉搜索树的方式插入节点并将其着色为红色，然后根据父节点和叔叔节点的颜色判断情况并修复：1. 父节点是黑色则无需操作；2. 父节点和叔叔节点均为红色时需变色并向上继续修复；3. 叔叔节点为黑色且新节点是父节点的右孩子时先左旋转化为情况4；4. 叔叔节点为黑色且新节点是父节点的左孩子时变色并右旋。删除操作同样先按二叉搜索树方式执行，若删除的是黑色节点则需修复，修复涉及兄弟节点颜色及子节点颜色等多种情况，并通过旋转和变色将“缺少一个黑色”问题向上传递直至解决。与avl树相比，红黑树使用颜色而非高度差维持平衡，允许一定程度不平衡，因此插入删除时旋转次数更少、性能更优，但实现逻辑更复杂，适用于频繁插入删除的场景。

C语言中如何实现红黑树 C语言平衡二叉树插入删除操作

红黑树的实现，本质上是在二叉搜索树的基础上，通过颜色属性和旋转操作来维持树的平衡。C语言实现红黑树，重点在于理解红黑树的性质，并将其转化为代码逻辑。平衡二叉树的插入删除操作，同样依赖于旋转和调整，但具体策略与红黑树有所不同。

解决方案

C语言实现红黑树，需要定义节点结构体，包含颜色信息、键值对以及指向父节点、左右子节点的指针。插入和删除操作是核心，需要维护红黑树的五个性质：

每个节点要么是红色，要么是黑色。
根节点是黑色。
所有叶子节点（NIL节点，空节点）是黑色。
如果一个节点是红色，那么它的两个子节点都是黑色。（反之不一定成立）
从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。

插入操作：先按照二叉搜索树的方式插入新节点，颜色设为红色。然后，通过旋转和重新着色来修复红黑树的性质。修复过程需要考虑多种情况，例如父节点是红色，叔叔节点是红色或黑色等。

立即学习“C语言免费学习笔记（深入）”；

删除操作：先按照二叉搜索树的方式删除节点。如果删除的是黑色节点，可能会破坏红黑树的性质，需要通过旋转和重新着色来修复。修复过程比插入更复杂，需要考虑更多的情况。

以下是一个简化的节点结构体定义：

typedef struct RBNode {
    int key;
    int color; // 0: Black, 1: Red
    struct RBNode *parent, *left, *right;
} RBNode;

登录后复制

具体实现时，需要编写插入、删除、左旋、右旋、着色等函数。

如何用C语言实现红黑树的插入操作？

插入操作的核心在于，先像普通二叉搜索树一样插入节点，然后将新节点着色为红色。因为红色节点对黑高影响最小。插入后，可能会违反红黑树的性质，所以需要进行修复。修复过程通常涉及到以下几种情况：

情况1： 新节点的父节点是黑色，不需要任何操作。
情况2： 新节点的父节点是红色，叔叔节点也是红色。此时，将父节点和叔叔节点都着色为黑色，祖父节点着色为红色，然后将祖父节点作为新的当前节点，继续向上修复。
情况3： 新节点的父节点是红色，叔叔节点是黑色或 NIL 节点，且新节点是父节点的右孩子（或左孩子）。此时，需要进行左旋（或右旋），将情况转化为情况4。
情况4： 新节点的父节点是红色，叔叔节点是黑色或 NIL 节点，且新节点是父节点的左孩子（或右孩子）。此时，将父节点着色为黑色，祖父节点着色为红色，然后进行右旋（或左旋）。

代码示例（简化版，未包含所有边界条件）：

云雀语言模型

云雀是一款由字节跳动研发的语言模型，通过便捷的自然语言交互，能够高效的完成互动对话

查看详情

void insert_fixup(RBNode *root, RBNode *node) {
    while (node->parent != NULL && node->parent->color == 1) { // 父节点是红色
        if (node->parent == node->parent->parent->left) { // 父节点是祖父节点的左孩子
            RBNode *uncle = node->parent->parent->right;
            if (uncle != NULL && uncle->color == 1) { // 叔叔节点是红色
                node->parent->color = 0;
                uncle->color = 0;
                node->parent->parent->color = 1;
                node = node->parent->parent;
            } else { // 叔叔节点是黑色或 NIL
                if (node == node->parent->right) {
                    node = node->parent;
                    left_rotate(root, node);
                }
                node->parent->color = 0;
                node->parent->parent->color = 1;
                right_rotate(root, node->parent->parent);
            }
        } // else 对称情况，省略
    }
    root->color = 0; // 根节点必须是黑色
}

登录后复制