红黑树的基本操作

2024-11-09 技术教程

rbTree.h

#ifndefRBTREE_H_INCLUDED#defineRBTREE_H_INCLUDED#undefNULL#ifdefined(__cplusplus)#defineNULL0#else#defineNULL((void*)0)#endif/*红黑树是二叉查找树的一种且具有以下性质：1：每个节点要么是红色要么是黑色2：根节点和叶子节点都是黑色的3：如果一个结点是红的，那么它的两个儿子都是黑的4：每一条路径上黑节点的数目都相同*//*左旋：right是node的右孩子。-----条件旋转之后node成为right的左孩子。right的左孩子成为node的右孩子。node的左孩子不变，right的右孩子不变。noderight/\==>/\arightnodey/\/\byab*//*右旋：nodeleft/\/\lefty==>anode/\/\abby父节点的左孩子才能右旋右旋后父节点和左子树关系交换。父节点变成左孩子的右孩子左孩子的左孩子（a）位置不变父节点的右孩子（y）位置不变*/typedefenumen_color{RED=0,BLK}COLOR;typedefstructtag_rb_t{structtag_rb_t*pstLt;//左孩子节点structtag_rb_t*pstRt;//右孩子节点structtag_rb_t*pstPt;//双亲节点COLORcolor;//节点的颜色intkey;//key}rb_t;//左旋voidrb_LeftRotate(rb_t*pNode,rb_t**ppRoot);//右旋voidrb_RightRotate(rb_t*pNode,rb_t**ppRoot);//插入时修正左子树voidrb_InsertFixupLeft(rb_t*pGrand,rb_t**pParent,rb_t*pUncle,rb_t**ppNode,rb_t**ppRoot);//插入时修正右子树voidrb_InsertFixupRight(rb_t*pGrand,rb_t**pParent,rb_t*pUncle,rb_t**ppNode,rb_t**ppRoot);//插入时修正左右子树的入口voidrb_InsertFixup(rb_t*pNode,rb_t**ppRoot);//插入intrb_Insert(rb_t*pNode,rb_t**ppRoot);//删除节点voidrb_Delete(rb_t*pDel,rb_t**ppRoot);//查找一个节点rb_t*rb_Search(intkey);#endif//RBTREE_H_INCLUDED

rbTree.c

