红黑树算法源码：
一、左旋代码分析：
/*-----------------------------------------------------------
|   node           right
|   / \    ==>     / \
|   a  right     node  y
|       / \       / \    
|       b  y     a   b    //左旋
-----------------------------------------------------------*/
static rb_node_t* rb_rotate_left(rb_node_t* node, rb_node_t* root)      //传入根节点和node（要旋转的节点）
{
rb_node_t* right = node->right;                                        //指定指针指向 right == node->right

if ((node->right = right->left))                                      //使node的右孩子变为b        
{
right->left->parent = node; 
}
right->left = node;                                                 //使node成为right的左孩子

if ((right->parent = node->parent))                                    //使right继承node的父母
{
if (node == node->parent->right)                                //如果node是父母的右孩子，就让right继承右孩子
{
node->parent->right = right;
}
else                                                            //反之，继承左孩子        
{
node->parent->left = right;
}
}
else                                                                //如果node没有父母（他是根节点），就让right继承根节点    
{
root = right;
}
node->parent = right;                                                //最后right成为node的父母

return root;
}

二、右旋代码分析：
/*-----------------------------------------------------------
|       node            left
|       / \             / \
|    left  y   ==>    a    node
|   / \                    / \
|  a   b                  b   y  //右旋与左旋差不多，分析略过
-----------------------------------------------------------*/
static rb_node_t* rb_rotate_right(rb_node_t* node, rb_node_t* root)                //传入根节点和node（要旋转的节点）
{
rb_node_t* left = node->left;                                                 //保存传入节点的左节点，准备进行右旋转

if ((node->left = left->right))                                                //使b覆盖left的位置，与node完成双向指向（原left == b）
{
left->right->parent = node;                                            
}
left->right = node;                                                            //将left的右节点换成node    

if ((left->parent = node->parent))                                             //将left的父亲换成node的父亲
{
if (node == node->parent->right)                                           //判断node属于原父亲的哪一边节点，将left移到相应位置
{
node->parent->right = left;
}
else
{
node->parent->left = left;
}
}
else                                                                           //如果node为根节点，没有父亲，此时将根节点赋为left
{
root = left;
}
node->parent = left;                                                           //将node的父亲换为left，完成旋转   

return root;
}

三、红黑树查找结点代码：
//----------------------------------------------------
//rb_search_auxiliary：查找
//rb_node_t* rb_search：返回找到的结点
//----------------------------------------------------
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;                    //等于0时，返回这个节点
}
}

if (save)                                //当查找的数值找不到时，save用来保存与要查找的节点最近的位置（用来插入）
{
*save = parent;
}

return NULL;                            //找不到，返回空
}

//返回上述rb_search_auxiliary查找结果
rb_node_t* rb_search(key_t key, rb_node_t* root)
{
return rb_search_auxiliary(key, root, NULL);        //只用来查找，不需要返回从哪里插入  
}

四、红黑树插入的代码：
//---------------------------------------------------------
//红黑树的插入结点
rb_node_t* rb_insert(key_t key, data_t data, rb_node_t* root)                //传入节点的值，节点包含的数据，以及根节点
{
rb_node_t *parent = NULL, *node;                                        //parent用来保存插入的地方，node代表节点空间（用来分配）

parent = NULL;
if ((node = rb_search_auxiliary(key, root, &parent)))                    //调用rb_search_auxiliary找到插入结点的地方  //为一个指针赋值为NULL的等式（判断为假）
{
return root;
}

node = rb_new_node(key, data);  //分配结点
node->parent = parent;   
node->left = node->right = NULL;
node->color = RED;

if (parent)                                    //判断插入的节点处于parent的哪个位置（左，右）
{
if (parent->key > key)
{
parent->left = node;
}
else
{
parent->right = node;
}
}
else                                         //根节点为空时，将node设置成根节点
{
root = node;
}

return rb_insert_rebalance(node, root);       //插入结点后，调用rb_insert_rebalance修复红黑树的性质
}

