【數(shù)據(jù)結(jié)構(gòu)】動態(tài)選擇求第k小元素問題

東北大學(xué)信息科學(xué)與工程學(xué)院數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告題目動態(tài)選擇求第k小元素問題課題組長肖瑤課題組成員陳果張帥專業(yè)名稱計(jì)算機(jī)科學(xué)與技術(shù)班級計(jì)1307指導(dǎo)教師楊雷課程設(shè)計(jì)任務(wù)書題目：B12、動態(tài)選擇求第k小元素問題問題描述：一棵紅黑樹本身就是一棵二叉排序樹。紅黑樹中的結(jié)點(diǎn)顏色是黑色或紅色。從紅黑樹的根結(jié)點(diǎn)到葉子結(jié)點(diǎn)的路徑上的黑色結(jié)點(diǎn)數(shù)目相同，最短的路徑就是所有結(jié)點(diǎn)都是黑色。集合中的元素是動態(tài)構(gòu)成的。要求對集合中的n個(gè)元素求解第k小的元素。設(shè)計(jì)要求：設(shè)計(jì)應(yīng)用紅黑平衡二叉樹實(shí)現(xiàn)動態(tài)查找第k小的元素。(1)實(shí)現(xiàn)動態(tài)查找表的三種基本功能：查找、插入、刪除。(2)實(shí)現(xiàn)紅黑平衡二叉樹的動態(tài)查找第k小的元素。(3)可以考慮與快速排序方法的實(shí)現(xiàn)做比較。指導(dǎo)教師簽字：課題程序設(shè)計(jì)分工學(xué)號姓名··設(shè)計(jì)函數(shù)原型、類功能說明20133995肖瑤PRBTreeNodeRBTREEDELETE(PRBTreepTree.PRBTreeNodepDel)FIXUPRBAFTERDELETE(PRBTreepTree,PRBTreeNodepNode)voidRBTREEINSERT(PRBTreepTree,PRBTreeNodepNode)FIXUPRBAFTERINSERT(PRBTreepTree,PRBTreeNodepNode)紅黑樹的節(jié)點(diǎn)刪除在紅黑樹刪除動作后進(jìn)行紅黑性質(zhì)恢復(fù)紅黑樹的節(jié)點(diǎn)插入在紅黑樹插入動作后進(jìn)行紅黑性質(zhì)恢復(fù)20134002陳果PRBTreeNodeRBTREEMAX(PRBTreeNodepRoot)PRBTreeNodeRBTREEMIN(PRBTreeNodepRoot)PRBTreeNodeRBTREEPREDECESSOR(PRBTreeNPRBTreeNodeRBTREESUCCESSOR(PRBTreeNodPRBTreeNodeRBTREESEARCH(PRBTreeNodepRoot,intval_key)voidKminelem(PRBTreepTree,intk)查找最大鍵值節(jié)點(diǎn)查找最小鍵值節(jié)點(diǎn)查找指定節(jié)點(diǎn)的前趨節(jié)點(diǎn)查找指定節(jié)點(diǎn)的后繼節(jié)點(diǎn)查找指定鍵值的節(jié)點(diǎn)查找第K小元素，輸出鍵值與顏色20133997張帥typedefstructtagRBTreeNodePRBTreeNodeCreateRBTreeNode(intkeyVal)DeleteRBTreeNode(PRBTreeNodvoidInitRBTree(PRBTreepTree)INORDERRBTREE_WALK(PRBTreeNodepRoot)LEFTROTATION(PRBTreepTree,PRBTreeNodepNode)RIGHTROTATION(PRBTreepTree,PRBTreeNodepNode)紅黑樹結(jié)構(gòu)紅黑樹結(jié)點(diǎn)結(jié)構(gòu)生成一個(gè)紅黑樹節(jié)點(diǎn)釋放一個(gè)節(jié)點(diǎn)的內(nèi)存初始化一棵紅黑樹中序遍歷二叉樹主函數(shù)對指定節(jié)點(diǎn)進(jìn)行左旋對指定節(jié)點(diǎn)進(jìn)行右旋課題報(bào)告分工章節(jié)內(nèi)容完成人1課題概述1.1課題任務(wù)1.2課題原理1.3相關(guān)知識張帥2需求分析2.1課題調(diào)研2.2用戶需求分析肖瑤3方案設(shè)計(jì)3.1總體功能設(shè)計(jì)3.2數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)3.3函數(shù)原型設(shè)計(jì)3.4主算法設(shè)計(jì)3.5用戶界面設(shè)計(jì)張帥4方案實(shí)現(xiàn)4.1開發(fā)環(huán)境與工具4.2程序設(shè)計(jì)關(guān)鍵技術(shù)4.3個(gè)人設(shè)計(jì)實(shí)現(xiàn)(按組員分工)4.3.14.3.24.3.3陳果5課題總結(jié)5.1課題評價(jià)5.2團(tuán)隊(duì)協(xié)作5.3個(gè)人設(shè)計(jì)心得(按組員分工)肖瑤集合中的元素是動態(tài)構(gòu)成的。要求對集合中的n個(gè)元素求解第k小的元素。(1)實(shí)現(xiàn)動態(tài)查找表的三種基本功能：查找、插入、刪除。(2)實(shí)現(xiàn)紅黑平衡二叉樹的動態(tài)查找第k小的元素。(3)可以考慮與快速，它的統(tǒng)計(jì)性能要好于平衡數(shù)據(jù)結(jié)構(gòu)，典型的用途是實(shí)現(xiàn)關(guān)聯(lián)數(shù)組。它是在1972年由RudolfBayer發(fā)明的，他稱之為"對稱二叉B樹",它現(xiàn)代的名字是在LeoJ.Guibas和RobertSedgewick于1978年寫的一篇論文中獲得的。它是復(fù)雜的，但它的操作有著良查找，插入和刪除，這里的n是樹中元素的數(shù)目。通過對任何一條從根到葉子的路徑上各個(gè)結(jié)點(diǎn)著色方式的限制，紅黑樹確保沒3.每個(gè)葉結(jié)點(diǎn)(葉結(jié)點(diǎn)即指樹尾端NIL指針或NULL結(jié)點(diǎn))都是黑的。這些約束強(qiáng)制了紅黑樹的關(guān)鍵性質(zhì)：從根到葉子的最長的可能路徑不多于最短的可能路徑的兩倍長。結(jié)果是這個(gè)樹大致上是平衡的。因?yàn)椴僮鞅热绮迦搿h除和查找某個(gè)值的最壞情況時(shí)間都要求與樹的高度成比例，這個(gè)在高度上的理要知道為什么這些特性確保了這個(gè)結(jié)果，注意到性質(zhì)4導(dǎo)致了路徑不能有兩個(gè)毗連的紅色節(jié)點(diǎn)就足夠了。最短的可能路徑都是黑色節(jié)點(diǎn)，最長的可能路徑有交替的紅色和黑色節(jié)點(diǎn)。因?yàn)楦鶕?jù)性質(zhì)5所有最長的路徑都有相同數(shù)目的黑色包含數(shù)據(jù)。用這種范例表示紅黑樹是可能的，但是這會改變一些屬性并使算法復(fù)雜。為此，本文中我們使用"nil葉子"或"空(null)葉子",如上圖所示，它不包含數(shù)據(jù)而只充當(dāng)樹在此結(jié)束的指示。這些節(jié)點(diǎn)在繪圖中經(jīng)常被省略，導(dǎo)致了這些樹好象同上述原則相矛盾，而實(shí)際上不是這樣。與此有關(guān)的結(jié)論是所有節(jié)2需求分析二叉排序樹有3個(gè)性質(zhì)：(1)若左子樹不空，則左子樹上所有結(jié)點(diǎn)的值均小于樹，具有以下性質(zhì)：它是一棵空樹或它的左右兩個(gè)子樹的高度差的絕對值不超過1,并且左右兩個(gè)子樹都是一棵平衡二叉樹。對于一般的二叉搜索樹(BinarySearchTree),其期望高度(即為一棵平衡樹時(shí))為log2n,其各操作的時(shí)間復(fù)雜度(0(log2n))同時(shí)也由此而決定。但是，在某些極端的情況下(如在插入的序列是有序的時(shí)),二叉搜索樹將退化成近似鏈或鏈，此時(shí)，其操作的時(shí)間復(fù)雜度將退化成線性的，即0(n)。吳偉民編著)下圖所示，即是一顆紅黑樹：2.2用戶需求分析用戶要求在一組數(shù)據(jù)中查找第K小元素，為了是查找效率最高，本算法用紅黑二叉樹實(shí)現(xiàn)，同時(shí)實(shí)現(xiàn)的還有元素的查找、添加與刪除。3方案設(shè)計(jì)3.1總體功能設(shè)計(jì)實(shí)現(xiàn)動態(tài)查找表的三種基本功能：查找、插入、刪除；實(shí)現(xiàn)紅黑平衡二叉樹的動態(tài)查找第k小的元素。3.2數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)建立樹與結(jié)點(diǎn)的結(jié)構(gòu)體，構(gòu)造紅黑二叉樹，對元素進(jìn)行查找，插入與刪除以及查找、刪除后進(jìn)行紅黑性質(zhì)的恢復(fù)。3.3函數(shù)原型設(shè)計(jì)生成一個(gè)紅黑樹節(jié)點(diǎn)，缺省的節(jié)點(diǎn)顏色是紅黑。PRBTreeNodeCreateRBTreeNode(intkeyVal)voidInitRBTree(PRBTreepTree)//初始化一棵紅黑樹中序遍歷二叉樹，并輸出鍵值與顏色voidINORDER_RBTREE_WALK(PRBTreeNodepRoot)查找指定鍵值的節(jié)點(diǎn)PRBTreeNodeRBTREE_SEARCH(PRBTreeNodepRoot,intval_key)對指定節(jié)點(diǎn)進(jìn)行左旋staticvoidLEFT_ROTATION(PRBTreepTree,PRBTreeNodepNode)對指定節(jié)點(diǎn)進(jìn)行右旋staticvoidRIGHT_ROTATION(PRBTreepTree,PRBTreeNodepNode)在紅黑樹插入動作后進(jìn)行紅黑性質(zhì)恢復(fù)staticvoidFIX_UP_RB_AFTER_INSERT(PRBTreepTree,PRBTreeNodepNode)紅黑樹的節(jié)點(diǎn)插入voidRBTREE_INSERT(PRBTreepTree,PRBTreeNodepNode)在紅黑樹刪除動作后進(jìn)行紅黑性質(zhì)恢復(fù)staticvoidFIX_UP_RB_AFTER_DELETE(PRBTreepTree,PRBTreeNodepNode)紅黑樹的節(jié)點(diǎn)刪除PRBTreeNodeRBTREE_DELETE(PRBTreepTree,PRBTreeNodepDel)voidK_min_elem(PRBTreepTree,intk)3.4主算法設(shè)計(jì)RBTreebsTree;InitRBTree(&bsTree);printf("請先創(chuàng)建一個(gè)紅黑書，依次輸入元素的整型數(shù)值，以#結(jié)束!\n");scanf("%d",&_key);bsTree.root->key=_key;PRBTreeNodepNode;RBTREE_INSERT(&bsTree,bsTree.root);for(inti=2;_key!='#';i++)}-----------2\n");-----------4\n");查找第查找元素K小元素printf("請選擇您對紅黑平衡二叉樹的操作：");scanf("%d",&j);charJudge='Y';while(Judge=='Y')PRBTreeNodep_Node;printf("請輸入要插入元素的數(shù)值：");scanf("%d",&p_Node->keyRBTREE_INSERT(&bsTree,p_Node);break;printf("請輸入要查找元素的數(shù)值：");intval_key;PRBTreeNodepnode;pnode=RBTREE_SEARCH(bsTree.root,valkey);printf("元素為值：%d,元素顏色為：%s,左孩子：%d,左孩子：%d\n",pnode->key,pnode->color==BLACK?"BLACK":"RED",pnode->left->key,pnode->right->key);break;PRBTreeNodep_Del;printf("請輸入要?jiǎng)h除元素的數(shù)值：");scanf("%d",&p_Del->keRBTREE_DELETE(&bsTree,p_Del);break;printf("請輸入K值：");Kminelem(&bsTree,K);break;default:break;}return0;3.5用戶界面設(shè)計(jì)...........14請先創(chuàng)建一個(gè)紅黑書，依次輸入元素的整型數(shù)值，以·結(jié)束!請先創(chuàng)建一個(gè)紅黑書，依次輸入元素的整型數(shù)值，以·結(jié)束!情輸入第1個(gè)數(shù)值Pressanykeytocontinue通人元素一通人元素一 1則除元素 3退出操作一-0請選擇您對紅黑平衡二叉樹的操作：查找元素 2杳找第K小元素-44方案實(shí)現(xiàn) 4.1開發(fā)環(huán)境與工具 4.2程序設(shè)計(jì)關(guān)鍵技術(shù) 本程序的設(shè)計(jì)關(guān)鍵在與紅黑樹的構(gòu)建及紅黑樹性質(zhì)的恢復(fù)與維護(hù)：當(dāng)我們在對紅黑樹進(jìn)行插入和刪除等操作時(shí)，對樹做了修改，那么可能會違背紅黑樹的性質(zhì)。為了保持紅黑樹的性質(zhì)，我們可以通過對樹進(jìn)行旋轉(zhuǎn)，即修改樹種某些結(jié)點(diǎn)的顏色及指針結(jié)構(gòu)，以達(dá)到對紅黑樹進(jìn)行插入、刪除結(jié)點(diǎn)等操作時(shí)，紅黑樹依然能保持它特有的性質(zhì)?？梢詾闃鋬?nèi)任意右孩子而不是NIL[T]的結(jié)點(diǎn)。左旋以pivot到y(tǒng)之間的鏈為“支軸”進(jìn)行，它使y成為該孩子樹新的根，而y的左孩子b則成為pivot的右孩子。右旋與之類似。插入操作：情況1:插入的是根結(jié)點(diǎn)原樹是空樹，此情況只會違反性質(zhì)2。對策：直接把此結(jié)點(diǎn)涂為黑色。情況2:插入的結(jié)點(diǎn)的父結(jié)點(diǎn)是黑色。此不會違反性質(zhì)2和性質(zhì)4,紅黑樹沒有情況3:當(dāng)前結(jié)點(diǎn)的父結(jié)點(diǎn)是紅色且祖父結(jié)點(diǎn)的另一個(gè)子結(jié)點(diǎn)(叔叔結(jié)點(diǎn))是的。我們將此歸為同一類。對策：將當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)和叔叔節(jié)點(diǎn)涂黑，祖父情況4:當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)是紅色，叔叔節(jié)點(diǎn)是黑色，當(dāng)前節(jié)點(diǎn)是其父節(jié)點(diǎn)的右情況5:當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)是紅色，叔叔節(jié)點(diǎn)是黑色，當(dāng)前節(jié)點(diǎn)是其父節(jié)點(diǎn)的左情況1:當(dāng)前節(jié)點(diǎn)是紅色。解法，直接把當(dāng)前節(jié)點(diǎn)染成黑色，結(jié)束。情況2:當(dāng)前節(jié)點(diǎn)是黑色且是根節(jié)點(diǎn)。解法：什么都不做，結(jié)束情況3:當(dāng)前節(jié)點(diǎn)是黑色，且兄弟節(jié)點(diǎn)為紅色(此時(shí)父節(jié)點(diǎn)和兄弟節(jié)點(diǎn)的子節(jié)點(diǎn)然后，針對父節(jié)點(diǎn)做一次左旋。此變換后原紅黑樹性質(zhì)5不變，而把問題轉(zhuǎn)化情況4:當(dāng)前節(jié)點(diǎn)是黑色，且兄弟是黑色，且兄弟節(jié)點(diǎn)的兩個(gè)子節(jié)點(diǎn)全為黑色。解法：把當(dāng)前節(jié)點(diǎn)和兄弟節(jié)點(diǎn)中抽取一重黑色追加到父節(jié)點(diǎn)上，把父節(jié)點(diǎn)當(dāng)成情況5:當(dāng)前節(jié)點(diǎn)顏色是黑色，兄弟節(jié)點(diǎn)是黑色，兄弟的左子是紅色，右子是黑色。解法：把兄弟結(jié)點(diǎn)染紅，兄弟左子節(jié)情況6:當(dāng)前節(jié)點(diǎn)顏色是黑色，它的兄弟節(jié)點(diǎn)是黑色，但是兄弟節(jié)點(diǎn)的右子是紅把當(dāng)前節(jié)點(diǎn)父節(jié)點(diǎn)染成黑色，兄弟節(jié)點(diǎn)右子染成黑色，之后以當(dāng)前節(jié)點(diǎn)的父節(jié)4.3個(gè)人設(shè)計(jì)實(shí)現(xiàn)(按組員分工)//在紅黑樹插入動作后進(jìn)行紅黑性質(zhì)恢復(fù)staticvoidFIX_UP_RBAFTER_INSERT(PRBTreepTree,PRBTreeNodepNode)if(pNode->parent==pNode->parent->parent->left){if(RED==pUncleNode->color){pNode->parent->color=BLACK;pUncleNode->color=BLACK;pNode=pUncleNode->parent;pNode->color=RED;if(pNode==pNode->parent->right){pNode=pNode->parent;LEFT_ROTATION(pTree,pNode);pNode->parent->color=BLACK:PRBTreeNodeTempP=pNode->parent->parent;TempP->color=RED;RIGHT_ROTATION(pTree,TempP);PRBTreeNodepUncleNode=pNode->parent->parent->left;if(RED==pUncleNode->color){pNode->parent->color=BLACK;pUncleNode->color=BLACK;pNode=pUncleNode->parent;pNode->color=RED;if(pNode==pNode->parent->left){pNode=pNode->parent;RIGHT_ROTATION(pTree,pNode);pNode->parent->color=BLACK;PRBTreeNodeTempP=pNode->parent->parent;TempP->color=RED;LEFT_ROTATION(pTree,TempP);pTree->root->color=BLACK;//紅黑樹的節(jié)點(diǎn)插入voidRBTREE_INSERT(PRBTreepTree,PRBTreeNodepNode)PRBTreeNodepNodePosition=pTree->root;PRBTreeNodepParent=PNIL;while(PNIL!=pNodePosipParent=pNodePosition;pNodePosition=pNode->key>pNodePosition->key?pNodePosition->right:pNodePosition->left;pNode->parent=pParent;if(PNIL==pParent){pTree->root=pNode;if(pNode->key>pParent->key){pParent->right=pNode;pParent->left=pNode;~FIX_UP_RB_AFTER_INSERT(pTree,pNode);//在紅黑樹刪除動作后進(jìn)行紅黑性質(zhì)恢復(fù)staticvoidFIX_UP_RB_AFTER_DELETE(PRBTreepTree,PRBTreeNodepNode){while((pNode->color==BLACK)&&(pNode!=pTree->root)){if(pNode==pNode->parent->left){PRBTreeNodepBrother=pNode->parent->right;if(RED==pBrother->color){pBrother->color=BLACK;pNode->parent->color=RED;LEFT_ROTATION(pTree,pNode->parent);pBrother=pNode->parent->right;if((BLACK==pBrother->right->color)&&(BLACK==pBrother->left->color)){pBrother->color=RED;pNode=pNode->parent;if(BLACK==pBrother->right->color){pBrother->color=RED;pBrother->left->color=BLACK;RIGHT_ROTATION(pTree,pBrother);pBrother=pNode->parent->right;pBrother->right->color=BLACK;pBrother->color=pNode->parent->color;pNode->parent->color=BLACK;LEFT_ROTATION(pTree,pNode->parent);pNode=pTree->root;PRBTreeNodepBrother=pNode->parent->left;if(RED==pBrother->color){pBrother->color=BLACK;pNode->parent->color=RED;RIGHT_ROTATION(pTree,pNode->parent);pBrother=pNode->parent->left;if((BLACK==pBrother->left->color)&&(BLACKpBrother->color=RED;==pBrother->right->color)){pNode=pNode->parent;if(BLACK==pBrother->left->color){pBrother->color=RED;pBrother->right->color=BLACK;LEFT_ROTATION(pTree,pBrother);pBrother=pNode->parent->left;pBrother->left->color=BLACK;pBrother->color=pNode->parent->color;pNode->parent->color=BLACK;RIGHT_ROTATION(pTree,pNode->parent);pNode=pTree->root;pNode->color=BLACK;//紅黑樹的節(jié)點(diǎn)刪除PRBTreeNodeRBTREE_DELETE(PRBTreepTree,PRBTreeNodepDel)PRBTreeNodepRelDel;if((PNIL==pDel->left)||(PNIL==pDel->right)){pRelDel=pDel;pRelDel=RBTREE_SUCCESSOR(pDel);PRBTreeNodepChildOfDel;pChildOfDel=(pRelDel->left!=PNIL?pRelDel->left:pRelDel->right);pChildOfDel>parent=pRelDel->parent;if(PNIL==pRelDel->parent){pTree->root=pChildOfDel;if(pRelDel==pRelDel->parent->left){pRelDel>parent->left=pChildOfDel;pRelDel->parent->right=pChildOfDel;if(pRelDel!=pDel){pDel>key=pRelDel->key;if(pRelDel->color==BLACK){FIX_UP_RB_AFTER_DELETE(pTree,pChildOfDel);returnpRelDel;//查找指定鍵值的節(jié)點(diǎn)PRBTreeNodeRBTREE_SEARCH(PRBTreeNodepRoot,intval_key)while((PNIL!=pRoot)&&(val_key!=pRoot->key)){pRoot=(valkey<pRoot->key?pRoot->left:pRoot->right);returnpRoot;/1查找最大鍵值節(jié)點(diǎn)PRBTreeNodeRBTREE_MAX(PRBTreeNodepRoot)while(PNIL!=pRoot->right){pRoot=pRoot->right;returnpRoot;//查找最小鍵值節(jié)點(diǎn)PRBTreeNodeRBTREE_MIN(PRBTreeNodepRoot)while(PNIL!=pRoot->left){pRoot=pRoot->left;returnpRoot;//查找指定節(jié)點(diǎn)的后繼節(jié)點(diǎn)PRBTreeNodeRBTREE_SUCCESSOR(PRBTreeNodepRoot)if(PNIL!=pRoot->right){returnRBTREE_MIN(pRoot->right);PRBTreeNodepParent=pRoot->parent;while((PNIL!=pParent)&&(pRoot==pParent->right)){pRoot=pParent;pParent=pRoot->parent;//查找指定節(jié)點(diǎn)的前趨節(jié)點(diǎn)PRBTreeNodeRBTREE_PREDECESSOR(PRBTreeNodepRoot)if(PNIL!=pRoot->left){returnRBTREE_MAX(pRoot->left);PRBTreeNodepParent=pRoot->parent;while((PNIL!=pParent)&&(pRoot==pRoot->left)){pRoot=pParent;pParent=pRoot->parent;}//打印出紅黑樹每個(gè)節(jié)點(diǎn)的各項(xiàng)值。voidRBTREE_STRUCTURE(PRBTreeNodepRoot)#defineGetKey(p)(p==PNIL?-1:p->key)if(PNIL!=pRoot){printf("KeyValue=%d,color=%s,Left=%d,Right=%d,Parent=%d\n",pRoot->key,pRoot->color==BLACK?"BLACK":"RED",GetKey(pRoot->left),GetKey(pRoot->right),GetKey(pRoot->parent));RBTREE_STRUCTURE(pRoot->left);RBTREE_STRUCTURE(pRoot->right);voidK_min_elem(PRBTreepTree,intk)PRBTreeNodepNode=RBTREE_MIN(pTree->root);for(i=2;i<=k;i++)pNode=RBTREE_SUCCESSOR(pNode);\n",pNode->key,pNode->color==BLACK?"BLACK":"RED");4.3.3張帥設(shè)計(jì)實(shí)現(xiàn)：//定義節(jié)點(diǎn)顏色enumCOLORBLACK=0,RED//紅黑樹節(jié)點(diǎn)typedefstructtagRBTreeNodeintkey;structtagRBTreeNode*left;structtagRBTreeNode*right;structtagRBTreeNode*parent;unsignedcharcolor;}RBTreeNode,*PRBTreeNode;//紅黑樹，包含一個(gè)指向根節(jié)點(diǎn)的指針typedefstructtagRBTreePRBTreeNoderoot;}RBTree,*PRBTree;//紅黑樹的NIL節(jié)點(diǎn)staticRBTreeNodeNIL={0,0,0,0,BLACK};#definePNIL(&NIL)//NIL節(jié)點(diǎn)地址//生成一個(gè)紅黑樹節(jié)點(diǎn)，缺省的節(jié)點(diǎn)顏色是紅黑。PRBTreeNodeCreateRBTreeNode(intkeyVal)PRBTreeNodep=(PRBTreeNode)malloc(sizeof(RBTreeNode));p->color=RED:p->left=PNIL;p->right=PNIL;p->parent=PNIL:p->key=keyVal;returnp;//釋放一個(gè)節(jié)點(diǎn)的內(nèi)存voidDeleteRBTreeNode(PRBTreeNodepDif(PNIL!=pDel){)voidInitRBTree(PRBTreepTree)//初始化一棵紅黑樹pTree->root=PNIL;//中序遍歷二叉樹，并輸出鍵值與顏色voidINORDER_RBTREE_WALK(PRBTreeNodepRoot)if(PNIL!=pRoot){}}//對指定節(jié)點(diǎn)進(jìn)行左旋PRBTreeNodepRight=pNode->rightpRight->parent=pNode->parent;if(pNode->parent->left==pNode){pRight->parent->left=pRight;pRight->parent->right=pRight;}if(PNIL==pRight->parent){pTree->root=pRight;if(PNIL!=pRight->left){pRight->left->parent=pNode;pNode->right=pRight->left;pNode->parent=pRight;pRight->left=pNode;//對指定節(jié)點(diǎn)進(jìn)行右旋staticvoidRIGHT_ROTATION(PRBTreepTree,PRBTreeNodepNode)PRBTreeNodepLeft=pNode->left;pLeft->parent=pNode->parent;if(pNode->parent->left==pNode){pLeft->parent->left=pLeft;pLeft->parent->right=pLeft;了if(PNIL==pLeft->parent){pTree->root=pLeft;if(PNIL!=pLeft->rightpLeft->right->parent=pNode;pNode->left=pLeft->right;pNode->parent=pLeft;pLeft->right=pNode;RBTreebsTree;printf("請先創(chuàng)建一個(gè)紅黑書，依