红黑树--求救
各位大牛：走过路过，请大家给小弟指点指点吧。看算法导论的红黑树看了2周了，连代码都没有完全写出来啊。小弟愚钝啊。请各位指点啊。下面是按照算法导论上的伪代码修改成的C源码。还望各位提点意见啊。
#ifndef _XXX_RED_BLACK_TREE__XXX__#define _XXX_RED_BLACK_TREE__XXX__#define FAIL 0#define OK 1#define EXIST 2typedef int Status;typedef int ElementType;enum Node_Color{RED,BLACK};typedef struct _RedBlack_Tree_Node_{ ElementType data; Node_Color color; struct _RedBlack_Tree_Node_ *pParent; struct _RedBlack_Tree_Node_ *pLchild,*pRchild;}RBTreeNode,*PRBTreeNode;typedef struct RBTree{ PRBTreeNode root; RBTreeNode nillNode;//哨兵}*PRBTree;void LeftRotate(PRBTree T,PRBTreeNode pNode);void RightRotate(PRBTree T,PRBTreeNode pNode);Status RB_Insert(PRBTree T,PRBTreeNode pNode);void RB_Insert_FixUp(PRBTree T,PRBTreeNode pNode);void LeftRotate(PRBTree T,PRBTreeNode pNode){ PRBTreeNode y=pNode->pRchild; pNode->pRchild = y->pLchild; if (y->pLchild!=&(T->nillNode)) { y->pLchild->pParent = pNode; } y->pParent = pNode->pParent; if (pNode->pParent==&(T->nillNode)) { T->root = y; } else if(pNode==(pNode->pParent->pLchild)) pNode->pParent->pLchild = y; else pNode->pParent->pRchild = y; y->pLchild = pNode; pNode->pParent = y;}void RightRotate(PRBTree T,PRBTreeNode pNode){ PRBTreeNode y = pNode->pLchild; pNode->pLchild = y->pRchild; if(y->pRchild!=&(T->nillNode)) y->pRchild->pParent = pNode; y->pParent = pNode->pParent; if (pNode->pParent==&(T->nillNode)) { T->root = y; } else if(pNode==(pNode->pParent->pLchild)) pNode->pParent->pLchild = y; else pNode->pParent->pRchild = y; y->pRchild = pNode; pNode->pParent = y;}Status RB_Insert(PRBTree T,PRBTreeNode pNode){ PRBTreeNode y =& T->nillNode; PRBTreeNode x = T->root; while(x!=&(T->nillNode)) { y = x; if(pNode->data<x->data) x = x->pLchild; else if(pNode->data>x->data) x = x->pRchild; else { printf("This node is already exist!\n"); return EXIST; } } pNode->pParent = y; if(y==&(T->nillNode)) T->root = pNode; else if(pNode->data<y->data) y->pLchild = pNode; else y->pRchild = pNode; pNode->pLchild = &(T->nillNode); pNode->pRchild = &(T->nillNode); pNode->color = RED; RB_Insert_FixUp(T,pNode); return OK;}void RB_Insert_FixUp(PRBTree T,PRBTreeNode pNode){ PRBTreeNode y; while(pNode->pParent->color==RED) { if (pNode->pParent==pNode->pParent->pParent->pLchild) { y = pNode->pParent->pParent->pRchild; if (y->color==RED) { pNode->pParent->color = BLACK; y->color = BLACK; pNode->pParent->pParent->color = RED; pNode = pNode->pParent->pParent; } else { if (pNode==pNode->pParent->pRchild) { pNode = pNode->pParent; LeftRotate(T,pNode); } pNode->pParent->color = BLACK; pNode->pParent->pParent->color = RED; RightRotate(T,pNode->pParent->pParent); } } else//right child { y = pNode->pParent->pParent->pLchild; if (y->color==RED) { pNode->pParent->color = BLACK; y->color = BLACK; pNode->pParent->pParent->color = RED; pNode = pNode->pParent->pParent; } else { if (pNode==pNode->pParent->pRchild) { pNode = pNode->pParent; LeftRotate(T,pNode); } pNode->pParent->color = BLACK; pNode->pParent->pParent->color = RED; RightRotate(T,pNode->pParent->pParent); } } } T->root->color = BLACK;}void Visited(PRBTreeNode point,PRBTreeNode pnillNode){ if(point->pLchild !=pnillNode) Visited(point->pLchild,pnillNode); printf("%d (%s) parent:%d,%c\n",point->data,(point->color==RED?"Red":"Black"),point->pParent->data,(point->pParent->pLchild==point?'L':'R')); if(point->pRchild != pnillNode) Visited(point->pRchild,pnillNode);}void Inorder(PRBTree T){ Visited(T->root,&(T->nillNode));}void freeNode(PRBTreeNode pt,PRBTreeNode pnillNode){ if(pt->pLchild!=pnillNode) freeNode(pt->pLchild,pnillNode); if(pt->pRchild!=pnillNode) freeNode(pt->pRchild,pnillNode); free(pt);}void DestroyTree(PRBTree T){ freeNode(T->root,&(T->nillNode));}#endif
void RB_Insert_FixUp(PRBTree T,PRBTreeNode pNode){ PRBTreeNode y; while(pNode->pParent->color==RED) { if (pNode->pParent==pNode->pParent->pParent->pLchild) { y = pNode->pParent->pParent->pRchild; if (y->color==RED) { pNode->pParent->color = BLACK; y->color = BLACK; pNode->pParent->pParent->color = RED; pNode = pNode->pParent->pParent; } else { if (pNode==pNode->pParent->pRchild) { pNode = pNode->pParent; LeftRotate(T,pNode); } pNode->pParent->color = BLACK; pNode->pParent->pParent->color = RED; RightRotate(T,pNode->pParent->pParent); } } else//违规的是右子树节点 { y = pNode->pParent->pParent->pLchild;//叔叔节点 if (y->color==RED)//如果叔叔是红的，那么就按照和左子树一样的规则处理 { pNode->pParent->color = BLACK; y->color = BLACK; pNode->pParent->pParent->color = RED; pNode = pNode->pParent->pParent; } else//叔叔不是红的 { if (pNode==pNode->pParent->pLchild)//当前节点是父节点的左子树，需要把它转成右子树来处理 { pNode = pNode->pParent; RightRotate(T,pNode); } //处理右子树，只需要进行旋转就可以了 pNode->pParent->color = BLACK; pNode->pParent->pParent->color = RED; LeftRotate(T,pNode->pParent->pParent); } } } T->root->color = BLACK;}