373 lines
13 KiB
C
373 lines
13 KiB
C
#include <c_RBTree.h>
|
||
|
||
/* ------------------------------------------------------------------------------------------------------------------ */
|
||
/* */
|
||
|
||
|
||
#define RB_NODE_DATA(node) ((void*)((char*)(node) + sizeof(c_RBNode_t)))
|
||
|
||
/* ------------------------------------------------------------------------------------------------------------------ */
|
||
/* */
|
||
|
||
|
||
// ==================================================================================================================
|
||
// 1. 基石级无哨兵旋转 (Rotations)
|
||
// ==================================================================================================================
|
||
|
||
C_STATIC_FORCE_INLINE
|
||
void c_RBTree_LeftRotate(c_RBTree_t* self, c_RBNode_t* x) {
|
||
c_RBNode_t* y = x->right;
|
||
x->right = y->left;
|
||
if (y->left != NULL) {
|
||
y->left->parent = x;
|
||
}
|
||
y->parent = x->parent;
|
||
if (x->parent == NULL) {
|
||
self->root = y;
|
||
} else if (x == x->parent->left) {
|
||
x->parent->left = y;
|
||
} else {
|
||
x->parent->right = y;
|
||
}
|
||
y->left = x;
|
||
x->parent = y;
|
||
}
|
||
|
||
C_STATIC_FORCE_INLINE
|
||
void c_RBTree_RightRotate(c_RBTree_t* self, c_RBNode_t* y) {
|
||
c_RBNode_t* x = y->left;
|
||
y->left = x->right;
|
||
if (x->right != NULL) {
|
||
x->right->parent = y;
|
||
}
|
||
x->parent = y->parent;
|
||
if (y->parent == NULL) {
|
||
self->root = x;
|
||
} else if (y == y->parent->right) {
|
||
y->parent->right = x;
|
||
} else {
|
||
y->parent->left = x;
|
||
}
|
||
x->right = y;
|
||
y->parent = x;
|
||
}
|
||
|
||
// ==================================================================================================================
|
||
// 2. 无哨兵插入自修复 (Insert Fixup)
|
||
// ==================================================================================================================
|
||
|
||
C_STATIC_FORCE_INLINE
|
||
void c_RBTree_InsertFixup(c_RBTree_t* self, c_RBNode_t* z) {
|
||
// 只有当 z 不是根，且其父亲是红色时（红红冲突）才需要修复
|
||
while (z != self->root && c_RBTree_GetColor(z->parent) == C_RB_RED) {
|
||
if (z->parent == z->parent->parent->left) {
|
||
c_RBNode_t* y = z->parent->parent->right; // 叔叔节点（可能为 NULL）
|
||
|
||
if (c_RBTree_GetColor(y) == C_RB_RED) {
|
||
// 情况 1: 叔叔是红的 -> 变色，指针上移
|
||
c_RBTree_SetColor(z->parent, C_RB_BLACK);
|
||
c_RBTree_SetColor(y, C_RB_BLACK);
|
||
c_RBTree_SetColor(z->parent->parent, C_RB_RED);
|
||
z = z->parent->parent;
|
||
} else {
|
||
// 情况 2: 叔叔是黑的，且 z 是右孩子 -> 先左旋转化为情况 3
|
||
if (z == z->parent->right) {
|
||
z = z->parent;
|
||
c_RBTree_LeftRotate(self, z);
|
||
}
|
||
// 情况 3: 叔叔是黑的，且 z 是左孩子 -> 变色并右旋
|
||
c_RBTree_SetColor(z->parent, C_RB_BLACK);
|
||
c_RBTree_SetColor(z->parent->parent, C_RB_RED);
|
||
c_RBTree_RightRotate(self, z->parent->parent);
|
||
}
|
||
} else {
|
||
// 镜像对称对称分支
|
||
c_RBNode_t* y = z->parent->parent->left;
|
||
if (c_RBTree_GetColor(y) == C_RB_RED) {
|
||
c_RBTree_SetColor(z->parent, C_RB_BLACK);
|
||
c_RBTree_SetColor(y, C_RB_BLACK);
|
||
c_RBTree_SetColor(z->parent->parent, C_RB_RED);
|
||
z = z->parent->parent;
|
||
} else {
|
||
if (z == z->parent->left) {
|
||
z = z->parent;
|
||
c_RBTree_RightRotate(self, z);
|
||
}
|
||
c_RBTree_SetColor(z->parent, C_RB_BLACK);
|
||
c_RBTree_SetColor(z->parent->parent, C_RB_RED);
|
||
c_RBTree_LeftRotate(self, z->parent->parent);
|
||
}
|
||
}
|
||
}
|
||
c_RBTree_SetColor(self->root, C_RB_BLACK); // 根节点雷打不动强制为黑
|
||
}
|
||
|
||
|
||
/**
|
||
* @brief 【二级指针艺术】：将 u 子树用 v 子树就地顶替
|
||
* @note 完美合并了“修改父节点孩子指针”与“修改根节点 self->root”的两套繁琐逻辑
|
||
*/
|
||
C_STATIC_FORCE_INLINE
|
||
void c_RBTree_Transplant(c_RBTree_t* self, c_RBNode_t* u, c_RBNode_t* v) {
|
||
c_RBNode_t** pp = (u->parent == NULL) ? &(self->root) : ((u == u->parent->left) ? &(u->parent->left) : &(u->parent->right));
|
||
*pp = v; // 一行代码，顺着物理内存地址直接擦除并覆写
|
||
if (v != NULL) {
|
||
v->parent = u->parent;
|
||
}
|
||
}
|
||
|
||
/**
|
||
* @brief 后序遍历释放树中所有节点的私有递归函数
|
||
*/
|
||
static void c_RBTree_ClearInternal(c_RBTree_t* self, c_RBNode_t* node) {
|
||
if (node == NULL) return;
|
||
|
||
// 采用后序遍历（Post-order），自下而上打包火化，防止提前斩断前驱后驱通路
|
||
c_RBTree_ClearInternal(self, node->left);
|
||
c_RBTree_ClearInternal(self, node->right);
|
||
|
||
// 闭环通过内置的多态分配器，物理回收合并变长连续空间
|
||
c_Allocator_Free(&self->allocator, node);
|
||
}
|
||
|
||
|
||
// ==================================================================================================================
|
||
// 3. 终极奥义：基于二级指针引用的无哨兵删除自修复 (Remove & Fixup)
|
||
// ==================================================================================================================
|
||
|
||
|
||
C_STATIC_FORCE_INLINE
|
||
void c_RBTree_RemoveFixup(c_RBTree_t* self, c_RBNode_t* x, c_RBNode_t* x_parent) {
|
||
// 由于 x 可能为 NULL（此时表示黑色叶子外部边缘），我们需要依靠显式传递的 x_parent 来逆向感知拓扑
|
||
while (x != self->root && c_RBTree_GetColor(x) == C_RB_BLACK) {
|
||
if (x == x_parent->left || (x == NULL && x_parent->left == NULL)) {
|
||
c_RBNode_t* w = x_parent->right; // 兄弟节点
|
||
|
||
if (c_RBTree_GetColor(w) == C_RB_RED) {
|
||
// 情况 1: 兄弟是红的
|
||
c_RBTree_SetColor(w, C_RB_BLACK);
|
||
c_RBTree_SetColor(x_parent, C_RB_RED);
|
||
c_RBTree_LeftRotate(self, x_parent);
|
||
w = x_parent->right;
|
||
}
|
||
|
||
if (w != NULL && c_RBTree_GetColor(w->left) == C_RB_BLACK && c_RBTree_GetColor(w->right) == C_RB_BLACK) {
|
||
// 情况 2: 兄弟的孩子全为黑
|
||
c_RBTree_SetColor(w, C_RB_RED);
|
||
x = x_parent;
|
||
x_parent = x->parent; // 双指针同步上滑
|
||
} else {
|
||
// 情况 3: 兄弟的右孩子是黑色
|
||
if (w != NULL && c_RBTree_GetColor(w->right) == C_RB_BLACK) {
|
||
c_RBTree_SetColor(w->left, C_RB_BLACK);
|
||
c_RBTree_SetColor(w, C_RB_RED);
|
||
c_RBTree_RightRotate(self, w);
|
||
w = x_parent->right;
|
||
}
|
||
// 情况 4: 复杂的终极平衡变色旋转
|
||
if (w != NULL) {
|
||
c_RBTree_SetColor(w, c_RBTree_GetColor(x_parent));
|
||
c_RBTree_SetColor(w->right, C_RB_BLACK);
|
||
}
|
||
c_RBTree_SetColor(x_parent, C_RB_BLACK);
|
||
c_RBTree_LeftRotate(self, x_parent);
|
||
x = self->root; // 强行收敛跳出
|
||
}
|
||
} else {
|
||
// 镜像对称对称分支
|
||
c_RBNode_t* w = x_parent->left;
|
||
if (c_RBTree_GetColor(w) == C_RB_RED) {
|
||
c_RBTree_SetColor(w, C_RB_BLACK);
|
||
c_RBTree_SetColor(x_parent, C_RB_RED);
|
||
c_RBTree_RightRotate(self, x_parent);
|
||
w = x_parent->left;
|
||
}
|
||
if (w != NULL && c_RBTree_GetColor(w->right) == C_RB_BLACK && c_RBTree_GetColor(w->left) == C_RB_BLACK) {
|
||
c_RBTree_SetColor(w, C_RB_RED);
|
||
x = x_parent;
|
||
x_parent = x->parent;
|
||
} else {
|
||
if (w != NULL && c_RBTree_GetColor(w->left) == C_RB_BLACK) {
|
||
c_RBTree_SetColor(w->right, C_RB_BLACK);
|
||
c_RBTree_SetColor(w, C_RB_RED);
|
||
c_RBTree_LeftRotate(self, w);
|
||
w = x_parent->left;
|
||
}
|
||
if (w != NULL) {
|
||
c_RBTree_SetColor(w, c_RBTree_GetColor(x_parent));
|
||
c_RBTree_SetColor(w->left, C_RB_BLACK);
|
||
}
|
||
c_RBTree_SetColor(x_parent, C_RB_BLACK);
|
||
c_RBTree_RightRotate(self, x_parent);
|
||
x = self->root;
|
||
}
|
||
}
|
||
}
|
||
c_RBTree_SetColor(x, C_RB_BLACK);
|
||
}
|
||
|
||
/* ------------------------------------------------------------------------------------------------------------------ */
|
||
/* */
|
||
|
||
|
||
|
||
// 原地初始化：控制头全清零，root 严格初始化为 NULL (0)
|
||
c_err_t c_RBTree_Init(c_RBTree_t* self, c_size_t item_size, c_RBTree_CompareFn_t compare_fn, c_Allocator_t* allocator) {
|
||
if (!self || item_size == 0 || !compare_fn) return C_ERR_PARAM;
|
||
|
||
self->allocator = (allocator != NULL) ? *allocator : c_DefaultAllocator;
|
||
self->item_size = item_size;
|
||
self->compare = compare_fn;
|
||
self->size = 0;
|
||
self->root = NULL; // 零开销初始空态
|
||
return C_ERR_OK;
|
||
}
|
||
|
||
|
||
c_err_t c_RBTree_Insert(c_RBTree_t* self, const void* item) {
|
||
if (!self || !item) return C_ERR_PARAM;
|
||
|
||
c_RBNode_t* y = NULL;
|
||
c_RBNode_t* x = self->root;
|
||
|
||
while (x != NULL) {
|
||
y = x;
|
||
int cmp = self->compare(item, RB_NODE_DATA(x));
|
||
if (cmp < 0) x = x->left;
|
||
else if (cmp > 0) x = x->right;
|
||
else return C_ERR_PARAM; // 去重拒绝
|
||
}
|
||
|
||
// 分配变长一体化连续空间
|
||
c_size_t total_bytes = sizeof(c_RBNode_t) + self->item_size;
|
||
c_RBNode_t* z = (c_RBNode_t*)c_Allocator_Alloc(&self->allocator, total_bytes);
|
||
if (!z) return C_ERR_NOMEM;
|
||
|
||
z->parent = y;
|
||
z->left = NULL;
|
||
z->right = NULL;
|
||
z->color = C_RB_RED; // 新插入节点必为红色
|
||
memcpy(RB_NODE_DATA(z), item, self->item_size);
|
||
|
||
if (y == NULL) {
|
||
self->root = z;
|
||
} else if (self->compare(RB_NODE_DATA(z), RB_NODE_DATA(y)) < 0) {
|
||
y->left = z;
|
||
} else {
|
||
y->right = z;
|
||
}
|
||
|
||
c_RBTree_InsertFixup(self, z);
|
||
self->size++;
|
||
return C_ERR_OK;
|
||
}
|
||
|
||
|
||
c_err_t c_RBTree_Remove(c_RBTree_t* self, const void* key) {
|
||
if (!self || !key || self->size == 0) return C_ERR_PARAM;
|
||
|
||
c_RBNode_t* z = self->root;
|
||
while (z != NULL) {
|
||
int cmp = self->compare(key, RB_NODE_DATA(z));
|
||
if (cmp < 0) z = z->left;
|
||
else if (cmp > 0) z = z->right;
|
||
else break;
|
||
}
|
||
|
||
if (z == NULL) return C_ERR_NOTFOUND; // 节点不存在
|
||
|
||
c_RBNode_t* x;
|
||
c_RBNode_t* x_parent; // 【防跑飞核心】：显式声明局部变量缓存亲代变量
|
||
c_RBNode_t* y = z;
|
||
c_RBColor_t y_original_color = y->color;
|
||
|
||
if (z->left == NULL) {
|
||
x = z->right;
|
||
x_parent = z->parent;
|
||
c_RBTree_Transplant(self, z, z->right);
|
||
} else if (z->right == NULL) {
|
||
x = z->left;
|
||
x_parent = z->parent;
|
||
c_RBTree_Transplant(self, 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) {
|
||
x_parent = y; // 后继直接在下面，新父亲变为后继本身
|
||
} else {
|
||
x_parent = y->parent;
|
||
c_RBTree_Transplant(self, y, y->right);
|
||
y->right = z->right;
|
||
if (y->right != NULL) y->right->parent = y;
|
||
}
|
||
c_RBTree_Transplant(self, z, y);
|
||
y->left = z->left;
|
||
if (y->left != NULL) y->left->parent = y;
|
||
y->color = z->color;
|
||
}
|
||
|
||
// 物理熔断销毁控制外壳
|
||
c_Allocator_Free(&self->allocator, z);
|
||
|
||
// 如果剥离的底色是黑色，黑高天平倾斜，驱动自平衡修复
|
||
if (y_original_color == C_RB_BLACK) {
|
||
c_RBTree_RemoveFixup(self, x, x_parent);
|
||
}
|
||
|
||
self->size--;
|
||
return C_ERR_OK;
|
||
}
|
||
|
||
bool c_RBTree_Contains(const c_RBTree_t* self, const void* key) {
|
||
if (!self || !key) return false;
|
||
c_RBNode_t* x = self->root;
|
||
while (x != NULL) {
|
||
int cmp = self->compare(key, RB_NODE_DATA(x));
|
||
if (cmp < 0) x = x->left;
|
||
else if (cmp > 0) x = x->right;
|
||
else return true;
|
||
}
|
||
return false;
|
||
}
|
||
|
||
|
||
void c_RBTree_Clear(c_RBTree_t* self) {
|
||
// 强御级边界守卫：拦截一切非法或已经是空态的呼叫
|
||
if (!self || self->root == NULL) {
|
||
return;
|
||
}
|
||
|
||
// 驱动自下而上的递归解体火化流
|
||
c_RBTree_ClearInternal(self, self->root);
|
||
|
||
// 状态完全与死节点脱钩，重新滑移复位到你指定的 0 纯净空树状态
|
||
self->root = NULL;
|
||
self->size = 0; // 账目同步清零
|
||
}
|
||
|
||
void c_RBTree_Destroy(c_RBTree_t* self) {
|
||
// 強御級防禦：若控制頭指標本身為空，或者這棵樹已經是純淨的 0 態空樹，則直接冪等返回
|
||
if (!self || self->root == NULL) {
|
||
return;
|
||
}
|
||
|
||
// 1. 呼叫核心 Clear 接口：自下而上執行後序（Post-order）遞迴火化
|
||
// 內部的 c_Allocator_Free 會將所有變長節點資源完整退還給綁定的專屬記憶體池
|
||
c_RBTree_Clear(self);
|
||
|
||
// 2. 徹底清空控制頭中的核心狀態，將生命週期變數完美還原至 0
|
||
self->root = NULL;
|
||
self->size = 0;
|
||
self->item_size = 0;
|
||
self->compare = NULL;
|
||
|
||
// 注意：self->allocator 控制頭本身是由呼叫者在外部（例如棧或宿主結構體）宣告的物理記憶體，
|
||
// 其銷毀工作（如 c_Allocator_Destroy）應遵循職責隔離規範，由外部的宿主模組繼續向下推動。
|
||
}
|