C语言 红黑树插入代码

Question

我正在尝试编写一棵红黑树的实现供我自己学习，我已经盯着这个几天了。

谁能帮我弄清楚如何让双旋转案例正常工作？如果您在浏览片段时发现任何其他糟糕的东西，请随时让我觉得自己像个白痴。

感谢您的帮助。

再平衡功能

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;
};

Answer 1

与 AVL 树相比，红黑树中的双旋转有点棘手，原因是 RB 树中存在父指针。 当我们旋转树时，我们也需要调整父指针。 我将用一个例子来演示它。下面的树是初始树

20 
/       
10        30
/             
3      15      
/    
12    18

这是右边旋转的

10 
/       
3        20
/           
15    30    
/    
12    18

我们在那里观察到两件事。 1.根被改变了。 2. 3 个节点的父指针已更改(10、20、15(，即。对于新根，旧根和新根的右子根。对于 所有正确的旋转案例。这是为了确保，按顺序 旋转发生后遍历保持不变。

现在看看我们如何逐步旋转。

public Node rotateRight() {
if(root.left == null) {
System.out.println("Cannot be rotated Right");
} else {
Node newRoot = root.left; // Assign new root.
Node orphaned = newRoot.right; // Store ref to the right child of new root.
newRoot.parent = root.parent; // new root parent point to old root parent.
root.parent = newRoot; // new root becomes parent of old root.
newRoot.right = root;  // old root becomes right child of new root
root.left = orphaned;
if (orphaned != null) {
orphaned.parent = root;
}
root = newRoot;
}
return root;
}

尝试在纸上做几次，然后看起来会更简单。 希望这有帮助。

回到RB树。上述实现将应用于我们在平衡过程中所做的两个旋转。(让我们采取正确的案例(

当我们有 3 代节点时，一个祖父、一个父亲和一个 入的孩子。 1.当我们有RR或LL配置时，不要交换颜色 2.使用RL和LR，我们旋转祖父，我们交换爷爷和父亲的颜色，但是在旋转父级时，我们不会尝试交换 颜色。目的只是将它们带到 RR 或 LL 配置中。

a. We need to see if the grandpa is right or left child of its 
parent and assign the root accordingly.
b. If the grandpa has no parent means we are doing rotation at the level of tree's root, then we reassign the root of the tree.

我的 RB 树实现的代码片段。

temp is the new node which is added.
// if new node is the right child AND parent is right child
else if(temp.parent.right == temp && grandPa!=null && grandPa.right == temp.parent) {
// If becomes a right-right case
Boolean isLeft = isLeftChild(grandPa);
if(isLeft == null) {
// Grandpa has no parent, reassign root.
root = rotateLeft(grandPa,true);
}
else if(isLeft) {
grandPa.parent.left = rotateLeft(grandPa,true);
} else {
grandPa.parent.right = rotateLeft(grandPa,true);
}
}