您好,登錄后才能下訂單哦!
這篇文章給大家分享的是有關編程語言中數(shù)據(jù)結構之紅黑樹的示例分析的內容。小編覺得挺實用的,因此分享給大家做個參考,一起跟隨小編過來看看吧。
紅黑樹是具有下列著色性質的二叉查找樹:
1.每一個節(jié)點或者著紅色,或者著黑色。
2.根是黑色的。
3.如果一個節(jié)點是紅色的,那么它的子節(jié)點必須是黑色。
4.從一個節(jié)點到一個NULL指針的每一條路徑必須包含相同數(shù)目的黑色節(jié)點。
下面是一棵紅黑樹。
1.自底向上插入
通常把新項作為樹葉放到樹中。如果我們把該項涂成黑色,那么違反條件4,因為將會建立一條更長的黑節(jié)點路徑。因此這一項必須涂成紅色。如果它的父節(jié)點是黑色的,插入完成。如果父節(jié)點是紅色的,那么違反條件3。在這種情況下我們必須調整該樹以滿足條件3。用于完成這項目任務的基本操作是顏色的改變和樹的旋轉。
如果新插入的節(jié)點的父節(jié)點是黑色,那么插入完成。
如果父節(jié)點是紅色,那么有幾種情形需要考慮。首先,假設這個父節(jié)點的兄弟是黑色(NULL節(jié)點約定為黑色)。這對于插入3或8是適用的,但對插入99不適用。令X是新加的樹葉,P是它的父節(jié)點,S是該父節(jié)點的兄弟,G是祖父節(jié)點情況一:父節(jié)點的兄弟是黑色的。通過操作使得到達A,B,C的黑色路徑保持不變(滿足條件4),而且沒有連續(xù)的紅色節(jié)點(滿足條件3).。
情況二:父節(jié)點的兄弟是紅色的。
2.自頂向下刪除
紅黑樹中的刪除可以是自頂向下進行。每一件工作都歸結于能夠刪除一片樹葉。這是因為,要刪除一個帶有兩個兒子的節(jié)點,我們用右子樹上的最小節(jié)點代替它;該節(jié)點最多有一個兒子,然后將該節(jié)點刪除。只有一個右兒子的節(jié)點可以用相同的方式刪除,而只有一個左兒子的節(jié)點通過用其左子樹上最大的節(jié)點替換,然后可將該節(jié)點刪除。但是假如刪除的節(jié)點不是紅色的,那么就會破壞紅黑樹的平衡。解決的方法就是保證從上到下刪除期間樹葉是紅色的。
在整個討論中,令X為當前節(jié)點,T是它的兄弟,而P是它們的父親。開始時我們把根涂成紅色。當沿著樹向下遍歷時,我們設法保證X是紅色的。當我們到達一個新的節(jié)點時,我們要確信P是紅色的并且X和T是黑色的(因為不能有兩個相連的紅色節(jié)點)。存在兩種主要情形。
情況一:X有兩個黑色兒子。此時有三個子情況。
(1)T有兩個黑兒子,那么我們可以翻轉X、T、P的顏色來保持這種不變性。
(2)T的左兒子是紅色的
(3)T的右兒子是紅色的
情況二:X的兒子之一是紅的。在這種情況下,我們落到下一層,得到新的X、T、P。如果幸運,X落在紅兒子上。則我們繼續(xù)前行。如果不是這樣,那么我們知道T將是紅的,而X和P將是黑的。我們可以旋轉T和P,使得X的新父親是紅的;當然X和它的祖父是黑的。此時我們可以回到第一種主情況。
3.紅黑樹的實現(xiàn)
3.1 頭文件
// // RedBlackTree.h // RedBlackTree3 // // Created by Wuyixin on 2017/7/3. // Copyright © 2017年 Coding365. All rights reserved. // #ifndef RedBlackTree_h #define RedBlackTree_h #include <stdio.h> #include <stdlib.h> #include <limits.h> typedef int ElementType; typedef enum { RED, BLACK } COLOR; typedef struct RedBlackNode *RedBlackTree,*Position; struct RedBlackNode{ ElementType Element; COLOR Color; RedBlackTree Left; RedBlackTree Right; }; static Position NullNode = NULL; static Position Header; static Position X,P,GP,GGP; /* 初始化 */ RedBlackTree Initialize(); /* 插入 */ RedBlackTree Insert(RedBlackTree T,ElementType Item); /* 刪除 */ RedBlackTree Remove(RedBlackTree T,ElementType Item); /* 查找 */ Position Find(RedBlackTree T,ElementType Item); /* 遍歷 */ void Travel(RedBlackTree T); #endif /* RedBlackTree_h */
3.2 實現(xiàn)文件
// // RedBlackTree.c // RedBlackTree3 // // Created by Wuyixin on 2017/7/3. // Copyright © 2017年 Coding365. All rights reserved. // #include "RedBlackTree.h" /* 左旋轉 */ static Position SingleRotateLeft(Position X); /* 右旋轉 */ static Position SingleRotateRight(Position X); /* 旋轉 */ static Position Rotate(Position Parent,Position* Origin ,ElementType Item); /* 左旋轉 */ static Position SingleRotateLeft(Position T){ Position TL = T->Left; T->Left = TL->Right; TL->Right = T; return TL; } /* 右旋轉 */ static Position SingleRotateRight(Position T){ Position TR = T->Right; T->Right = TR->Left; TR->Left = T; return TR; } /* 旋轉 */ static Position Rotate(Position Parent,Position* Origin ,ElementType Item){ if (Item < Parent->Element){ if (Origin != NULL) *Origin = Parent->Left; return Parent->Left = Item < Parent->Left->Element ? SingleRotateLeft(Parent->Left) : SingleRotateRight(Parent->Left); } else{ if (Origin != NULL) *Origin = Parent->Right; return Parent->Right = Item < Parent->Right->Element ? SingleRotateLeft(Parent->Right) : SingleRotateRight(Parent->Right); } } /* 初始化 */ RedBlackTree Initialize(){ if (NullNode == NULL){ NullNode = malloc(sizeof(struct RedBlackNode)); if (NullNode == NULL) exit(EXIT_FAILURE); NullNode->Element = INT_MAX; NullNode->Color = BLACK; NullNode->Left = NullNode->Right = NullNode; } Header = malloc(sizeof(struct RedBlackNode)); if (Header == NULL) exit(EXIT_FAILURE); /* header的值為無窮小,所以根插入到右邊*/ Header->Element = INT_MIN; Header->Left = Header->Right = NullNode; Header->Color = BLACK; return Header; } static Position GetSibling(Position Parent,Position X){ if (Parent->Element == INT_MIN) return NULL; if (X == Parent->Left) return Parent->Right; else if (X == Parent->Right) return Parent->Left; else return NULL; } void HandleReorientForInsert(ElementType Item){ Position Sibling,Origin; /* 當P與X同時為紅節(jié)點才進行調整 */ if (X == NullNode || !(P->Color == RED && X->Color == RED)) return ; Sibling = GetSibling(GP, P); if (Sibling == NULL) return ; /* GP,P,X是成字型,調整為一字型 */ if ((GP->Element < Item) != (P->Element < Item)){ P = Rotate(GP, &Origin,Item); X = Origin; } GP = Rotate(GGP, &Origin,Item); P = Origin; /* P的兄弟是黑色的 */ if (Sibling->Color == BLACK){ GP->Color = BLACK; GP->Left->Color = RED; GP->Right->Color = RED; } /* P的兄弟是紅的 */ else{ GP->Color = RED; GP->Left->Color = BLACK; GP->Right->Color = BLACK; } } RedBlackTree _Insert(RedBlackTree T,ElementType Item){ if (T == NullNode){ T = malloc(sizeof(struct RedBlackNode)); T->Element = Item; T->Left = T->Right = NullNode; T->Color = RED; } else if (Item < T->Element) T->Left = _Insert(T->Left, Item); else if (Item > T->Element) T->Right = _Insert(T->Right, Item); /* 重復值不插入 */ X = P,P = GP,GP = GGP, GGP = T; HandleReorientForInsert(Item); return T; } /* 插入 */ RedBlackTree Insert(RedBlackTree T,ElementType Item){ GGP = GP = P = X = NullNode; T = _Insert(T, Item); T->Right->Color = BLACK; return T; } static void _HandleReorientForRemove(ElementType Item){ RedBlackTree Sibling,R; Sibling = GetSibling(P, X); if (Sibling == NULL) return ; if (Sibling->Left->Color == BLACK && Sibling->Right->Color == BLACK){ P->Color = BLACK; X->Color = RED; Sibling->Color = RED; }else if(Sibling->Left->Color == RED){ R = Sibling->Left; P->Color = BLACK; X->Color = RED; R = Rotate(P, NULL, R->Element); GP = Rotate(GP, NULL, R->Element); }else if (Sibling->Right->Color == RED){ X->Color = RED; P->Color = BLACK; Sibling->Color = RED; Sibling->Right->Color = BLACK; GP = Rotate(GP, NULL, Sibling->Element); } } static void HandleReorientForRemove(RedBlackTree T, ElementType Item){ RedBlackTree Sibling,Origin,OriginGP; if (X == NullNode) return ; /* X有兩個黑兒子 */ if (X->Left->Color == BLACK && X->Right->Color == BLACK){ _HandleReorientForRemove(Item); }else{ OriginGP = GP; /* 落到下一層 */ GP = P; P = X; if (Item < X->Element) X = X->Left; else X = X->Right; Sibling = GetSibling(P, X); /* 如果X是黑的,則Sibling是紅的,旋轉 */ if (X->Color == BLACK){ GP = Rotate(GP, &Origin, Sibling->Element); P = Origin; GP->Color = BLACK; P->Color = RED; _HandleReorientForRemove(Item); } /* 恢復X,PX,GP。由于X是當前節(jié)點 如果當前節(jié)點正是Item,不恢復會影響查找 */ if (X->Element == Item){ X = P ; P = GP ;GP = OriginGP; } } } /* 刪除 */ RedBlackTree Remove(RedBlackTree T,ElementType Item){ ElementType Origin; Position DeletePtr; Origin = NullNode->Element; NullNode->Element = Item; GP = P = X = T; /* 根染紅 */ T->Right->Color = RED; while (X->Element != Item) { GP = P ; P = X; if (Item < X->Element) X = X->Left; else X = X->Right; HandleReorientForRemove(T, Item); } NullNode->Element = Origin; /* 找到 */ if (X != NullNode){ DeletePtr = X; if (X->Left != NullNode){ GP = P ; P = X; X = X->Left; HandleReorientForRemove(T, Item); /* 尋找左子樹最大值替換 */ while (X->Right != NullNode) { GP = P ; P = X; X = X->Right; HandleReorientForRemove(T, Item); } if (X == P->Left) P->Left = X->Left; else P->Right = X->Left; }else if (X->Right != NullNode){ GP = P ; P = X; X = X->Right; HandleReorientForRemove(T, Item); /* 尋找右子樹最大值替換 */ while (X->Left != NullNode) { GP = P ; P = X; X = X->Left; HandleReorientForRemove(T, Item); } if (X == P->Left) P->Left = X->Right; else P->Right = X->Right; }else{ /* X是樹葉 */ if (X == P->Left) P->Left = NullNode; else P->Right = NullNode; } DeletePtr->Element = X->Element; free(X); } /* 根染黑 */ T->Right->Color = BLACK; return T; } typedef enum { ROOT, LEFT, RIGHT } NodeType; static char *TypeC; static char *ColorC; void _Travel(RedBlackTree T , NodeType Type){ if (T != NullNode){ if (Type == ROOT) TypeC = "root"; else if (Type == LEFT) TypeC = "left"; else if (Type == RIGHT) TypeC = "right"; if (T->Color == BLACK) ColorC = "black"; else ColorC = "red"; printf("(%d,%s,%s) ",T->Element,ColorC,TypeC); _Travel(T->Left, LEFT); _Travel(T->Right, RIGHT); } } /* 遍歷 */ void Travel(RedBlackTree T){ _Travel(T->Right,ROOT); }
3.3 調用
// // main.c // RedBlackTree3 // // Created by Wuyixin on 2017/7/3. // Copyright © 2017年 Coding365. All rights reserved. // #include "RedBlackTree.h" int main(int argc, const char * argv[]) { RedBlackTree T = Initialize(); T = Insert(T, 10); T = Insert(T, 85); T = Insert(T, 15); T = Insert(T, 70); T = Insert(T, 20); T = Insert(T, 60); T = Insert(T, 30); T = Insert(T, 50); T = Insert(T, 65); T = Insert(T, 80); T = Insert(T, 90); T = Insert(T, 40); T = Insert(T, 5); T = Insert(T, 55); T = Insert(T, 100); T = Remove(T, 100); Travel(T); return 0; }
感謝各位的閱讀!關于“編程語言中數(shù)據(jù)結構之紅黑樹的示例分析”這篇文章就分享到這里了,希望以上內容可以對大家有一定的幫助,讓大家可以學到更多知識,如果覺得文章不錯,可以把它分享出去讓更多的人看到吧!
免責聲明:本站發(fā)布的內容(圖片、視頻和文字)以原創(chuàng)、轉載和分享為主,文章觀點不代表本網站立場,如果涉及侵權請聯(lián)系站長郵箱:is@yisu.com進行舉報,并提供相關證據(jù),一經查實,將立刻刪除涉嫌侵權內容。