#include"stdafx.h"#include"rbTree.h"#defineRETURN_ERR-1#defineRETURN_OK0/*****************************************************************************函数功能：红黑树插入节点时左旋函数入参：rb_t*pNode左旋操作前的父节点函数出参：rb_t**ppRoot红黑树的根节点，在左旋过程中有可能需要改变根节点的位置函数返回值：无其他：左旋操作参看头文件中的说明******************************************************************************/voidrb_LeftRotate(rb_t*pNode,rb_t**ppRoot){//pNode的右孩子。左旋发生在父节点（pNode）和右孩子（ppstRt）之间。左旋完成之后ppstRt成为父节点，pNode成为左孩子rb_t*ppstRt=pNode->pstRt;//ppstRt的左孩子需要成为pNode的右孩子，pNode的左孩子不变，ppstRt的右孩子不变。if(NULL!=(pNode->pstRt=ppstRt->pstLt)){ppstRt->pstLt->pstPt=pNode;//ppstRt的左孩子成为node的右孩子，所以ppstRt的左孩子的父节点需要由ppstRt修改成pNode}ppstRt->pstLt=pNode;//交换pNode和ppstRt的父子关系。if(NULL!=(ppstRt->pstPt=pNode->pstPt))//修改父节点。如果不为空说明pNode不是红黑树的根节点{//左旋后，未变动的节点的父节点也需要修改if(pNode==pNode->pstPt->pstRt){pNode->pstPt->pstRt=ppstRt;}else{pNode->pstPt->pstLt=ppstRt;}}else{*ppRoot=ppstRt;//pNode是红黑树的根节点，此时根节点需要修改成为左旋前pNode的右孩子}pNode->pstPt=ppstRt;return;}/*****************************************************************************函数功能：红黑树插入节点时右旋函数入参：rb_t*pNode右旋前的父节点函数出参：rb_t**ppRoot红黑树的根节点函数返回值：无其他：右旋操作参看头文件中的说明******************************************************************************/voidrb_RightRotate(rb_t*pNode,rb_t**ppRoot){rb_t*ppstLt=pNode->pstLt;if(NULL!=(pNode->pstLt=ppstLt->pstRt)){ppstLt->pstRt->pstRt=pNode;}ppstLt->pstRt=pNode;if(NULL!=(ppstLt->pstPt=pNode->pstPt)){if(pNode==pNode->pstPt->pstRt){pNode->pstPt->pstRt=ppstLt;}else{pNode->pstPt->pstLt=ppstLt;}}else{*ppRoot=ppstLt;}pNode->pstPt=ppstLt;return;}/*****************************************************************************函数功能：红黑树插入节点时调整左子树函数入参：rb_t*pGrand,祖父节点rb_t**ppstPt,父节点rb_t**pUncle,父节点的兄弟节点rb_t**ppNode,待调整的节点rb_t**ppRoot红黑树的根节点函数出参：无函数返回值：无其他：******************************************************************************/voidrb_InsertFixupLeft(rb_t*pGrand,rb_t**pppstPt,rb_t*pUncle,rb_t**ppNode,rb_t**ppRoot){rb_t*pNodeTmp=NULL;boolIsTrue=false;IsTrue=((NULL!=pUncle)&&(RED==pUncle->color));//uncle存在且是红色if(IsTrue){pUncle->color=BLK;(*pppstPt)->color=BLK;pGrand->color=RED;(*ppNode)=pGrand;//将祖父当做新增结点z，指针z上移俩层，且着为红色。return;}//uncle不存在，或者是黑色的if((*ppNode)==(*pppstPt)->pstRt)//pNode是右孩子，左旋的条件{rb_LeftRotate(*pppstPt,ppRoot);pNodeTmp=*pppstPt;*pppstPt=*ppNode;*ppNode=pNodeTmp;}//uncle是黑色的，此时pNode成为了左孩子。(*pppstPt)->color=BLK;pGrand->color=RED;rb_RightRotate(pGrand,ppRoot);return;}/*****************************************************************************函数功能：红黑树插入节点时调整右子树函数入参：rb_t*pGrand,祖父节点rb_t**ppstPt,父节点rb_t**pUncle,父节点的兄弟节点rb_t**ppNode,待调整的节点rb_t**ppRoot红黑树的根节点函数出参：无函数返回值：无其他：******************************************************************************/voidrb_InsertFixupRight(rb_t*pGrand,rb_t**pppstPt,rb_t*pUncle,rb_t**ppNode,rb_t**ppRoot){rb_t*pNodeTmp=NULL;boolIsTrue;IsTrue=((NULL!=pUncle)&&(RED==pUncle->color));if(IsTrue){pUncle->color=BLK;(*pppstPt)->color=BLK;pGrand->color=RED;(*ppNode)=pGrand;return;}if((*ppNode)==(*pppstPt)->pstLt){rb_RightRotate(*pppstPt,ppRoot);pNodeTmp=*pppstPt;*pppstPt=*ppNode;*ppNode=pNodeTmp;}(*pppstPt)->color=BLK;pGrand->color=RED;rb_LeftRotate(pGrand,ppRoot);return;}/*****************************************************************************函数功能：红黑树插入节点时调整子树函数入参：rb_t*pNode,带插入节点rb_t**ppRoot红黑树的根节点函数出参：无函数返回值：无其他：******************************************************************************/voidrb_InsertFixup(rb_t*pNode,rb_t**ppRoot){rb_t*ppstPt=NULL;rb_t*pGrand=NULL;rb_t*pUncle=NULL;while((NULL!=(ppstPt=pNode->pstPt))&&(RED==ppstPt->color)){//ppstPt是pNode的父节点，且父节点是红色的pGrand=ppstPt->pstPt;if(ppstPt==pGrand->pstLt){pUncle=pGrand->pstRt;rb_InsertFixupLeft(pGrand,&ppstPt,pUncle,&pNode,ppRoot);}else{pUncle=pGrand->pstLt;rb_InsertFixupRight(pGrand,&ppstPt,pUncle,&pNode,ppRoot);}}(*ppRoot)->color=BLK;return;}/*****************************************************************************函数功能：红黑树插入节点函数入参：rb_t*pNode,插入节点rb_t**ppRoot红黑树的根节点函数出参：无函数返回值：无其他：******************************************************************************/intrb_Insert(rb_t*pNode,rb_t**ppRoot){rb_t**ppNodeTmp=ppRoot;rb_t*ppstPt=NULL;//二叉查找树插入方法相同while(NULL!=(*ppRoot)){ppstPt=*ppNodeTmp;if(pNode->key>(*ppNodeTmp)->key){ppNodeTmp=&((*ppNodeTmp)->pstRt);}elseif(pNode->key<(*ppNodeTmp)->key){ppNodeTmp=&((*ppNodeTmp)->pstLt);}else{returnRETURN_ERR;}}*ppNodeTmp=pNode;pNode->pstPt=ppstPt;pNode->color=RED;pNode->pstLt=NULL;pNode->pstRt=NULL;rb_InsertFixup(pNode,ppRoot);returnRETURN_OK;}/*****************************************************************************函数功能：根据key，查找节点函数入参：intkeyrb_t*pRoot红黑树的根节点函数出参：无函数返回值：key对应的节点其他：******************************************************************************/rb_t*rb_Search(intkey,rb_t*pRoot){rb_t*pTmp=pRoot;while(NULL!=pTmp){if(pTmp->key<key){pTmp=pTmp->pstLt;}elseif(pTmp->key>key){pTmp=pTmp->pstRt;}else{returnpTmp;}}returnNULL;}voidrb_DeletepDelHaveTwoChildren(rb_t*pDel,rb_t**ppRoot,COLOR*peColor,rb_t**ppDelNxtChild,rb_t**ppDelNxtParent){rb_t*pTmp=pDel;rb_t*pDelNext=NULL;//待删除节点的后继节点rb_t*pDelNxtChild=NULL;//后继节点的右孩子rb_t*pDelNxtParent=NULL;//后继节点的父节点//查找pDel的后继pDelNext=pDel->pstRt;pDelNext=pDelNext->pstLt;while(NULL!=pDelNext){pDelNext=pDelNext->pstLt;}pDelNxtChild=pDelNext->pstRt;pDelNxtParent=pDelNext->pstPt;*peColor=pDelNext->color;//后续节点存在右孩子if(NULL!=pDelNxtChild){pDelNxtChild->pstPt=pDelNxtParent;}if(NULL!=pDelNxtParent){if(pDelNxtParent->pstLt==pDelNext){pDelNxtParent->pstLt=pDelNxtChild;}else{pDelNxtParent->pstRt=pDelNxtChild;}}else//后续节点为空，说明待删除的节点时根节点，需要修改根节点{*ppRoot=pDelNxtChild;}if(pDelNext->pstPt==pTmp){pDelNxtParent=pDelNext;}pDelNext->pstPt=pTmp->pstPt;pDelNext->color=pTmp->color;pDelNext->pstRt=pTmp->pstRt;pDelNext->pstLt=pTmp->pstLt;if(pTmp->pstPt){if(pTmp->pstPt->pstLt==pTmp){pTmp->pstPt->pstLt=pDelNext;}else{pTmp->pstPt->pstRt=pDelNext;}}else{*ppRoot=pDel;}pTmp->pstLt->pstPt=pDel;if(pTmp->pstRt){pTmp->pstRt->pstPt=pDel;}*ppDelNxtChild=pDelNxtChild;*ppDelNxtParent=pDelNxtParent;return;}voidrb_DeletepDelNoTwoChild(rb_t*pDel,rb_t**ppRoot,COLOR*peColor,rb_t**ppDelNxtChild,rb_t**ppDelNxtParent){rb_t*pTmp=pDel;rb_t*pDelNext=NULL;//待删除节点的后继节点rb_t*pDelNxtChild=NULL;//后继节点的孩子rb_t*pDelNxtParent=NULL;//后继节点的父节点//只有一个孩子的情况if(NULL!=pDel->pstLt){pDelNxtChild=pDel->pstRt;}elseif(NULL!=pDel->pstRt){pDelNxtChild=pDel->pstLt;}pDelNxtParent=pDel->pstPt;*peColor=pDel->color;//修改待删除节点的孩子节点的父节点if(pDelNxtChild){pDelNxtChild->pstPt=pDelNxtParent;}if(pDelNxtParent){if(pDelNxtParent->pstLt==pDel){pDelNxtParent->pstLt=pDelNxtChild;}else{pDelNxtParent->pstRt=pDelNxtChild;}}else//父节点为空说明待删除的节点是根节点，需要修改根节点{*ppRoot=pDelNxtChild;}*ppDelNxtChild=pDelNxtChild;*ppDelNxtParent=pDelNxtParent;return;}voidrb_DeleteNode(rb_t*pDel,rb_t**ppRoot,COLOR*peColor,rb_t**ppDelNxtChild,rb_t**ppDelNxtParent){//待删除的节点既有左孩子又有右孩子if((NULL!=pDel->pstLt)&&(NULL!=pDel->pstRt)){rb_DeletepDelHaveTwoChildren(pDel,ppRoot,peColor,ppDelNxtChild,ppDelNxtParent);}else{rb_DeletepDelNoTwoChild(pDel,ppRoot,peColor,ppDelNxtChild,ppDelNxtParent);}return;}voidrb_DelFixupLeft(rb_t**ppDelNxtChild,rb_t*pDelNxtParent,rb_t**ppRoot){rb_t*pTmp;rb_t*pTmpLeft;pTmp=pDelNxtParent->pstRt;if(pTmp->color==RED)//情况1：待删除节点的兄弟pTmp是红色的{pTmp->color=BLK;pDelNxtParent->color=RED;//上俩行，改变颜色，pTmp->黑、待删除的节点的父节点->红。rb_LeftRotate(pDelNxtParent,ppRoot);//再对待删除的节点的父节点做一次左旋pTmp=pDelNxtParent->pstRt;//待删除节点的新兄弟neww是旋转之前w的某个孩子。其实就是左旋后的效果。}if((!pTmp->pstLt||pTmp->pstLt->color==BLK)&&(!pTmp->pstRt||pTmp->pstRt->color==BLK))//情况2：x的兄弟w是黑色，且w的俩个孩子也都是黑色的{//由于w和w的俩个孩子都是黑色的，则在x和w上得去掉一黑色，pTmp->color=RED;//于是，兄弟w变为红色。*ppDelNxtChild=pDelNxtParent;//p[x]为新结点xpDelNxtParent=(*ppDelNxtChild)->pstPt;//x<-p[x]}else//情况3：x的兄弟w是黑色的，且，w的左孩子是红色，右孩子为黑色。{if(!pTmp->pstRt||pTmp->pstRt->color==BLK){if((pTmpLeft=pTmp->pstLt))//w和其左孩子pstLt[w]，颜色交换。{pTmpLeft->color=BLK;//w的左孩子变为由黑->红色}pTmp->color=RED;//w由黑->红rb_RightRotate(pTmp,ppRoot);//再对w进行右旋，从而红黑性质恢复。pTmp=pDelNxtParent->pstRt;//变化后的，父结点的右孩子，作为新的兄弟结点}//情况4：x的兄弟w是黑色的pTmp->color=pDelNxtParent->color;//把兄弟节点染成当前节点父节点的颜色。pDelNxtParent->color=BLK;//把当前节点父节点染成黑色if(pTmp->pstRt)//且w的右孩子是红{pTmp->pstRt->color=BLK;//兄弟节点w右孩子染成黑色}rb_LeftRotate(pDelNxtParent,ppRoot);//并再做一次左旋*ppDelNxtChild=*ppRoot;//并把x置为根。return;}return;}voidrb_DelFixupRight(rb_t**ppDelNxtChild,rb_t*pDelNxtParent,rb_t**ppRoot){rb_t*pTmp;rb_t*pTmpRight;pTmp=pDelNxtParent->pstLt;if(pTmp->color==RED){pTmp->color=BLK;pDelNxtParent->color=RED;rb_RightRotate(pDelNxtParent,ppRoot);pTmp=pDelNxtParent->pstLt;}if((!pTmp->pstLt||pTmp->pstLt->color==BLK)&&(!pTmp->pstRt||pTmp->pstRt->color==BLK)){pTmp->color=RED;*ppDelNxtChild=pDelNxtParent;pDelNxtParent=(*ppDelNxtChild)->pstPt;}else{if(!pTmp->pstLt||pTmp->pstLt->color==BLK){if((pTmpRight=pTmp->pstRt)){pTmpRight->color=BLK;}pTmp->color=RED;rb_LeftRotate(pTmp,ppRoot);pTmp=pDelNxtParent->pstLt;}pTmp->color=pDelNxtParent->color;pDelNxtParent->color=BLK;if(pTmp->pstLt){pTmp->pstLt->color=BLK;}rb_RightRotate(pDelNxtParent,ppRoot);*ppDelNxtChild=*ppRoot;return;}return;}voidrb_DelFixup(rb_t*pDelNxtChild,rb_t*pDelNxtParent,rb_t**ppRoot){while((!pDelNxtChild||pDelNxtChild->color==BLK)&&pDelNxtChild!=*ppRoot){if(pDelNxtParent->pstLt==pDelNxtChild){rb_DelFixupLeft(&pDelNxtChild,pDelNxtParent,ppRoot);}else{rb_DelFixupRight(&pDelNxtChild,pDelNxtParent,ppRoot);}}if(pDelNxtChild){pDelNxtChild->color=BLK;}return;}/*****************************************************************************函数功能：将一个节点从红黑树中删除（只是将节点从红黑树中摘掉，节点的内存不会再本函数中释放）函数入参：rb_t*pDelrb_t**ppRoot函数出参：无函数返回值：无特别说明：pDel的内存需要在调用此函数之后，手动释放******************************************************************************/voidrb_Delete(rb_t*pDel,rb_t**ppRoot){COLORcolor;rb_t*pDelNxtChild=NULL;rb_t*pDelNxtParent=NULL;//将待删除的节点从红黑树中摘掉rb_DeleteNode(pDel,ppRoot,&color,&pDelNxtChild,&pDelNxtParent);if(color==BLK){rb_DelFixup(pDelNxtChild,pDelNxtParent,ppRoot);//调用rb_erase_rebalance来恢复红黑树性质}return;}