我正在尝试为自己的学习编写一个红黑树的实现，我已经盯着这个看了几天了。
谁能帮我弄清楚如何让双旋转箱正常工作？如果您在浏览这些片段时发现了其他任何令人讨厌的东西，请随时让我觉得自己像个白痴。
感谢您的帮助。
再平衡功能
int impl_rbtree_rebalance (xs_rbtree_node *node)
{
check_mem(node);
xs_rbtree_node *p = node->parent;
if (!p) return 0;
if (p->color == BLACK) return 0;
xs_rbtree_node *gp = p->parent;
if (!gp) return 0;
xs_rbtree_node *uncle;
int is_parent_left_child;
/* check if parent is left or right child */
if (p == gp->left) {
uncle = gp->right;
is_parent_left_child = 1;
} else {
uncle = gp->left;
is_parent_left_child = 0;
}
if (uncle && uncle->color == RED) {
p->color = uncle->color = BLACK;
gp->color = RED;
} else { /* uncle is black */
if (gp->parent == NULL) return 0;
if (node == p->left) {
if (is_parent_left_child == 0) {
/* Double rotation logic */
} else {/* parent is left child */
gp->color = RED;
gp->left->color = BLACK;
impl_rbtree_rr(&gp);
}
} else { /* node is right child */
if (is_parent_left_child == 1) {
/* Double rotation logic */
} else { /* parent is right child */
gp->color = RED;
gp->right->color = BLACK;
impl_rbtree_rl(&gp);
}
}
}
return 0;
}
相关职能
xs_rbtree_node *impl_rbtree_node_alloc (xs_rbtree_node *parent, void *val)
{
xs_rbtree_node *n = malloc(sizeof(xs_rbtree_node));
n->parent = parent;
n->val = val;
n->left = n->right = NULL;
n->color = (parent == NULL) ? BLACK : RED;
return n;
}
void rbtree_insert (xs_rbtree_ *tree, void *val)
{
check_mem(tree);
check_mem(val);
tree->root = impl_rbtree_insert(tree->cmp, NULL, tree->root, val);
tree->root->color = BLACK;
}
xs_rbtree_node *impl_rbtree_insert (xs_tree_cmp cmp, xs_rbtree_node *parent, xs_rbtree_node *node, void *val)
{
check_mem(cmp);
check_mem(val);
if (!node) {
node = impl_rbtree_node_alloc(parent, val);
} else if (cmp(node->val, val) < 0) {
/* node->val < val */
check_mem(node);
node->right = impl_rbtree_insert(cmp, node, node->right, val);
impl_rbtree_rebalance(node->right);
} else if (cmp(node->val, val) > 0) {
/* node->val > val */
check_mem(node);
node->left = impl_rbtree_insert(cmp, node, node->left, val);
impl_rbtree_rebalance(node->left);
}
/* ignoring values that are equal */
return node;
}
旋转函数
#include <xs/base/bstree.h>
void impl_tree_rr(xs_tree_node **node)
{
check_mem(*node);
check_mem((*node)->left);
xs_tree_node *k1, *k2;
k2 = *node;
k1 = k2->left;
k2->left = k1->right;
k1->right = k2;
k1->parent = k2->parent;
k2->parent = k1;
*node = k1;
}
void impl_tree_rl(xs_tree_node **node)
{
check_mem(*node);
check_mem((*node)->right);
xs_tree_node *k1, *k2;
k2 = *node;
k1 = k2->right;
k2->right = k1->left;
k1->left = k2;
k1->parent = k2->parent;
k2->parent = k1;
*node = k1;
}
void impl_tree_drr(xs_tree_node **node)
{
check_mem(*node);
impl_tree_rl(&((*node)->left));
impl_tree_rr(node);
}
void impl_tree_drl(xs_tree_node **node)
{
check_mem(*node);
impl_tree_rr(&((*node)->right));
impl_tree_rl(node);
}
RBT 定义
typedef struct xs_rbtree_node xs_rbtree_node;
typedef struct xs_rbtree_ xs_rbtree_;
typedef enum { RED, BLACK } impl_rbtree_color;
struct xs_rbtree_node {
xs_rbtree_node *left;
xs_rbtree_node *right;
xs_rbtree_node *parent;
void *val;
impl_rbtree_color color;
};
struct xs_rbtree_ {
xs_rbtree_node *root;
xs_tree_cmp cmp;
};