学步园

接着算法联系五，实现了红黑树的节点删除功能。

补充了五个函数，这里主要将 删除 和 删除修正两个函数给出，其它的就十分简单了。

//删除

RBNode* RBDelete(RBNode** proot, RBNode* pnode, RBNode* pguardNode);

//删除修正

void RBDeleteFixup(RBNode** proot, RBNode* pnode, RBNode* pguardNode);

//返回以节点为根的最小元素

RBNode* TreeMinimum(RBNode* pnode, RBNode* pguardNode);

//返回以节点为根的最大元素

RBNode* TreeMaxmum(RBNode* pnode, RBNode* pguardNode);

//返回节点的后继

RBNode* TreeSuccessor(RBNode* pnode, RBNode* pguardNode);

//删除<br /> RBNode* RBDelete(RBNode** proot, RBNode* pnode, RBNode* pguardNode)<br /> {<br /> RBNode* y;<br /> RBNode* x;<br /> if ( pnode->pLeft == pguardNode || pnode->pRight == pguardNode )<br /> {<br /> y = pnode;<br /> }<br /> else<br /> {<br /> y = TreeSuccessor(pnode,pguardNode);<br /> }<br /> if ( y->pLeft != pguardNode )<br /> {<br /> x = y->pLeft;<br /> }<br /> else<br /> {<br /> x = y->pRight;<br /> }<br /> x->pParent = y->pParent;<br /> if ( y->pParent == pguardNode )<br /> {<br /> *proot = x;<br /> }<br /> else<br /> {<br /> if ( y == y->pParent->pLeft )<br /> {<br /> y->pParent->pLeft = x;<br /> }<br /> else<br /> {<br /> y->pParent->pRight = x;<br /> }<br /> }<br /> if ( y != pnode )<br /> {<br /> pnode->key = y->key; //*这里没有将y的颜色赋值给pnode，这一点十分重要*//<br /> }<br /> if ( y->color == BLACK )<br /> {<br /> RBDeleteFixup( proot,x,pguardNode );<br /> }<br /> return y;<br /> }<br /> //删除修正<br /> void RBDeleteFixup(RBNode** proot, RBNode* px, RBNode* pguardNode)<br /> {<br /> RBNode* w;<br /> while( px != *proot && px->color == BLACK && px != pguardNode )<br /> {<br /> if ( px == px->pParent->pLeft ) //case1 px的兄弟是红色的<br /> {<br /> w = px->pParent->pRight;<br /> if ( w->color == RED )<br /> {<br /> w->color = BLACK;<br /> px->pParent->color = RED;<br /> LeftRotate( proot, px->pParent, pguardNode );<br /> w = px->pParent->pRight;<br /> }<br /> if ( w->pLeft->color == BLACK && w->pRight->color == BLACK )<br /> { // case2 px的兄弟w是黑色的，并且w的两个孩子都是黑色的<br /> w->color = RED;<br /> px = px->pParent;<br /> }<br /> else<br /> {<br /> if ( w->pRight->color == BLACK )<br /> {<br /> //case3 px的兄弟w是黑色的,w的左孩子是红色的，右孩子是黑色的<br /> w->pLeft->color = BLACK;<br /> w->color = RED;<br /> RightRotate(proot,w,pguardNode);<br /> w = px->pParent->pRight;<br /> }<br /> w->color = px->pParent->color;<br /> px->pParent->color = BLACK;<br /> w->pRight->color = BLACK;<br /> LeftRotate(proot,px->pParent,pguardNode);<br /> px = *proot;<br /> }<br /> }<br /> else // px == px->pParent->pRight<br /> {<br /> w = px->pParent->pLeft;<br /> if ( w->color == RED )<br /> {<br /> w->color = BLACK;<br /> px->pParent->color = RED;<br /> RightRotate( proot, px->pParent, pguardNode );<br /> w = px->pParent->pLeft;<br /> }<br /> if ( w->pLeft->color == BLACK && w->pRight->color == BLACK )<br /> {<br /> w->color = RED;<br /> px = px->pParent;<br /> }<br /> else<br /> {<br /> if ( w->pLeft->color == BLACK )<br /> {<br /> w->pRight->color = BLACK;<br /> w->color = RED;<br /> LeftRotate( proot, w, pguardNode );<br /> w = px->pParent->pLeft;<br /> }<br /> w->color = px->pParent->color;<br /> px->pParent->color = BLACK;<br /> w->pLeft->color = BLACK;<br /> RightRotate(proot, px->pParent, pguardNode );<br /> px = *proot;<br /> }<br /> }</p> <p> }//end while loop<br /> px->color = BLACK;<br /> }