面试题：C语言优化红黑树删除操作的内存管理

优化思路

内存池：预先分配一块较大的内存空间作为内存池，从这个内存池中分配和回收节点内存。这样可以减少频繁的系统级内存分配和释放操作，从而提高效率并减少内存碎片。
标记清除算法：在删除节点时，不立即释放内存，而是标记该节点为可回收。当内存使用达到一定阈值或者程序空闲时，统一遍历所有标记的节点并释放内存。这种方法可以减少内存分配和释放的频率，降低产生内存碎片的可能性。
合并相邻空闲块：如果使用链表式的内存管理方式，在释放节点内存时，检查相邻的内存块是否也处于空闲状态，如果是，则将它们合并成一个更大的空闲块，减少内存碎片。

代码示例

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

// 定义红黑树节点结构
typedef enum { RED, BLACK } Color;
typedef struct Node {
    int key;
    Color color;
    struct Node *left, *right, *parent;
} Node;

// 内存池相关定义
#define POOL_SIZE 1000
Node memoryPool[POOL_SIZE];
int poolIndex = 0;

// 从内存池分配节点
Node* allocateNode() {
    if (poolIndex >= POOL_SIZE) {
        fprintf(stderr, "内存池耗尽\n");
        exit(1);
    }
    return &memoryPool[poolIndex++];
}

// 标记清除相关定义
#define MAX_MARKED_NODES 100
Node* markedNodes[MAX_MARKED_NODES];
int markedCount = 0;

// 标记节点为可回收
void markNodeForDeletion(Node* node) {
    if (markedCount >= MAX_MARKED_NODES) {
        fprintf(stderr, "标记节点数组已满，考虑增加大小\n");
        exit(1);
    }
    markedNodes[markedCount++] = node;
}

// 清除标记的节点
void clearMarkedNodes() {
    for (int i = 0; i < markedCount; i++) {
        // 重置节点状态以便下次复用
        markedNodes[i]->left = markedNodes[i]->right = markedNodes[i]->parent = NULL;
        markedNodes[i]->color = RED;
    }
    markedCount = 0;
}

// 左旋操作
void leftRotate(Node** root, 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) {
        *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(Node** root, 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) {
        *root = x;
    } else if (y == y->parent->right) {
        y->parent->right = x;
    } else {
        y->parent->left = x;
    }
    x->right = y;
    y->parent = x;
}

// 插入修复红黑树性质
void insertFixup(Node** root, Node* z) {
    while (z != *root && z->parent->color == RED) {
        if (z->parent == z->parent->parent->left) {
            Node* 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(root, z);
                }
                z->parent->color = BLACK;
                z->parent->parent->color = RED;
                rightRotate(root, z->parent->parent);
            }
        } else {
            Node* 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(root, z);
                }
                z->parent->color = BLACK;
                z->parent->parent->color = RED;
                leftRotate(root, z->parent->parent);
            }
        }
    }
    (*root)->color = BLACK;
}

// 插入节点
void insert(Node** root, int key) {
    Node* z = allocateNode();
    z->key = key;
    z->left = z->right = z->parent = NULL;
    z->color = RED;
    Node* y = NULL;
    Node* x = *root;
    while (x != NULL) {
        y = x;
        if (z->key < x->key) {
            x = x->left;
        } else {
            x = x->right;
        }
    }
    z->parent = y;
    if (y == NULL) {
        *root = z;
    } else if (z->key < y->key) {
        y->left = z;
    } else {
        y->right = z;
    }
    insertFixup(root, z);
}

// 移植节点
void transplant(Node** root, Node* u, Node* v) {
    if (u->parent == NULL) {
        *root = v;
    } else if (u == u->parent->left) {
        u->parent->left = v;
    } else {
        u->parent->right = v;
    }
    if (v != NULL) {
        v->parent = u->parent;
    }
}

// 删除修复红黑树性质
void deleteFixup(Node** root, Node* x) {
    while (x != *root && (x == NULL || x->color == BLACK)) {
        if (x == x->parent->left) {
            Node* w = x->parent->right;
            if (w->color == RED) {
                w->color = BLACK;
                x->parent->color = RED;
                leftRotate(root, 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(root, w);
                    w = x->parent->right;
                }
                w->color = x->parent->color;
                x->parent->color = BLACK;
                w->right->color = BLACK;
                leftRotate(root, x->parent);
                x = *root;
            }
        } else {
            Node* w = x->parent->left;
            if (w->color == RED) {
                w->color = BLACK;
                x->parent->color = RED;
                rightRotate(root, 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(root, w);
                    w = x->parent->left;
                }
                w->color = x->parent->color;
                x->parent->color = BLACK;
                w->left->color = BLACK;
                rightRotate(root, x->parent);
                x = *root;
            }
        }
    }
    if (x != NULL) {
        x->color = BLACK;
    }
}

// 删除节点
void deleteNode(Node** root, int key) {
    Node* z = *root;
    while (z != NULL && z->key != key) {
        if (key < z->key) {
            z = z->left;
        } else {
            z = z->right;
        }
    }
    if (z == NULL) {
        return;
    }
    Node* y = z;
    Color y_original_color = y->color;
    Node* x;
    if (z->left == NULL) {
        x = z->right;
        transplant(root, z, z->right);
    } else if (z->right == NULL) {
        x = z->left;
        transplant(root, z, z->left);
    } else {
        y = z->right;
        while (y->left != NULL) {
            y = y->left;
        }
        y_original_color = y->color;
        x = y->right;
        if (y->parent == z) {
            if (x != NULL) {
                x->parent = y;
            }
        } else {
            transplant(root, y, y->right);
            y->right = z->right;
            y->right->parent = y;
        }
        transplant(root, z, y);
        y->left = z->left;
        y->left->parent = y;
        y->color = z->color;
    }
    if (y_original_color == BLACK) {
        deleteFixup(root, x);
    }
    markNodeForDeletion(z);
}

// 打印红黑树（简单的中序遍历示例）
void inorderTraversal(Node* root) {
    if (root != NULL) {
        inorderTraversal(root->left);
        printf("%d(%s) ", root->key, root->color == RED? "R" : "B");
        inorderTraversal(root->right);
    }
}

int main() {
    Node* root = NULL;
    insert(&root, 5);
    insert(&root, 3);
    insert(&root, 8);
    insert(&root, 2);
    insert(&root, 4);
    insert(&root, 7);
    insert(&root, 9);

    printf("插入后的红黑树: ");
    inorderTraversal(root);
    printf("\n");

    deleteNode(&root, 5);
    printf("删除5后的红黑树: ");
    inorderTraversal(root);
    printf("\n");

    clearMarkedNodes();
    return 0;
}

在上述代码中：

内存池：通过memoryPool数组和poolIndex实现，allocateNode函数从内存池中分配节点。
标记清除：使用markedNodes数组和markedCount来标记可回收节点，markNodeForDeletion函数标记节点，clearMarkedNodes函数统一处理回收。
删除操作：deleteNode函数在删除节点后，将节点标记为可回收，然后调用deleteFixup修复红黑树性质，确保红黑树的正确性。同时，通过transplant函数正确处理节点的左右子树。

星途面试题库

面试题：C语言优化红黑树删除操作的内存管理

知识考点

面试题答案

优化思路

代码示例