红黑树的C语言简单实现与代码解析

红黑树 C 语言的简单实现与代码解析

红黑树是计算机科学中一种重要的自平衡二叉搜索树。它确保了在最坏情况下，基本的动态集合操作（如插入、删除和查找）具有对数时间复杂度。在这篇博客中，我们将介绍一个简化的C语言红黑树实现，并对代码进行详细解析。

1、示例代码

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

typedef enum { RED, BLACK } color_t;

typedef struct Node {
    int data;
    color_t color;
    struct Node *left, *right, *parent;
} Node;

typedef struct RedBlackTree {
    Node *root;
} RedBlackTree;

// 创建新节点
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->left = newNode->right = newNode->parent = NULL;
    newNode->color = RED;  // 默认为红色
    return newNode;
}

// 左旋
void leftRotate(RedBlackTree* tree, Node* x) {
    Node* y = x->right;
    x->right = y->left;
    if (y->left != NULL) y->left->parent = x;
    y->parent = x->parent;
    if (x->parent == NULL) tree->root = y;
    else if (x == x->parent->left) x->parent->left = y;
    else x->parent->right = y;
    y->left = x;
    x->parent = y;
}

// 右旋
void rightRotate(RedBlackTree* tree, Node* y) {
    Node* x = y->left;
    y->left = x->right;
    if (x->right != NULL) x->right->parent = y;
    x->parent = y->parent;
    if (y->parent == NULL) tree->root = x;
    else if (y == y->parent->left) y->parent->left = x;
    else y->parent->right = x;
    x->right = y;
    y->parent = x;
}

// 插入修复操作
void insertFixup(RedBlackTree* tree, Node* z) {
    while (z->parent && z->parent->color == RED) {
        if (z->parent == z->parent->parent->left) {
            Node* y = z->parent->parent->right;
            if (y && y->color == RED) {
                z->parent->color = BLACK;
                y->color = BLACK;
                z->parent->parent->color = RED;
                z = z->parent->parent;
            } else {
                if (z == z->parent->right) {
                    z = z->parent;
                    leftRotate(tree, z);
                }
                z->parent->color = BLACK;
                z->parent->parent->color = RED;
                rightRotate(tree, z->parent->parent);
            }
        } else {
            // 类似地处理右侧情况
            // ...
        }
    }
    tree->root->color = BLACK;
}

// 插入节点
void insert(RedBlackTree* tree, int data) {
    Node* z = createNode(data);
    Node* y = NULL;
    Node* x = tree->root;

    while (x != NULL) {
        y = x;
        if (z->data < x->data) x = x->left;
        else x = x->right;
    }

    z->parent = y;
    if (y == NULL) tree->root = z;
    else if (z->data < y->data) y->left = z;
    else y->right = z;

    insertFixup(tree, z);
}

// 其他操作（如删除、查找等）可以根据上述模式扩展

int main() {
    RedBlackTree tree = {NULL};
    int arr[] = {7, 3, 18, 10, 22, 8, 11, 26, 2, 6, 13};
    int n = sizeof(arr) / sizeof(arr[0]);
    for (int i = 0; i < n; i++) {
        insert(&tree, arr[i]);
    }
    // 执行其他操作或打印树结构
    return 0;
}

2、代码解析

2.1. 基本结构

我们首先定义了两个基本结构：Node 和 RedBlackTree。

typedef enum { RED, BLACK } color_t;

typedef struct Node {
    int data;
    color_t color;
    struct Node *left, *right, *parent;
} Node;

typedef struct RedBlackTree {
    Node *root;
} RedBlackTree;

• Node 结构包含一个整数数据、一个颜色（红色或黑色）以及左、右子节点和父节点的指针。
• RedBlackTree 结构只包含一个根节点指针。

2.2 左旋与右旋操作

红黑树的核心操作之一是旋转，这有助于维护树的平衡性。

• leftRotate 和 rightRotate 函数分别实现了左旋和右旋操作。

2.2 1. 左旋操作

左旋操作是为了将一个节点旋转到其右子节点的位置。这个操作旨在维护红黑树的平衡性。以下是左旋操作的步骤：

1. 选择节点：假设要进行左旋的节点为 x，并且其右子节点为 y。
2. 更新子节点：将 x 的右子节点 y 的左子节点（y 的左子节点）作为 x 的新右子节点。
3. 更新父节点：如果 x 有父节点，更新其父节点以指向 y 而不是 x。
4. 更新 y 的左子节点：将 y 的左子节点设置为 x。
5. 更新 x 的父节点：将 y 的父节点设置为 x 的父节点。

2.2.2 右旋操作

右旋操作与左旋相反。它是为了将一个节点旋转到其左子节点的位置。以下是右旋操作的步骤：

右旋步骤：

1. 选择节点：假设要进行右旋的节点为 y，并且其左子节点为 x。
2. 更新子节点：将 y 的左子节点 x 的右子节点（x 的右子节点）作为 y 的新左子节点。
3. 更新父节点：如果 y 有父节点，更新其父节点以指向 x 而不是 y。
4. 更新 x 的右子节点：将 x 的右子节点设置为 y。
5. 更新 y 的父节点：将 x 的父节点设置为 y 的父节点。

3. 插入与修复操作

当向红黑树中插入新节点时，可能会破坏红黑树的性质。因此，我们需要进行修复操作。

• insertFixup 函数实现了在插入后修复红黑树的逻辑。

4. 插入操作

为了简化，我们只展示了如何向红黑树中插入新节点。其他操作（如删除、查找等）可以基于相似的原理进行扩展。

5. 示例

在主函数中，我们展示了如何使用上述功能来创建和填充一个红黑树。

int main() {
    RedBlackTree tree = {NULL};
    int arr[] = {7, 3, 18, 10, 22, 8, 11, 26, 2, 6, 13};
    int n = sizeof(arr) / sizeof(arr[0]);
    for (int i = 0; i < n; i++) {
        insert(&tree, arr[i]);
    }
    return 0;
}

3、结论

虽然上述代码提供了一个基本的红黑树实现，但实际上红黑树的设计和实现要复杂得多。在实际应用中，需要考虑许多其他细节和情况。然而，通过这个简化的示例，我们可以更好地理解红黑树的基本原理和操作。