root = rb_rotate_right(other, root);
other = parent->right;
}
other->color = parent->color;
parent->color = BLACK;
if (other->right)
{
other->right->color = BLACK;
}
root = rb_rotate_left(parent, root);
node = root;
break;
}
}
else
{
other = parent->left;
if (other->color == RED)
{
other->color = BLACK;
parent->color = RED;
root = rb_rotate_right(parent, root);
other = parent->left;
}
if ((!other->left || other->left->color == BLACK) &&
(!other->right || other->right->color == BLACK))
{
other->color = RED;
node = parent;
parent = node->parent;
}
else
{
if (!other->left || other->left->color == BLACK)
{
if ((o_right = other->right))
{
o_right->color = BLACK;
}
other->color = RED;
root = rb_rotate_left(other, root);
other = parent->left;
}
other->color = parent->color;
parent->color = BLACK;
if (other->left)
{
other->left->color = BLACK;
}
root = rb_rotate_right(parent, root);
node = root;
break;
}
}
}
if (node)
{
node->color = BLACK;
}
return root;
}
static rb_node_t* rb_search_auxiliary(key_t key, rb_node_t* root, rb_node_t** save)
{
rb_node_t *node = root, *parent = NULL;
int ret;
while (node)
{
parent = node;
ret = node->key - key;
if (0 < ret)
{
node = node->left;
}
else if (0 > ret)
{
node = node->right;
}
else
{
return node;
}
}
if (save)
{
*save = parent;
}
return NULL;
}
rb_node_t* rb_insert(key_t key, data_t data, rb_node_t* root)
{
rb_node_t *parent = NULL, *node;
parent = NULL;
if ((node = rb_search_auxiliary(key, root, &parent)))
{
tmpValue = node->data;
return root;
}
node = rb_new_node(key, data);
node->parent = parent;
node->left = node->right = NULL;
node->color = RED;
if (parent)
{
if (parent->key > key)
{
parent->left = node;
}
else
{
parent->right = node;
}
}
else
{
root = node;
}
return rb_insert_rebalance(node, root);
}
rb_node_t* rb_search(key_t key, rb_node_t* root)
{
return rb_search_auxiliary(key, root, NULL);
}
rb_node_t* rb_erase(key_t key, rb_node_t *root)
{
rb_node_t *child, *parent, *old, *left, *node;
color_t color;
if (!(node = rb_search_auxiliary(key, root, NULL)))
{
printf("key %d is not exist!\n");
return root;
}
old = node;
if (node->left && node->right)
{
node = node->right;
while ((left = node->left) != NULL)
{
n