红黑树

正如在CLRS中定义的那样（译者： CLRS指的是一本著名的算法书Introduction to Algorithms，中文名应该叫算法导论，CLRS是该书作者Cormen, Leiserson, Rivest and Stein的首字母缩写），一棵红黑树是指一棵满足下述性质的二叉搜索树（BST, binary search tree）：

1. 每个结点或者为黑色或者为红色。
2. 根结点为黑色。
3. 每个叶结点(实际上就是NULL指针)都是黑色的。
4. 如果一个结点是红色的，那么它的两个子节点都是黑色的（也就是说，不能有两个相邻的红色结点）。
5. 对于每个结点，从该结点到其所有子孙叶结点的路径中所包含的黑色结点数量必须相同。

数据项只能存储在内部结点中（internal node）。我们所指的"叶结点"在其父结点中可能仅仅用一个NULL指针表示，但是将它也看作一个实际的结点有助于描述红黑树的插入与删除算法，叶结点一律为黑色。

/*******************************************************************************
文件： rbtree.h
说明： 本文件是REFS文件系统应用的红黑树算法的例程，如果要正确使用本程序，需要提
       供一个哨兵NIL,另在结构体中U16和U8需要定义。哨兵节点的定义如下：
       NIL = malloc(sizeof(rbtreeNode));
       NIL->color = BLACK;
*******************************************************************************/

#include "../config/type.h"

enum color
{    BLACK,RED   };
typedef struct _rbtreeNode
{
    U16 key;
    U8  color;
    struct _rbtreeNode  *left;
    struct _rbtreeNode  *right;
    struct _rbtreeNode  *p;
} rbtreeNode;

void rbtLeftRotate(rbtreeNode **root,rbtreeNode *xNode);
void rbtRightRotate(rbtreeNode **root,rbtreeNode *xNode);

void rbtInsertFixup(rbtreeNode **root,rbtreeNode *zNode);
void rbtDeleteFixup(rbtreeNode **root, rbtreeNode *xNode);

rbtreeNode *rbtMinimum(rbtreeNode *xNode);
rbtreeNode *rbtMaximum(rbtreeNode *xNode);

rbtreeNode *rbtPredecessor(rbtreeNode *xNode);
rbtreeNode *rbtSuccessor(rbtreeNode *xNode);

void rbtInsert(rbtreeNode **root,rbtreeNode *zNode);
void rbtDelete(rbtreeNode **root, rbtreeNode *zNode);

/*******************************************************************************
文件： rbtree.c
说明： 本文件是REFS文件系统应用的红黑树算法的例程，如果要正确使用本程序，需要提
       供一个哨兵NIL,另在结构体中U16和U8需要定义。哨兵节点的定义如下：
       NIL = malloc(sizeof(rbtreeNode));
       NIL->color = BLACK;
*******************************************************************************/
#include "rbtree.h"

rbtreeNode *NIL;

void rbtLeftRotate(rbtreeNode **root,rbtreeNode *xNode)
{
    rbtreeNode *yNode = xNode->right;
    xNode->right = yNode->left;
    if(yNode->left!=NIL)
    {   yNode->left->p = xNode; }
    yNode->p = xNode->p;
    if(xNode->p ==NIL)
    {   *root = yNode;   }
    else if(xNode == xNode->p->left)
    {   xNode->p->left = yNode; }
    else
    {   xNode->p->right = yNode;    }
    yNode->left = xNode;
    xNode->p = yNode;
    return;
}
void rbtRightRotate(rbtreeNode **root,rbtreeNode *xNode)
{
    rbtreeNode *yNode = xNode->left;
    xNode->left = yNode->right;
    if(yNode->right!=NIL)
    {   yNode->right->p = xNode; }
    yNode->p = xNode->p;
    if(xNode->p ==NIL)
    {   *root = yNode;   }
    else if(xNode == xNode->p->right)
    {   xNode->p->right = yNode; }
    else
    {   xNode->p->left = yNode;    }
    yNode->right = xNode;
    xNode->p = yNode;
    return;
}

void rbtInsertFixup(rbtreeNode **root,rbtreeNode *zNode)
{
    rbtreeNode *yNode;
    while((zNode!=*root)&&(zNode->p->color == RED))
    {
        if(zNode->p == zNode->p->p->left)
        {
            yNode = zNode->p->p->right;
            if(yNode->color == RED) /*  CASE 1  */
            {  
                zNode->p->color = BLACK;
                yNode->color = BLACK;
                zNode->p->p->color = RED;
                zNode = zNode->p->p;
            }
            else
            {
                if(zNode == zNode->p->right)   /*  CASE 2  */
                {
                    zNode = zNode->p;
                    rbtLeftRotate(root, zNode);
                }
                zNode->p->color = BLACK;      /*   CASE 3 */
                zNode->p->p->color = RED;
                rbtRightRotate(root, zNode->p->p);
            }
        }
        else
        {
            yNode = zNode->p->p->left;
            if(yNode->color == RED) /*  CASE 1  */
            {  
                zNode->p->color = BLACK;
                yNode->color = BLACK;
                zNode->p->p->color = RED;
                zNode = zNode->p->p;
            }
            else
            {
                if(zNode == zNode->p->left)   /*  CASE 2  */
                {
                    zNode = zNode->p;
                    rbtRightRotate(root, zNode);
                }
                zNode->p->color = BLACK;      /*   CASE 3 */
                zNode->p->p->color = RED;
                rbtLeftRotate(root, zNode->p->p);
            }
        }
    }
    (*root)->color = BLACK;
}
void rbtInsert(rbtreeNode **root,rbtreeNode *zNode)
{
    rbtreeNode *yNode = NIL;
    rbtreeNode *xNode = *root;
    while(xNode != NIL)
    {
        yNode = xNode;
        if(zNode->key < xNode->key)
        {   xNode = xNode->left;    }
        else
        {   xNode = xNode->right;   }
    }
    zNode->p = yNode;
    if(yNode == NIL)
    {   *root = zNode;   }
    else if(zNode->key < yNode->key)
    {   yNode->left = zNode;    }
    else
    {   yNode->right = zNode;   }
    zNode->left = NIL;
    zNode->right = NIL;
    zNode->color = RED;
    rbtInsertFixup(root, zNode);
   
}