五、针对红黑树插入的三种情况的修复工作：
//红插入的3种情况黑树修复
//为了在下面的注释中表示方便，也为了让下述代码与我的倆篇文章相对应，
//用z表示当前结点，p[z]表示父母、p[p[z]]表示祖父、y表示叔叔。
//--------------------------------------------------------------
static rb_node_t* rb_insert_rebalance(rb_node_t *node, rb_node_t *root)
{
rb_node_t *parent, *gparent, *uncle, *tmp;                      //父母p[z]、祖父p[p[z]]、叔叔y、临时结点*tmp

while ((parent = node->parent) && parent->color == RED)         //parent 为node的父母，且当父母的颜色为红时
{
gparent = parent->parent;                                   //gparent为祖父

if (parent == gparent->left)                                //当父母是祖父的左孩子时。

{
uncle = gparent->right;                                  //定义叔叔的概念，叔叔y就是父母的右孩子。

            if (uncle && uncle->color == RED)                 //情况1：z的叔叔y是红色的，z的父母为红色，父母为祖父母的左孩子，叔叔为右孩子
{
uncle->color = BLACK;                               //将叔叔结点y着为黑色
parent->color = BLACK;                              //z的父母p[z]也着为黑色。解决z，p[z]都是红色的问题。
gparent->color = RED;  
node = gparent;                                     //将祖父当做新增结点z，指针z上移俩层，且着为红色。（进行后续的判断）
}
else                                             //情况2：z的叔叔y是黑色的，z的父母为红色，同时z为父母的右节点
{   
if (parent->right == node)                          //且z为右孩子
{
root = rb_rotate_left(parent, root);             //左旋[结点z，与父母结点]
tmp = parent;                                    //parent与node 互换角色
parent = node;
node = tmp;    
}
//情况3：z的叔叔y是黑色的，z的父母为红色，此时z成为了左孩子。
parent->color = BLACK;                               //z的父母p[z]着为黑色
gparent->color = RED;                               //原祖父结点着为红色
root = rb_rotate_right(gparent, root);                //右旋[结点z，与祖父结点]
}
} 
else 
{                                                     //祖父的右孩子作为父母的节点
uncle = gparent->left;                          //祖父的左孩子作为叔叔结点。[原理还是与上部分一样的]
if (uncle && uncle->color == RED)                  //情况1：z的叔叔y是红色的，父母的颜色为红
{
uncle->color = BLACK;
parent->color = BLACK;
gparent->color = RED;
node = gparent;                               //同上。
}
else                                               
{
if (parent->left == node)                     //情况2：z的叔叔y是黑色的，父母的颜色为红，且z为父母左孩子
{
root = rb_rotate_right(parent, root);     //以结点parent、root右旋
tmp = parent;
parent = node;
node = tmp;                               //parent与node 互换角色
} 
//情况3，z的叔叔y是黑色的，父母的颜色为红，且z为父母右孩子
parent->color = BLACK;
gparent->color = RED;
root = rb_rotate_left(gparent, root);       //以结点gparent和root左旋
}
}
}

root->color = BLACK;                                     //根结点，不论怎样，都得置为黑色。
return root;                                              //返回根结点。
}

