原创 红黑树算法C实现

/*******************************************************************************
文件： 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);   }
}