MK
摩柯社区 - 一个极简的技术知识社区
AI 面试

C 语言实现红黑树深入讲解

2022-06-212.2k 阅读

红黑树简介

红黑树（Red - Black Tree）是一种自平衡的二叉查找树，它在计算机科学中广泛应用于实现高效的关联数组（如 C++ 中的 std::map 和 std::unordered_map）、数据库索引等场景。红黑树的每个节点都带有一个额外的颜色属性，要么是红色，要么是黑色，通过一系列规则来保持树的平衡。

红黑树具有以下几个重要特性：

  1. 节点颜色属性：每个节点要么是红色，要么是黑色。
  2. 根节点属性：根节点是黑色。
  3. 叶节点属性：每个叶节点（NIL 节点，在实际代码实现中通常是一个表示空节点的指针）是黑色。
  4. 红色节点限制：如果一个节点是红色的，那么它的两个子节点都是黑色的。这确保了从根到叶的任何路径上不会有两个连续的红色节点。
  5. 黑色高度一致性：从任意节点到其每个叶节点的所有路径都包含相同数目的黑色节点。这个属性保证了树的大致平衡。

C 语言实现红黑树的基本结构

在 C 语言中，我们首先需要定义红黑树的节点结构。由于红黑树是一种二叉树，每个节点会包含数据、颜色、左子节点指针、右子节点指针以及父节点指针。

// 定义红黑树节点颜色
typedef enum {
    RED,
    BLACK
} Color;

// 定义红黑树节点结构
typedef struct RBNode {
    int key;          // 节点数据
    Color color;      // 节点颜色
    struct RBNode *left;
    struct RBNode *right;
    struct RBNode *parent;
} RBNode;

// 定义红黑树结构
typedef struct RedBlackTree {
    RBNode *root;
} RedBlackTree;

在上述代码中，我们定义了一个枚举类型 Color 来表示节点的颜色，RED 代表红色，BLACK 代表黑色。RBNode 结构体表示红黑树的节点，包含了节点的数据 key、颜色 color 以及指向左右子节点和父节点的指针。RedBlackTree 结构体则是整个红黑树的表示，它只包含一个指向根节点的指针 root。

红黑树的旋转操作

红黑树通过旋转操作来调整树的结构，以维护其平衡特性。旋转分为左旋和右旋两种。

左旋操作

左旋操作是将一个节点的右子节点提升为父节点，并将原父节点变为新父节点的左子节点。

// 左旋操作
void leftRotate(RedBlackTree *tree, RBNode *x) {
    RBNode *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;
}

在 leftRotate 函数中，首先保存 x 的右子节点 y。然后将 y 的左子节点（如果存在）变为 x 的右子节点，并更新其 parent 指针。接着更新 y 的 parent 指针，并根据 x 在其父节点中的位置（左子节点还是右子节点），调整父节点与 y 的连接。最后将 x 变为 y 的左子节点，并更新 x 的 parent 指针。

右旋操作

右旋操作与左旋操作相反，它将一个节点的左子节点提升为父节点，并将原父节点变为新父节点的右子节点。

// 右旋操作
void rightRotate(RedBlackTree *tree, RBNode *y) {
    RBNode *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->right) {
        y->parent->right = x;
    } else {
        y->parent->left = x;
    }
    x->right = y;
    y->parent = x;
}

右旋操作的 rightRotate 函数逻辑与左旋类似，只是左右指针的操作方向相反。它先保存 y 的左子节点 x，然后调整子节点与父节点的连接关系，最后完成旋转。

红黑树的插入操作

红黑树的插入操作首先遵循二叉查找树的插入规则，找到合适的位置插入新节点。然后通过一系列颜色调整和旋转操作，使树重新满足红黑树的特性。

