數(shù)據(jù)結(jié)構(gòu) 紅黑樹的詳解
更新時(shí)間：2017年07月23日 09:48:01 投稿：lqh
這篇文章主要介紹了數(shù)據(jù)結(jié)構(gòu) 紅黑樹的詳解的相關(guān)資料,數(shù)據(jù)結(jié)構(gòu)中的二叉樹查找，紅黑樹的講解，需要的朋友可以參考下
數(shù)據(jù)結(jié)構(gòu) 紅黑樹的詳解
紅黑樹是具有下列著色性質(zhì)的二叉查找樹：
1.每一個(gè)節(jié)點(diǎn)或者著紅色，或者著黑色。
2.根是黑色的。
3.如果一個(gè)節(jié)點(diǎn)是紅色的，那么它的子節(jié)點(diǎn)必須是黑色。
4.從一個(gè)節(jié)點(diǎn)到一個(gè)NULL指針的每一條路徑必須包含相同數(shù)目的黑色節(jié)點(diǎn)。
下面是一棵紅黑樹。
1.自底向上插入
通常把新項(xiàng)作為樹葉放到樹中。如果我們把該項(xiàng)涂成黑色，那么違反條件4，因?yàn)閷?huì)建立一條更長(zhǎng)的黑節(jié)點(diǎn)路徑。因此這一項(xiàng)必須涂成紅色。如果它的父節(jié)點(diǎn)是黑色的，插入完成。如果父節(jié)點(diǎn)是紅色的，那么違反條件3。在這種情況下我們必須調(diào)整該樹以滿足條件3。用于完成這項(xiàng)目任務(wù)的基本操作是顏色的改變和樹的旋轉(zhuǎn)。
如果新插入的節(jié)點(diǎn)的父節(jié)點(diǎn)是黑色，那么插入完成。
如果父節(jié)點(diǎn)是紅色，那么有幾種情形需要考慮。首先，假設(shè)這個(gè)父節(jié)點(diǎn)的兄弟是黑色（NULL節(jié)點(diǎn)約定為黑色）。這對(duì)于插入3或8是適用的，但對(duì)插入99不適用。令X是新加的樹葉，P是它的父節(jié)點(diǎn)，S是該父節(jié)點(diǎn)的兄弟，G是祖父節(jié)點(diǎn)情況一：父節(jié)點(diǎn)的兄弟是黑色的。通過操作使得到達(dá)A,B,C的黑色路徑保持不變（滿足條件4），而且沒有連續(xù)的紅色節(jié)點(diǎn)（滿足條件3）.。
情況二：父節(jié)點(diǎn)的兄弟是紅色的。
2.自頂向下刪除
紅黑樹中的刪除可以是自頂向下進(jìn)行。每一件工作都?xì)w結(jié)于能夠刪除一片樹葉。這是因?yàn)?，要?jiǎng)h除一個(gè)帶有兩個(gè)兒子的節(jié)點(diǎn)，我們用右子樹上的最小節(jié)點(diǎn)代替它；該節(jié)點(diǎn)最多有一個(gè)兒子，然后將該節(jié)點(diǎn)刪除。只有一個(gè)右兒子的節(jié)點(diǎn)可以用相同的方式刪除，而只有一個(gè)左兒子的節(jié)點(diǎn)通過用其左子樹上最大的節(jié)點(diǎn)替換，然后可將該節(jié)點(diǎn)刪除。但是假如刪除的節(jié)點(diǎn)不是紅色的，那么就會(huì)破壞紅黑樹的平衡。解決的方法就是保證從上到下刪除期間樹葉是紅色的。
在整個(gè)討論中，令X為當(dāng)前節(jié)點(diǎn)，T是它的兄弟，而P是它們的父親。開始時(shí)我們把根涂成紅色。當(dāng)沿著樹向下遍歷時(shí)，我們?cè)O(shè)法保證X是紅色的。當(dāng)我們到達(dá)一個(gè)新的節(jié)點(diǎn)時(shí)，我們要確信P是紅色的并且X和T是黑色的（因?yàn)椴荒苡袃蓚€(gè)相連的紅色節(jié)點(diǎn)）。存在兩種主要情形。
情況一：X有兩個(gè)黑色兒子。此時(shí)有三個(gè)子情況。
（1）T有兩個(gè)黑兒子，那么我們可以翻轉(zhuǎn)X、T、P的顏色來保持這種不變性。
（2）T的左兒子是紅色的
（3）T的右兒子是紅色的
情況二：X的兒子之一是紅的。在這種情況下，我們落到下一層，得到新的X、T、P。如果幸運(yùn)，X落在紅兒子上。則我們繼續(xù)前行。如果不是這樣，那么我們知道T將是紅的，而X和P將是黑的。我們可以旋轉(zhuǎn)T和P，使得X的新父親是紅的；當(dāng)然X和它的祖父是黑的。此時(shí)我們可以回到第一種主情況。
3.紅黑樹的實(shí)現(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 實(shí)現(xiàn)文件
//
// RedBlackTree.c
// RedBlackTree3
//
// Created by Wuyixin on 2017/7/3.
// Copyright © 2017年 Coding365. All rights reserved.
//
#include "RedBlackTree.h"
/* 左旋轉(zhuǎn) */
static Position SingleRotateLeft(Position X);
/* 右旋轉(zhuǎn) */
static Position SingleRotateRight(Position X);
/* 旋轉(zhuǎn) */
static Position Rotate(Position Parent,Position* Origin ,ElementType Item);
/* 左旋轉(zhuǎn) */
static Position SingleRotateLeft(Position T){
Position TL = T->Left;
T->Left = TL->Right;
TL->Right = T;
return TL;
}
/* 右旋轉(zhuǎn) */
static Position SingleRotateRight(Position T){
Position TR = T->Right;
T->Right = TR->Left;
TR->Left = T;
return TR;
}
/* 旋轉(zhuǎn) */
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;
/* 當(dāng)P與X同時(shí)為紅節(jié)點(diǎn)才進(jìn)行調(diào)整 */
if (X == NullNode || !(P->Color == RED && X->Color == RED))
return ;
Sibling = GetSibling(GP, P);
if (Sibling == NULL)
return ;
/* GP,P,X是成字型，調(diào)整為一字型 */
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);
/* 重復(fù)值不插入 */
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有兩個(gè)黑兒子 */
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是紅的，旋轉(zhuǎn) */
if (X->Color == BLACK){
GP = Rotate(GP, &Origin, Sibling->Element);
P = Origin;
GP->Color = BLACK;
P->Color = RED;
_HandleReorientForRemove(Item);
}
/* 恢復(fù)X,PX,GP。由于X是當(dāng)前節(jié)點(diǎn) 如果當(dāng)前節(jié)點(diǎn)正是Item，不恢復(fù)會(huì)影響查找 */
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 調(diào)用
//
// 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;
}
以上就是關(guān)于數(shù)據(jù)結(jié)構(gòu)與算法中紅黑二叉樹的詳解，如有疑問請(qǐng)留言或者到本站的社區(qū)討論，感謝閱讀，希望能幫助到大家，謝謝大家對(duì)本站的支持！
相關(guān)文章
這篇文章主要給大家介紹了關(guān)于C語言結(jié)構(gòu)體的一些理解，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-11-11
本章主要介紹C語言與C++的內(nèi)存管理，以C++的內(nèi)存分布作為引入，介紹C++不同于C語言的內(nèi)存管理方式（new delete對(duì)比 malloc free)，感興趣的朋友來看看吧2022-06-06
這篇文章主要介紹了C++編程中的文件流與字符串流,是C++入門學(xué)習(xí)中的基礎(chǔ)知識(shí),需要的朋友可以參考下2015-09-09
C++實(shí)現(xiàn)班級(jí)成績(jī)管理系統(tǒng)
這篇文章主要為大家詳細(xì)介紹了C++實(shí)現(xiàn)班級(jí)成績(jī)管理系統(tǒng)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2022-02-02
由于這幾天在開發(fā)中要用到函數(shù)指針，所以就整理了一下關(guān)于函數(shù)指針的概念2013-08-08
無論是哪一門開發(fā)框架，如果涉及到UI這塊，肯定需要用到自定義控件，本文為大家準(zhǔn)備了一些基于QT編寫的超精美自定義控件，需要的可以參考一下2023-07-07
Boost是為C++語言標(biāo)準(zhǔn)庫提供擴(kuò)展的一些C++程序庫的總稱。Boost庫是一個(gè)可移植、提供源代碼的C++庫，作為標(biāo)準(zhǔn)庫的后備，是C++標(biāo)準(zhǔn)化進(jìn)程的開發(fā)引擎之一，是為C++語言標(biāo)準(zhǔn)庫提供擴(kuò)展的一些C++程序庫的總稱2022-11-11
c語言根據(jù)用戶輸入的出生年份并計(jì)算出當(dāng)前年齡
這篇文章主要介紹了c語言根據(jù)用戶輸入的出生年份并計(jì)算出當(dāng)前年齡,需要的朋友可以參考下2023-03-03
這篇文章主要介紹了C語言實(shí)現(xiàn)求定積分的方法,涉及C語言操作相關(guān)數(shù)學(xué)函數(shù)的技巧,具有一定參考借鑒價(jià)值,需要的朋友可以參考下2015-02-02
這篇文章主要介紹了二叉樹入門和刷題詳解的相關(guān)資料,需要的朋友可以參考下2023-07-07