基本数据结构--平衡二叉搜索树之红黑树示例代码

红黑树的规则。红黑树的每个节点有颜色（红或黑），满足以下性质：

1. 每个节点是红或黑。
2. 根节点是黑的。
3. 叶子节点（NIL节点）是黑的。
4. 红节点的子节点必须是黑的。
5. 从任一节点到其所有后代叶子节点的路径包含相同数量的黑节点。

#include <stdlib.h>typedef enum { RED, BLACK } Color;typedef struct RBNode {void *data;Color color;struct RBNode *left, *right, *parent;
} RBNode;typedef struct {RBNode *root;int (*compare)(const void*, const void*);void (*data_free)(void*); // 必须由用户初始化 
} RBTree;// 创建新节点（默认红色）
RBNode* create_node(void *data) {RBNode* node = (RBNode*)malloc(sizeof(RBNode));node->data = data;node->color = RED;node->left = node->right = node->parent = NULL;return node;
}// 左旋操作 
void left_rotate(RBTree *t, RBNode *x) {RBNode *y = x->right;x->right = y->left;if (y->left) y->left->parent = x;y->parent = x->parent;if (!x->parent)t->root = y;else if (x == x->parent->left)x->parent->left = y;else x->parent->right = y;y->left = x;x->parent = y;
}// 右旋操作 
void right_rotate(RBTree *t, RBNode *x) {RBNode *y = x->left;x->left = y->right;if (y->right)y->right->parent = x;y->parent = x->parent;if (!x->parent)t->root = y;else if (x == x->parent->left)x->parent->left = y;else x->parent->right = y;y->right = x;x->parent = y;
}// 插入修复 
void insert_fixup(RBTree *t, RBNode *z) {while (z->parent && z->parent->color == RED) {RBNode *parent = z->parent;RBNode *grandparent = parent->parent; if (parent == grandparent->left) {RBNode *uncle = grandparent->right;if (uncle && uncle->color == RED) {// Case 1: uncle存在且为红色 parent->color = BLACK;uncle->color = BLACK;grandparent->color = RED;z = grandparent;} else {// Case 2/3: uncle为黑色或不存在 if (z == parent->right) {z = parent;left_rotate(t, z);parent = z->parent;}// Case 3 parent->color = BLACK;grandparent->color = RED;right_rotate(t, grandparent);}} else {RBNode *uncle = grandparent->left;if (uncle && uncle->color == RED) {parent->color = BLACK;uncle->color = BLACK;grandparent->color = RED;z = grandparent;} else {if (z == parent->left) {z = parent;right_rotate(t, z);parent = z->parent;}parent->color = BLACK;grandparent->color = RED;left_rotate(t, grandparent);}}}t->root->color = BLACK;
}// 公共插入接口 
void rb_insert(RBTree *t, void *data) {RBNode *z = create_node(data);RBNode *y = NULL, *x = t->root;while (x) {y = x;int cmp = t->compare(z->data, x->data);if (cmp < 0)x = x->left;else x = x->right;}z->parent = y;if (!y)t->root = z;else if (t->compare(z->data, y->data) < 0)y->left = z;else y->right = z;insert_fixup(t, z);
}// 删除修复 
void delete_fixup(RBTree *t, RBNode *x) {while (x != t->root && (x == NULL || x->color == BLACK)) {if (x == x->parent->left) {RBNode *w = x->parent->right;if (w->color == RED) {// Case 1: 兄弟是红色 w->color = BLACK;x->parent->color = RED;left_rotate(t, x->parent);w = x->parent->right;}if ((w->left == NULL || w->left->color == BLACK) &&(w->right == NULL || w->right->color == BLACK)) {// Case 2: 兄弟的两个孩子都是黑色 w->color = RED;x = x->parent;} else {if (w->right == NULL || w->right->color == BLACK) {// Case 3: 兄弟左孩子红，右孩子黑 if (w->left) w->left->color = BLACK;w->color = RED;right_rotate(t, w);w = x->parent->right;}// Case 4: 兄弟右孩子红 w->color = x->parent->color;x->parent->color = BLACK;if (w->right) w->right->color = BLACK;left_rotate(t, x->parent);x = t->root; // 终止循环 }} else {// 对称处理右侧情况 RBNode *w = x->parent->left;if (w->color == RED) {// Case 1镜像 w->color = BLACK;x->parent->color = RED;right_rotate(t, x->parent);w = x->parent->left;}if ((w->right == NULL || w->right->color == BLACK) &&(w->left == NULL || w->left->color == BLACK)) {// Case 2镜像 w->color = RED;x = x->parent;} else {if (w->left == NULL || w->left->color == BLACK) {// Case 3镜像 if (w->right) w->right->color = BLACK;w->color = RED;left_rotate(t, w);w = x->parent->left;}// Case 4镜像 w->color = x->parent->color;x->parent->color = BLACK;if (w->left) w->left->color = BLACK;right_rotate(t, x->parent);x = t->root;}}}if (x) x->color = BLACK;
}
// 公共删除接口 
void rb_delete(RBTree *t, void *data) {RBNode *z = find_node(t, data);if (!z) return;RBNode *y = z, *x;Color original_color = y->color;if (!z->left) {x = z->right;transplant(t, z, z->right);} else if (!z->right) {x = z->left;transplant(t, z, z->left);} else {y = z->right;while (y->left) y = y->left;original_color = y->color;x = y->right;if (y->parent == z) {if (x) x->parent = y;} else {transplant(t, y, y->right);y->right = z->right;y->right->parent = y;}transplant(t, z, y);y->left = z->left;y->left->parent = y;y->color = z->color;}if (original_color == BLACK)delete_fixup(t, x);free(z);
}// 节点替换辅助函数 
void transplant(RBTree *t, RBNode *u, RBNode *v) {if (!u->parent)t->root = v;else if (u == u->parent->left)u->parent->left = v;else u->parent->right = v;if (v)v->parent = u->parent;
}/* 遍历函数（与AVL树实现相同） */
void pre_order(RBNode *root, void (*callback)(void*)) {if (root) {callback(root->data);pre_order(root->left, callback);pre_order(root->right, callback);}
}

 //递归形式实现的销毁树函数

/* 递归释放子树（内部函数）*/
static void _destroy_subtree(RBTree *t, RBNode *node) {if (!node) return;// 后序遍历释放子节点 _destroy_subtree(t, node->left);_destroy_subtree(t, node->right);// 释放数据内容 if (t->data_free) {t->data_free(node->data);  // 用户自定义释放函数 }// 释放节点本身 free(node);
}/* 公开的销毁函数 */
void rb_destroy(RBTree *t) {if (!t) return;_destroy_subtree(t, t->root);t->root = NULL;  // 重要！防止悬空指针 // 可选：重置比较函数指针 // t->compare = NULL;
}

 //为避免栈溢出，迭代式实现

/* 内部节点释放函数 */
static void _free_node(RBTree *t, RBNode *node) {if (!node) return;// 解除节点间的关联 node->left = node->right = node->parent = NULL;// 释放数据内容 if (t->data_free) {t->data_free(node->data);}// 释放节点内存 free(node);
}/* 改进后的迭代销毁实现 */
void rb_destroy(RBTree *t) {if (!t || !t->root) return;RBNode *current = t->root;while (current) {if (!current->left) {// 无左子树，直接处理右子树 RBNode *right = current->right;_free_node(t, current);current = right;} else {// 找到左子树的最右节点 RBNode *pre = current->left;while (pre->right && pre->right != current) {pre = pre->right;}if (!pre->right) {// 建立临时链接用于回溯 pre->right = current;current = current->left;} else {// 断开临时链接并处理节点 pre->right = NULL;RBNode *temp = current;current = current->right;_free_node(t, temp);}}}t->root = NULL;
}

/* 示例使用 */
#include<stdio.h>
int int_compare(const void* a, const void* b) {return *(int*)a - *(int*)b;
}void print_int(void* data) {printf("%d ", *(int*)data);
}int main() {RBTree tree = {NULL, int_compare,free};// 插入测试 int nums[] = {7, 3, 18, 10, 22, 8, 11, 26};for (int i = 0; i < sizeof(nums)/sizeof(nums[0]); i++) {int* data = malloc(sizeof(int));*data = nums[i];rb_insert(&tree, data);}printf("Pre-order traversal:\n");pre_order(tree.root,  print_int); // 输出：10 7 3 8 22 18 11 26 printf("\n");// 删除测试 int to_delete = 18;rb_delete(&tree, &to_delete);printf("\nAfter deletion of 18:\n");pre_order(tree.root,  print_int); // 输出：10 7 3 8 22 11 26 printf("\n");rb_destroy(tree);return 0;
}