六、红黑树的删除：
//------------------------------------------------------------
//红黑树的删除结点
rb_node_t* rb_erase(key_t key, rb_node_t *root)
{
rb_node_t *child, *parent, *old, *left, *node;            //child：用来替代要删除的那个节点 的节点  的儿子，最终作为平衡函数的参数
//parent：1.中间变量：用来将节点间的指向导正  2.作为平衡函数的参数：最终变换后的child的父亲节点
//old：保存要删除的那个节点，最后用来释放  left：中间变量  用来寻找 能替代即将删除的节点 的节点
//node：用来替代要删除的那个节点 的节点
color_t color;                                            //1.用来替代要删除的那个节点 的节点的颜色（在删除的节点左右子树不为空的情况下）
//2.删除节点的颜色（此时是删除的节点有一边为空）
if (!(node = rb_search_auxiliary(key, root, NULL)))      //调用rb_search_auxiliary查找要删除的结点
{
printf("key %d is not exist!\n");
return root;
}

old = node;                                            //保存node节点，此时node为最上层操作节点

if (node->left && node->right)                        //当node的左右孩子不为空时，进行判断
{
node = node->right;                                //使node等于他的右孩子    
while ((left = node->left) != NULL)                //对他的右孩子的左孩子依次遍历，直至为空       //取到左孩子为空的一个节点
{
node = left;                                //目的：取到能充当 要删除的节点的位置   的节点（原理：取到的节点比右子树的值小，比左子树的值大）
}
child = node->right;                            //将   替代要删除的那个节点 的节点  对应的右孩子取到
parent = node->parent;                            //将   替代要删除的那个节点 的节点  对应的父节点取到
color = node->color;                            //将   替代要删除的那个节点 的节点  对应的颜色取到，如果颜色为黑色的话，替代完后则会因为缺少黑色
//而破坏平衡
if (child)                                        //如果节点对应的右孩子不为空的话，将右孩子（child）划分到父亲（node的parent）的指向
{
child->parent = parent;
}
if (parent)                                        //判断node属于父亲的哪一边节点，让孩子（child）继承父亲（node）这边的节点（此时parent指向child）
{
if (parent->left == node)
{
parent->left = child;
}
else
{
parent->right = child;
}
}
else                                            //貌似有错误，此时parent一定会有值。可能情况，并发parent已经删除
{
root = child;
}

if (node->parent == old)                        //如果node一开始左孩子就为空，此时将parent下移（因为此时parent是即将删除的那个节点，需要移动）
{
parent = node;
}

node->parent = old->parent;                        //此时node位于old子树下最小的一个节点，让node覆盖old（要删除的节点）的位置（因为一直寻找的是old的右子树）
node->color = old->color;
node->right = old->right;
node->left = old->left;

if (old->parent)                                //使node继承  old的父亲  的指向
{
if (old->parent->left == old)
{
old->parent->left = node;
}
else
{
old->parent->right = node;
}
} 
else                                            //如果要删除的是根节点，则让node充当根节点
{
root = node;
}

old->left->parent = node;                        //使node继承  old左子树  的父亲

if (old->right)                                    //使node继承  old右子树  的父亲
{
old->right->parent = node;
}
}                                                    //此种情况原理：使要删除的节点  中的右子树  中的最小值 覆盖删除的节点的位置（原因：此值比他左子树任意值都大，
else                                                //比右子树任意值都小）。
{
if (!node->left)                                //此情况原理：如果要删除的节点  的左右儿子  有一方为空，那就让删除的节点的父亲指向 要删除的节点的儿子 ，
{                                                //完成删除。
child = node->right;
}
else if (!node->right)
{
child = node->left;
}
parent = node->parent;
color = node->color;                            //将删除节点的颜色取到，如果为黑的话，路径则会因为缺少黑色而造成不平衡

if (child)
{
child->parent = parent;
}
if (parent)
{
if (parent->left == node)
{
parent->left = child;
}
else
{
parent->right = child;
}
}
else                                            //如果删除的是根节点，就让他的儿子充当根节点
{
root = child;
}
}

free(old);                                            //释放删除节点的空间

if (color == BLACK)                                    //如果删除的那个节点的颜色为黑色，会破坏平衡，需要进行自平衡
{
root = rb_erase_rebalance(child, parent, root); //调用rb_erase_rebalance来恢复红黑树性质，从变动过的最下端进行平衡（child和parent的位置）
}

return root;
}
七、红黑树删除四种情况的修复工作：
//----------------------------------------------------------------
//红黑树修复删除的4种情况
//为了表示下述注释的方便，也为了让下述代码与我的倆篇文章相对应，
//x表示要删除的结点（用x替代了曾经要删除的节点，转换成了删除x），*other 表示兄弟结点 //x（表示曾经删除的node的位置，现在的child），w（表示other节点，child的兄弟节点）
//----------------------------------------------------------------
static rb_node_t* rb_erase_rebalance(rb_node_t *node, rb_node_t *parent, rb_node_t *root)
{
rb_node_t *other, *o_left, *o_right;                                   //传进来的node节点（child）的兄弟*other，兄弟左孩子*o_left,*o_right

while ((!node || node->color == BLACK) && node != root)             //当child为黑时（child为叶子节点（NULL为黑），或者它的颜色为黑），并且child不为根节点
{
if (parent->left == node)                                        //当child是他父亲的左节点时
{
other = parent->right;                                        //other为child的兄弟节点，也是曾经 node（这里指x）的兄弟节点

//因为删除了parent左子树的一个黑色节点，所以不平衡

if (other->color == RED)                                       //情况1：x（child）的兄弟w（other）是红色的
{                                                            //此时parent的颜色只能是黑色，进行如下变换
other->color = BLACK;                                      
parent->color = RED;                                           //改变颜色，w（other）变为黑、parent变为红。
root = rb_rotate_left(parent, root);                          //再对parent做一次左旋
other = parent->right;                                      //x（child）的新兄弟other变成了parent的右儿子，曾经的other是现在parent的父节点。
}
if ((!other->left || other->left->color == BLACK) &&
(!other->right || other->right->color == BLACK))  
//情况2：x（child）的兄弟w（other）是黑色，且w（other）的俩个孩子也都是黑色的

            {                                                                 //由于w（other）和w（other）的俩个孩子都是黑色的，则在x和w上得去掉一黑色，
other->color = RED;                                           //于是，兄弟w（other）变为红色。

//此时parent下已经达成平衡
//（但为了防止parent 和 w（other）同为红色进行一下操作（猜测会继续进行判断：类似递归））

                node = parent;                                               //此时将 node 和parent 全部上移
parent = node->parent;  
}
else                                                       
{ 
if (!other->right || other->right->color == BLACK)        //情况3：x（child）的兄弟w（other）是黑色的，右儿子为黑色或者空（NULL为黑），左儿子肯定为红
{
if ((o_left = other->left))                               //w（other）和其左孩子o_left，颜色交换。
{
o_left->color = BLACK;                                //w（other）的左孩子变为黑色
} 
other->color = RED;                                       //w（other）变成红色
root = rb_rotate_right(other, root);                      //再对w（other）进行右旋，此处是为了防止w（other）和parent同为红色。
other = parent->right;                                    //变化后的，父结点的右孩子，作为新的兄弟结点w（other）。
}
//情况4：x的兄弟w（other）是黑色的，右儿子为红，左儿子为黑，此种情况和变换后的情况3相同


//下面是对情况3和4的平衡算法，可直接完成平衡（无需再进行递归）
other->color = parent->color;                                  //把兄弟节点染成当前节点父节点的颜色。
parent->color = BLACK;                                      //把当前节点父节点染成黑色
if (other->right)                                              //因为w（other）右孩子是红
{
other->right->color = BLACK;                              //兄弟节点w（other）右孩子染成黑色
}
root = rb_rotate_left(parent, root);                          //并再做一次左旋
node = root;                                                   //此时这两种情况完成平衡，直接返回根节点；
break;
}
}
//下述情况与上述情况，原理一致。分析略。

else                                                            //此种情况x（child）在是他父亲的右节点
//（此时相当于删除的那个节点与替换的那个节点）是父子关系，才会导致child成为右节点
{
other = parent->left;
if (other->color == RED)                                    //情况1：x（child）的兄弟w（other）是红色的
{                                                                //此时parent的颜色只能是黑色，进行如下变换
other->color = BLACK;                                        //改变颜色，w（other）变为黑、parent变为红。
parent->color = RED;
root = rb_rotate_right(parent, root);                        //再对parent做一次右旋
other = parent->left;                                        //在重新定位w（other）的位置
}
if ((!other->left || other->left->color == BLACK) &&        //情况2：x（child）的兄弟w（other）是黑色，且w（other）的俩个孩子也都是黑色的
(!other->right || other->right->color == BLACK))            //由于w（other）和w（other）的俩个孩子都是黑色的，则在x和w上得去掉一黑色，
{
other->color = RED;                                            //于是，兄弟w（other）变为红色。
node = parent;                                                //此时parent下已经达成平衡
parent = node->parent;                                        //（但为了防止parent 和 w（other）同为红色进行一下操作（猜测会继续进行判断：类似递归））
}                                                                //此时将 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)                                                                //当child为红色时，直接将它改为黑色，就可以完成平衡
{
node->color = BLACK;                                                  //最后将node[上述步骤置为了根结点]，改为黑色。
}  
return root;  //返回root
}

八、测试用例
//主函数
int main()
{
int i, count = 100;
key_t key;
rb_node_t* root = NULL, *node = NULL;

srand(time(NULL));                                                        //srand((unsigned)time(NULL))则使用系统定时/计数器的值作为随机种子
for (i = 1; i < count; ++i)
{
key = rand() % count;                                                //rand函数是随机数生成器，第一次调用rand()之前没有调用srand()，
//那么系统会自动调用srand()，使用同种子相同的数调用 rand()会导致相同的随机数序列被生成
if ((root = rb_insert(key, i, root)))
{
printf("[i = %d] insert key %d success!\n", i, key);
}
else
{
printf("[i = %d] insert key %d error!\n", i, key);
exit(-1);
}

if ((node = rb_search(key, root)))
{
printf("[i = %d] search key %d success!\n", i, key);
}
else
{
printf("[i = %d] search key %d error!\n", i, key);
exit(-1);
}
if (!(i % 10))
{
if ((root = rb_erase(key, root)))
{
printf("[i = %d] erase key %d success\n", i, key);
}
else
{
printf("[i = %d] erase key %d error\n", i, key);
}
}
}

return 0;
}