// 插入操作
void insert(RedBlackTree *tree, int key) {
    RBNode *z = (RBNode *)malloc(sizeof(RBNode));
    z->key = key;
    z->color = RED;
    z->left = NULL;
    z->right = NULL;
    z->parent = NULL;

    RBNode *y = NULL;
    RBNode *x = tree->root;
    while (x != NULL) {
        y = x;
        if (z->key < x->key) {
            x = x->left;
        } else {
            x = x->right;
        }
    }
    z->parent = y;
    if (y == NULL) {
        tree->root = z;
    } else if (z->key < y->key) {
        y->left = z;
    } else {
        y->right = z;
    }

    while (z != tree->root && z->parent->color == RED) {
        if (z->parent == z->parent->parent->left) {
            RBNode *y = z->parent->parent->right;
            if (y != NULL && 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 {
            RBNode *y = z->parent->parent->left;
            if (y != NULL && y->color == RED) {
                z->parent->color = BLACK;
                y->color = BLACK;
                z->parent->parent->color = RED;
                z = z->parent->parent;
            } else {
                if (z == z->parent->left) {
                    z = z->parent;
                    rightRotate(tree, z);
                }
                z->parent->color = BLACK;
                z->parent->parent->color = RED;
                leftRotate(tree, z->parent->parent);
            }
        }
    }
    tree->root->color = BLACK;
}

在 insert 函数中，首先创建一个新节点 z，并初始化为红色。然后通过二叉查找树的插入逻辑，找到插入位置并连接新节点。接着，通过一个 while 循环来调整颜色和进行旋转操作，以保证红黑树的特性。在循环中，根据 z 及其父节点、叔父节点的颜色和位置关系，进行不同的处理。如果叔父节点是红色，则通过重新着色来保持黑色高度一致；如果叔父节点是黑色，则通过旋转和重新着色来恢复平衡。最后，确保根节点为黑色。

红黑树的删除操作

红黑树的删除操作比插入操作更为复杂。它同样先按照二叉查找树的删除规则删除节点，然后通过一系列调整操作来维护红黑树的特性。

// 找到节点的后继节点
RBNode *successor(RedBlackTree *tree, RBNode *node) {
    if (node->right != NULL) {
        RBNode *current = node->right;
        while (current->left != NULL) {
            current = current->left;
        }
        return current;
    } else {
        RBNode *current = node->parent;
        while (current != NULL && node == current->right) {
            node = current;
            current = current->parent;
        }
        return current;
    }
}

// 删除操作
void delete(RedBlackTree *tree, int key) {
    RBNode *z = tree->root;
    while (z != NULL && z->key != key) {
        if (key < z->key) {
            z = z->left;
        } else {
            z = z->right;
        }
    }
    if (z == NULL) {
        return;
    }

    RBNode *y = z;
    Color y_original_color = y->color;
    RBNode *x;
    if (z->left == NULL) {
        x = z->right;
        transplant(tree, z, z->right);
    } else if (z->right == NULL) {
        x = z->left;
        transplant(tree, z, z->left);
    } else {
        y = successor(tree, z);
        y_original_color = y->color;
        x = y->right;
        if (y->parent == z) {
            if (x != NULL) {
                x->parent = y;
            }
        } else {
            transplant(tree, y, y->right);
            y->right = z->right;
            y->right->parent = y;
        }
        transplant(tree, z, y);
        y->left = z->left;
        y->left->parent = y;
        y->color = z->color;
    }
    if (y_original_color == BLACK) {
        while (x != tree->root && (x == NULL || x->color == BLACK)) {
            if (x == x->parent->left) {
                RBNode *w = x->parent->right;
                if (w->color == RED) {
                    w->color = BLACK;
                    x->parent->color = RED;
                    leftRotate(tree, x->parent);
                    w = x->parent->right;
                }
                if ((w->left == NULL || w->left->color == BLACK) &&
                    (w->right == NULL || w->right->color == BLACK)) {
                    w->color = RED;
                    x = x->parent;
                } else {
                    if (w->right == NULL || w->right->color == BLACK) {
                        w->left->color = BLACK;
                        w->color = RED;
                        rightRotate(tree, w);
                        w = x->parent->right;
                    }
                    w->color = x->parent->color;
                    x->parent->color = BLACK;
                    w->right->color = BLACK;
                    leftRotate(tree, x->parent);
                    x = tree->root;
                }
            } else {
                RBNode *w = x->parent->left;
                if (w->color == RED) {
                    w->color = BLACK;
                    x->parent->color = RED;
                    rightRotate(tree, x->parent);
                    w = x->parent->left;
                }
                if ((w->right == NULL || w->right->color == BLACK) &&
                    (w->left == NULL || w->left->color == BLACK)) {
                    w->color = RED;
                    x = x->parent;
                } else {
                    if (w->left == NULL || w->left->color == BLACK) {
                        w->right->color = BLACK;
                        w->color = RED;
                        leftRotate(tree, w);
                        w = x->parent->left;
                    }
                    w->color = x->parent->color;
                    x->parent->color = BLACK;
                    w->left->color = BLACK;
                    rightRotate(tree, x->parent);
                    x = tree->root;
                }
            }
        }
        if (x != NULL) {
            x->color = BLACK;
        }
    }
}

// 节点替换操作
void transplant(RedBlackTree *tree, RBNode *u, RBNode *v) {
    if (u->parent == NULL) {
        tree->root = v;
    } else if (u == u->parent->left) {
        u->parent->left = v;
    } else {
        u->parent->right = v;
    }
    if (v != NULL) {
        v->parent = u->parent;
    }
}

在 delete 函数中，首先找到要删除的节点 z。然后根据 z 的子节点情况进行不同处理。如果 z 只有一个子节点，直接用子节点替换 z；如果 z 有两个子节点，则找到 z 的后继节点 y，用 y 替换 z，并调整 y 的子节点连接。接着，根据被删除节点 y 的原始颜色（如果是黑色），通过一个复杂的 while 循环来调整树的结构和颜色，以维护红黑树的特性。在循环中，根据 x（y 被删除后其位置的替代节点）及其兄弟节点 w 的颜色和子节点情况，进行不同的旋转和颜色调整操作。transplant 函数用于在树中替换节点，它调整节点的父子关系。

红黑树的遍历操作

红黑树作为二叉树的一种，常见的遍历方式有前序遍历、中序遍历和后序遍历。这里以中序遍历为例，展示如何遍历红黑树。

// 中序遍历
void inorderTraversal(RBNode *node) {
    if (node != NULL) {
        inorderTraversal(node->left);
        printf("%d ", node->key);
        inorderTraversal(node->right);
    }
}

inorderTraversal 函数通过递归的方式实现中序遍历。它先访问左子树，然后输出当前节点的数据，最后访问右子树。这样可以按照从小到大的顺序输出红黑树中的所有节点数据。

红黑树的应用场景

  1. 关联数组实现：许多编程语言的标准库中的关联数组（如 C++ 的 std::map）就是基于红黑树实现的。红黑树能够提供高效的插入、删除和查找操作，平均时间复杂度为 O(log n)，其中 n 是树中节点的数量。这使得关联数组能够快速地根据键值查找对应的值。
  2. 数据库索引：在数据库系统中，红黑树可用于实现索引结构。通过将数据库记录的某个字段作为键值构建红黑树，数据库系统可以快速定位到满足特定条件的记录，提高查询效率。例如，在关系型数据库中，对某一列建立索引后，查询该列满足特定值的记录时，红黑树结构的索引能够快速缩小查找范围。
  3. 内存管理：在一些内存管理系统中，红黑树可以用于管理内存块。通过将内存块的地址或大小等属性作为键值存储在红黑树中，内存管理系统可以高效地分配、释放内存块，并且能够快速找到合适大小的内存块来满足分配请求。

总结红黑树在 C 语言中的实现要点

在 C 语言中实现红黑树，需要深刻理解其原理和特性。从基本的节点结构定义，到旋转、插入、删除和遍历等操作的实现，每个环节都紧密相连，共同维护红黑树的平衡和正确性。

旋转操作是保持红黑树平衡的关键，左旋和右旋操作通过巧妙地调整节点间的指针关系，改变树的结构。插入和删除操作则是在遵循二叉查找树基本规则的基础上，通过复杂的颜色调整和旋转操作，使树重新满足红黑树的特性。遍历操作则是红黑树数据访问的重要手段，不同的遍历方式适用于不同的应用场景。

红黑树在计算机科学中具有广泛的应用，其高效的操作性能和自平衡特性使其成为解决许多实际问题的有力工具。通过深入学习和实践 C 语言实现红黑树，能够更好地理解数据结构和算法的设计与优化，为进一步的编程工作打下坚实的基础。

希望通过本文对 C 语言实现红黑树的深入讲解，读者能够对红黑树有更全面、深入的认识，并能够熟练地运用红黑树解决实际编程中的问题。在实际应用中，可以根据具体需求对红黑树的实现进行进一步优化和扩展，以满足不同场景的性能要求。同时，红黑树的实现也为学习其他更复杂的数据结构和算法提供了良好的基础和借鉴。