rbtreeNode *rbtMinimum(rbtreeNode *xNode)
{
    while(xNode->left != NIL)
    {   xNode = xNode->left;    }
    return xNode;
}
rbtreeNode *rbtMaximum(rbtreeNode *xNode)
{
    while(xNode->right != NIL)
    {   xNode = xNode->right;    }
    return xNode;
}
rbtreeNode *rbtSuccessor(rbtreeNode *xNode)
{
    rbtreeNode *yNode;
    if(xNode->right != NIL)
    {   return rbtMinimum(xNode->right);    }
    yNode = xNode->p;
    while((yNode != NIL)&&(xNode == yNode->right))
    {
        xNode = yNode;
        yNode = xNode->p;
    }
    return yNode;
}
rbtreeNode *rbtPredecessor(rbtreeNode *xNode);
{
    rbtreeNode *yNode;
    if(xNode->left != NIL)
    {   return rbtMinimum(xNode->right);    }
    yNode = xNode->p;
    while((yNode != NIL)&&(xNode == yNode->left))
    {
        xNode = yNode;
        yNode = xNode->p;
    }
    return yNode;
}
void rbtDeleteFixup(rbtreeNode **root, rbtreeNode *xNode)
{
    rbtreeNode *wNode;
    while((xNode != *root)&&(xNode->color == BLACK))
    {
        if(xNode == xNode->p->left)
        {
            wNode = xNode->p->right;
            if(wNode->color == RED) /*  CASE 1  */
            {
                wNode->color = BLACK;
                xNode->p->color = RED;
                rbtLeftRotate(root, xNode->p);
                wNode = xNode->p->right;
            }
            if((wNode->left->color == BLACK)&&(wNode->right->color == BLACK))
            {                       /*  CASE 2  */
                wNode->color = RED;
                xNode = xNode->p;
            }
            else
            {
                if(wNode->right->color == BLACK)    /*  CASE 3  */
                {
                    wNode->left->color = BLACK;
                    wNode->color = RED;
                    rbtRightRotate(root, wNode);
                    wNode = xNode->p->right;
                }
                wNode->color = xNode->p->color; /*  CASE 4  */
                xNode->p->color = BLACK;
                wNode->right->color = BLACK;
                rbtLeftRotate(root, xNode->p);
                xNode = *root;
            }
        }
        else
        {
            wNode = xNode->p->left;
            if(wNode->color == RED) /*  CASE 1  */
            {
                wNode->color = BLACK;
                xNode->p->color = RED;
                rbtRightRotate(root, xNode->p);
                wNode = xNode->p->left;
            }
            if((wNode->right->color == BLACK)&&(wNode->left->color == BLACK))
            {                       /*  CASE 2  */
                wNode->color = RED;
                xNode = xNode->p;
            }
            else
            {
                if(wNode->left->color == BLACK) /*  CASE 3  */
                {
                    wNode->right->color = BLACK;
                    wNode->color = RED;
                    rbtLeftRotate(root, wNode);
                    wNode = xNode->p->left;
                }
                wNode->color = xNode->p->color; /*  CASE 4  */
                xNode->p->color = BLACK;
                wNode->left->color = BLACK;
                rbtRightRotate(root, xNode->p);
                xNode = *root;
            }
        }
    }
    xNode->color = BLACK;
}
void rbtDelete(rbtreeNode **root, rbtreeNode *zNode)
{
    rbtreeNode *xNode,*yNode;
    if((zNode->left==NIL)||(zNode->right==NIL))
    {   yNode = zNode;  }
    else
    {   yNode = rbtSuccessor(zNode);    }
    if(yNode->left != NIL)
    {   xNode = yNode->left;    }
    else
    {   xNode = yNode->right;   }
    xNode->p = yNode->p;
    if(yNode->p == NIL)
    {   *root =xNode;   }
    else if(yNode == yNode->p->left)
    {   yNode->p->left = xNode; }
    else
    {   yNode->p->right = xNode;    }
    if(yNode != zNode)
    {   zNode->key = yNode->key;    }
    if(yNode->color == BLACK)
    {   rbtDeleteFixup(root, xNode);   }
}