403 lines
14 KiB
C
403 lines
14 KiB
C
#include <c_RedBlackBST.h>
|
|
|
|
|
|
/* ------------------------------------------------------------------------------------------------------------------ */
|
|
/* */
|
|
|
|
|
|
/**
|
|
* @brief 内部辅助：安全检测某个节点的父链接是否为红
|
|
*/
|
|
C_STATIC_FORCE_INLINE
|
|
bool c_RBBST_IsRed(const c_RBBSTNode_t* node) {
|
|
if (node == NULL) return C_RB_BLACK; // 空链接恒为黑色链接
|
|
return node->color == C_RB_RED;
|
|
}
|
|
|
|
/**
|
|
* @brief 内部平衡机制 1：左旋操作
|
|
*
|
|
* 将任意临时的右倾红链接，通过局部拓扑对调，安全置换为标准合规的左倾红链接
|
|
*/
|
|
C_STATIC_FORCE_INLINE
|
|
void c_RBBST_RotateLeft(c_RBBSTNode_t** node_ptr) {
|
|
c_RBBSTNode_t* h = *node_ptr;
|
|
c_RBBSTNode_t* x = h->right;
|
|
|
|
h->right = x->left;
|
|
x->left = h;
|
|
|
|
x->color = h->color;
|
|
h->color = C_RB_RED;
|
|
|
|
*node_ptr = x; // 代理写回父节点
|
|
}
|
|
|
|
/**
|
|
* @brief 内部平衡机制 2：右旋操作
|
|
*
|
|
* 临时放宽左侧的连续红链接，为后续的 4-node 拆分做前置拓扑对调准备
|
|
*/
|
|
C_STATIC_FORCE_INLINE
|
|
void c_RBBST_RotateRight(c_RBBSTNode_t** node_ptr) {
|
|
c_RBBSTNode_t* h = *node_ptr;
|
|
c_RBBSTNode_t* x = h->left;
|
|
|
|
h->left = x->right;
|
|
x->right = h;
|
|
|
|
x->color = h->color;
|
|
h->color = C_RB_RED;
|
|
|
|
*node_ptr = x;
|
|
}
|
|
|
|
|
|
/**
|
|
* @brief 内部平衡机制 3：颜色翻转（分解临时的 4-node 节点）
|
|
*/
|
|
C_STATIC_FORCE_INLINE
|
|
void c_RBBST_FlipColors(c_RBBSTNode_t* h) {
|
|
h->color = !h->color;
|
|
if (h->left) h->left->color = !h->left->color;
|
|
if (h->right) h->right->color = !h->right->color;
|
|
}
|
|
|
|
/**
|
|
* @brief 内部递归插入与自适应动态平衡状态机
|
|
*/
|
|
static c_err_t c_RedBlackBST_InternalPut(c_RedBlackBST_t* self, c_RBBSTNode_t** node_ptr, const void* key, const void* val, bool* is_new_inserted) {
|
|
c_RBBSTNode_t* curr = *node_ptr;
|
|
|
|
// 递归基：开辟挂载新节点，新生成的链接默认为极其活跃的【红链接】
|
|
if (curr == NULL) {
|
|
c_RBBSTNode_t* new_node = (c_RBBSTNode_t*)c_Allocator_Alloc(&self->allocator, sizeof(*new_node));
|
|
void* new_key = c_Allocator_Alloc(&self->allocator, self->key_size);
|
|
void* new_val = c_Allocator_Alloc(&self->allocator, self->val_size);
|
|
|
|
if (!new_node || !new_key || !new_val) {
|
|
if (new_node) c_Allocator_Free(&self->allocator, new_node);
|
|
if (new_key) c_Allocator_Free(&self->allocator, new_key);
|
|
if (new_val) c_Allocator_Free(&self->allocator, new_val);
|
|
return C_ERR_NOMEM;
|
|
}
|
|
|
|
memcpy(new_key, key, self->key_size);
|
|
memcpy(new_val, val, self->val_size);
|
|
new_node->key = new_key;
|
|
new_node->val = new_val;
|
|
new_node->left = NULL;
|
|
new_node->right = NULL;
|
|
new_node->color = C_RB_RED; // 🌟 核心：新节点一律为红链接
|
|
|
|
*node_ptr = new_node;
|
|
*is_new_inserted = true;
|
|
return C_ERR_OK;
|
|
}
|
|
|
|
int cmp_res = self->cmp(key, curr->key, self->args);
|
|
c_err_t err = C_ERR_OK;
|
|
|
|
if (cmp_res < 0) {
|
|
err = c_RedBlackBST_InternalPut(self, &(curr->left), key, val, is_new_inserted);
|
|
} else if (cmp_res > 0) {
|
|
err = c_RedBlackBST_InternalPut(self, &(curr->right), key, val, is_new_inserted);
|
|
} else {
|
|
// 键已存在，执行覆写
|
|
memcpy(curr->val, val, self->val_size);
|
|
*is_new_inserted = false;
|
|
return C_ERR_OK;
|
|
}
|
|
|
|
if (err != C_ERR_OK) return err;
|
|
|
|
// 🌟🌟🌟【左倾红黑树自适应自平衡标准控制链（Sedgewick 经典三部曲）】🌟🌟🌟
|
|
// 指针可能随着旋转被改写，故直接对当前二级指针接管的实体执行自底向上回溯刷新
|
|
|
|
// 步骤 1：若右链接为红且左链接为黑，强制执行左旋使其左倾
|
|
if (c_RBBST_IsRed((*node_ptr)->right) && !c_RBBST_IsRed((*node_ptr)->left)) {
|
|
c_RBBST_RotateLeft(node_ptr);
|
|
}
|
|
// 步骤 2：若左链接为红，且左子节点的左链接也是红（连续两条红链接出现），强制执行右旋平衡
|
|
if (c_RBBST_IsRed((*node_ptr)->left) && c_RBBST_IsRed((*node_ptr)->left->left)) {
|
|
c_RBBST_RotateRight(node_ptr);
|
|
}
|
|
// 步骤 3：若左右两条子链接同为红，强制翻转颜色，将红链接推向更高的父层级
|
|
if (c_RBBST_IsRed((*node_ptr)->left) && c_RBBST_IsRed((*node_ptr)->right)) {
|
|
c_RBBST_FlipColors(*node_ptr);
|
|
}
|
|
|
|
return C_ERR_OK;
|
|
}
|
|
|
|
/* ------------------------------------------------------------------------------------------------------------------ */
|
|
/* */
|
|
|
|
c_err_t c_RedBlackBST_Init(c_RedBlackBST_t* self, c_size_t key_size, c_size_t val_size, c_SortCompare_t cmp, void* args, c_Allocator_t* allocator) {
|
|
if (!self || key_size == 0 || val_size == 0 || !cmp) {
|
|
return C_ERR_PARAM;
|
|
}
|
|
|
|
if (allocator) {
|
|
self->allocator = *allocator;
|
|
} else {
|
|
self->allocator = c_DefaultAllocator;
|
|
}
|
|
|
|
self->root = NULL;
|
|
self->size = 0;
|
|
self->key_size = key_size;
|
|
self->val_size = val_size;
|
|
self->cmp = cmp;
|
|
self->args = args;
|
|
|
|
return C_ERR_OK;
|
|
}
|
|
|
|
|
|
/**
|
|
* @brief 存入键值对（始终维持树的对数级绝对平衡，时间复杂度 O(log N)）
|
|
*/
|
|
c_err_t c_RedBlackBST_Put(c_RedBlackBST_t* self, const void* key, const void* val) {
|
|
if (!self || !key || !val) return C_ERR_PARAM;
|
|
|
|
bool is_new = false;
|
|
c_err_t err = c_RedBlackBST_InternalPut(self, &(self->root), key, val, &is_new);
|
|
if (err == C_ERR_OK) {
|
|
if (is_new) self->size++;
|
|
// 根节点的父链接在扩容和旋转后必须强制恢复回稳定严肃的【黑链接】
|
|
self->root->color = C_RB_BLACK;
|
|
}
|
|
return err;
|
|
}
|
|
|
|
/**
|
|
* @brief 精准二叉有序检索（时间复杂度稳定为 O(log N)）
|
|
*/
|
|
c_err_t c_RedBlackBST_Get(const c_RedBlackBST_t* self, const void* key, void* out_val) {
|
|
if (!self || !key || !out_val) return C_ERR_PARAM;
|
|
|
|
c_RBBSTNode_t* curr = self->root;
|
|
while (curr != NULL) {
|
|
int cmp_res = self->cmp(key, curr->key, self->args);
|
|
if (cmp_res < 0) curr = curr->left;
|
|
else if (cmp_res > 0) curr = curr->right;
|
|
else {
|
|
memcpy(out_val, curr->val, self->val_size);
|
|
return C_ERR_OK;
|
|
}
|
|
}
|
|
return C_ERR_NOTFOUND;
|
|
}
|
|
|
|
/**
|
|
* @brief 检查树中是否有效包含指定的 Key
|
|
*/
|
|
bool c_RedBlackBST_Contains(const c_RedBlackBST_t* self, const void* key) {
|
|
if (!self || !key) return false;
|
|
c_RBBSTNode_t* curr = self->root;
|
|
while (curr != NULL) {
|
|
int cmp_res = self->cmp(key, curr->key, self->args);
|
|
if (cmp_res < 0) curr = curr->left;
|
|
else if (cmp_res > 0) curr = curr->right;
|
|
else return true;
|
|
}
|
|
return false;
|
|
}
|
|
|
|
static void c_RedBlackBST_InternalDeinit(c_Allocator_t* alloc, c_RBBSTNode_t* node) {
|
|
if (node == NULL) return;
|
|
c_RedBlackBST_InternalDeinit(alloc, node->left);
|
|
c_RedBlackBST_InternalDeinit(alloc, node->right);
|
|
c_Allocator_Free(alloc, node->key);
|
|
c_Allocator_Free(alloc, node->val);
|
|
c_Allocator_Free(alloc, node);
|
|
}
|
|
|
|
/**
|
|
* @brief 彻底销毁红黑树并逆向释放全部堆资源
|
|
*/
|
|
void c_RedBlackBST_Destroy(c_RedBlackBST_t* self) {
|
|
if (self && self->root) {
|
|
c_RedBlackBST_InternalDeinit(&self->allocator, self->root);
|
|
self->root = NULL;
|
|
self->size = 0;
|
|
}
|
|
}
|
|
|
|
/* ------------------------------------------------------------------------------------------------------------------ */
|
|
/* */
|
|
|
|
|
|
/**
|
|
* @brief 自底向上沿途修复平衡（Fix-up）
|
|
*/
|
|
static void c_RBBST_Balance(c_RBBSTNode_t** node_ptr) {
|
|
if (*node_ptr == NULL) return;
|
|
|
|
// 1. 纠正右倾红链接
|
|
if (c_RBBST_IsRed((*node_ptr)->right) && !c_RBBST_IsRed((*node_ptr)->left)) {
|
|
c_RBBST_RotateLeft(node_ptr);
|
|
}
|
|
// 2. 纠正连续红链接
|
|
if (c_RBBST_IsRed((*node_ptr)->left) && c_RBBST_IsRed((*node_ptr)->left->left)) {
|
|
c_RBBST_RotateRight(node_ptr);
|
|
}
|
|
// 3. 分解临时的 4-node
|
|
if (c_RBBST_IsRed((*node_ptr)->left) && c_RBBST_IsRed((*node_ptr)->right)) {
|
|
c_RBBST_FlipColors(*node_ptr);
|
|
}
|
|
}
|
|
|
|
/**
|
|
* @brief 假设当前节点 h 为红且 h->left 和 h->left->left 都为黑，将红链接强制向左移动
|
|
*/
|
|
static void c_RBBST_MoveRedLeft(c_RBBSTNode_t** node_ptr) {
|
|
c_RBBSTNode_t* h = *node_ptr;
|
|
c_RBBST_FlipColors(h);
|
|
|
|
// 如果亲兄弟节点的左子节点是红链接，说明可以向右边“借”一个红链接过来
|
|
if (c_RBBST_IsRed(h->right->left)) {
|
|
c_RBBST_RotateRight(&(h->right));
|
|
c_RBBST_RotateLeft(node_ptr);
|
|
// 旋转后由于指针载体换成新根，同步对其刷新颜色翻转
|
|
c_RBBST_FlipColors(*node_ptr);
|
|
}
|
|
}
|
|
|
|
/**
|
|
* @brief 假设当前节点 h 为红且 h->right 和 h->right->left 都为黑，将红链接强制向右移动
|
|
*/
|
|
static void c_RBBST_MoveRedRight(c_RBBSTNode_t** node_ptr) {
|
|
c_RBBSTNode_t* h = *node_ptr;
|
|
c_RBBST_FlipColors(h);
|
|
|
|
// 如果亲兄弟节点的左子节点是红链接，说明可以向左边“借”一个红链接过来
|
|
if (c_RBBST_IsRed(h->left->left)) {
|
|
c_RBBST_RotateRight(node_ptr);
|
|
c_RBBST_FlipColors(*node_ptr);
|
|
}
|
|
}
|
|
|
|
/**
|
|
* @brief 内部辅助：寻找指定子树的绝对最小值节点（内部删除并解绑提取）
|
|
*/
|
|
static c_RBBSTNode_t* c_RedBlackBST_InternalDeleteMin(c_RedBlackBST_t* self, c_RBBSTNode_t** node_ptr) {
|
|
c_RBBSTNode_t* curr = *node_ptr;
|
|
|
|
if (curr->left == NULL) {
|
|
*node_ptr = NULL; // 断开断裂
|
|
return curr;
|
|
}
|
|
|
|
// 核心推进：如果当前左子链和左子的左子都是黑色链接，为了防止删除 2-node 崩溃，强行将红链接左推
|
|
if (!c_RBBST_IsRed(curr->left) && !c_RBBST_IsRed(curr->left->left)) {
|
|
c_RBBST_MoveRedLeft(node_ptr);
|
|
}
|
|
|
|
c_RBBSTNode_t* min_node = c_RedBlackBST_InternalDeleteMin(self, &((*node_ptr)->left));
|
|
|
|
// 自底向上逐级退栈平衡修复
|
|
c_RBBST_Balance(node_ptr);
|
|
return min_node;
|
|
}
|
|
|
|
/**
|
|
* @brief 内部递归自适应删除核心逻辑
|
|
*/
|
|
static c_err_t c_RedBlackBST_InternalDelete(c_RedBlackBST_t* self, c_RBBSTNode_t** node_ptr, const void* key) {
|
|
c_RBBSTNode_t* curr = *node_ptr;
|
|
if (curr == NULL) {
|
|
return C_ERR_NOTFOUND;
|
|
}
|
|
|
|
// 1. 如果目标键小于当前节点，向左子树探查
|
|
if (self->cmp(key, curr->key, self->args) < 0) {
|
|
// 如果左边深度不足，前置借调红链接向左推
|
|
if (!c_RBBST_IsRed(curr->left) && !c_RBBST_IsRed(curr->left->left)) {
|
|
c_RBBST_MoveRedLeft(node_ptr);
|
|
}
|
|
c_err_t err = c_RedBlackBST_InternalDelete(self, &((*node_ptr)->left), key);
|
|
c_RBBST_Balance(node_ptr); // 退栈修复
|
|
return err;
|
|
}
|
|
else {
|
|
// 2. 如果当前左子链接是红的，强制右旋。
|
|
// 这可以让待比较的较大或相等的元素被顺利挪动并暴露到右侧
|
|
if (c_RBBST_IsRed(curr->left)) {
|
|
c_RBBST_RotateRight(node_ptr);
|
|
curr = *node_ptr; // 刷新本地缓存指针
|
|
}
|
|
|
|
// 3. 精确命中检查条件：如果完全相等，且已经走到了树的叶子底部（无右子树）
|
|
// 此时由于自顶向下红链接移位的保护，curr 必然含有红链接，可以直接抹除并释放
|
|
if (self->cmp(key, curr->key, self->args) == 0 && (curr->right == NULL)) {
|
|
c_RBBSTNode_t* old_node = curr;
|
|
*node_ptr = curr->left; // 让左子树托管
|
|
|
|
c_Allocator_Free(&self->allocator, old_node->key);
|
|
c_Allocator_Free(&self->allocator, old_node->val);
|
|
c_Allocator_Free(&self->allocator, old_node);
|
|
return C_ERR_OK;
|
|
}
|
|
|
|
// 4. 继续向右子树探查（目标比当前大，或者相等但处于中间层级）
|
|
if (!c_RBBST_IsRed(curr->right) && !c_RBBST_IsRed(curr->right->left)) {
|
|
c_RBBST_MoveRedRight(node_ptr);
|
|
curr = *node_ptr;
|
|
}
|
|
|
|
// 5. 中间层级精确命中：执行 Hibbard 后继者替换策略
|
|
if (self->cmp(key, curr->key, self->args) == 0) {
|
|
c_RBBSTNode_t* old_node = curr;
|
|
|
|
// 剥离并索取右子树的绝对最小值节点作为继承人
|
|
c_RBBSTNode_t* successor = c_RedBlackBST_InternalDeleteMin(self, &(curr->right));
|
|
|
|
// 继承人完美承接原有乱序节点的所有双向指针拓扑以及红黑颜色
|
|
successor->left = old_node->left;
|
|
successor->right = (*node_ptr)->right;
|
|
successor->color = old_node->color;
|
|
|
|
*node_ptr = successor; // 代理顶替
|
|
|
|
// 彻底释放旧节点占用的内存
|
|
c_Allocator_Free(&self->allocator, old_node->key);
|
|
c_Allocator_Free(&self->allocator, old_node->val);
|
|
c_Allocator_Free(&self->allocator, old_node);
|
|
|
|
c_RBBST_Balance(node_ptr);
|
|
return C_ERR_OK;
|
|
}
|
|
else {
|
|
// 只是普通的向右边路探查
|
|
c_err_t err = c_RedBlackBST_InternalDelete(self, &((*node_ptr)->right), key);
|
|
c_RBBST_Balance(node_ptr);
|
|
return err;
|
|
}
|
|
}
|
|
}
|
|
|
|
/**
|
|
* @brief 根据指定 Key 彻底从左倾红黑树中斩断删除该节点（时间复杂度卡死在完美的 O(log N) 上限）
|
|
*/
|
|
c_err_t c_RedBlackBST_Delete(c_RedBlackBST_t* self, const void* key) {
|
|
if (!self || !key) {
|
|
return C_ERR_PARAM;
|
|
}
|
|
// 状态码规范链条：空仓异常前置拦截
|
|
if (self->size == 0 || self->root == NULL) {
|
|
return C_ERR_EMPTY;
|
|
}
|
|
|
|
c_err_t err = c_RedBlackBST_InternalDelete(self, &(self->root), key);
|
|
if (err == C_ERR_OK) {
|
|
self->size--;
|
|
// 如果树还没被删空，必须对重组后的最终新树根强制刷新并恢复黑高性质 `'B'`
|
|
if (self->root != NULL) {
|
|
self->root->color = C_RB_BLACK;
|
|
}
|
|
}
|
|
return err;
|
|
}
|