欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

數(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)文章

  • 從C語言過渡到C++之const

    從C語言過渡到C++之const

    C++中最早引入const是為了替代#define，后來又衍生出了其它用法。這一篇中我們來詳細(xì)介紹const的各種常見用法。希望對(duì)大家學(xué)習(xí)C++有所幫助。
    2017-07-07
  • C++進(jìn)一步認(rèn)識(shí)類與對(duì)象

    C++進(jìn)一步認(rèn)識(shí)類與對(duì)象

    類是創(chuàng)建對(duì)象的模板，一個(gè)類可以創(chuàng)建多個(gè)對(duì)象，每個(gè)對(duì)象都是類類型的一個(gè)變量；創(chuàng)建對(duì)象的過程也叫類的實(shí)例化。每個(gè)對(duì)象都是類的一個(gè)具體實(shí)例（Instance），擁有類的成員變量和成員函數(shù)
    2021-10-10
  • C++ Primer Plus 第四章之C++ Primer Plus復(fù)合類型學(xué)習(xí)筆記

    C++ Primer Plus 第四章之C++ Primer Plus復(fù)合類型學(xué)習(xí)筆記

    數(shù)組（array）是一種數(shù)據(jù)格式，能夠存儲(chǔ)多個(gè)同類型的值。每個(gè)值都存儲(chǔ)在一個(gè)獨(dú)立的數(shù)組元素中，計(jì)算機(jī)在內(nèi)存中依次存儲(chǔ)數(shù)組的各個(gè)元素，今天給大家重點(diǎn)介紹C++ Primer Plus復(fù)合類型的實(shí)例詳解，感興趣的朋友一起看看吧
    2021-07-07
  • Opencv下載和導(dǎo)入Visual studio2022的實(shí)現(xiàn)步驟

    Opencv下載和導(dǎo)入Visual studio2022的實(shí)現(xiàn)步驟

    本文主要介紹了Opencv下載和導(dǎo)入Visual studio2022的實(shí)現(xiàn)步驟，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2022-05-05
  • 基于Qt的TCP實(shí)現(xiàn)通信

    基于Qt的TCP實(shí)現(xiàn)通信

    這篇文章主要為大家詳細(xì)介紹了基于Qt的TCP實(shí)現(xiàn)通信，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下
    2022-08-08
  • C語言實(shí)現(xiàn)的猴子吃桃問題算法解決方案

    C語言實(shí)現(xiàn)的猴子吃桃問題算法解決方案

    這篇文章主要介紹了C語言實(shí)現(xiàn)的猴子吃桃問題解決方案,較為詳細(xì)的分析了猴子吃桃問題并給出了C語言算法的實(shí)現(xiàn)方法,具有一定參考借鑒價(jià)值,需要的朋友可以參考下
    2016-10-10
  • C++實(shí)現(xiàn)LeetCode(157.用Read4來讀取N個(gè)字符)

    C++實(shí)現(xiàn)LeetCode(157.用Read4來讀取N個(gè)字符)

    這篇文章主要介紹了C++實(shí)現(xiàn)LeetCode(157.用Read4來讀取N個(gè)字符),本篇文章通過簡(jiǎn)要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下
    2021-07-07
  • C語言實(shí)現(xiàn)詞法分析器

    C語言實(shí)現(xiàn)詞法分析器

    這篇文章主要為大家詳細(xì)介紹了C語言實(shí)現(xiàn)詞法分析器，一個(gè)簡(jiǎn)單的詞法分析程序，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下
    2019-01-01
  • C++編程之?std::forward使用例子

    C++編程之?std::forward使用例子

    std::forward?是一個(gè)?C++11?中的模板函數(shù)，其主要作用是在模板函數(shù)或模板類中，將一個(gè)參數(shù)以“原樣”（forward）的方式轉(zhuǎn)發(fā)給另一個(gè)函數(shù)，這篇文章主要介紹了C++編程之?std::forward,需要的朋友可以參考下
    2023-03-03
  • C++超詳細(xì)分析紅黑樹

    C++超詳細(xì)分析紅黑樹

    這一篇我要跟大家介紹二叉搜索樹中的另一顆樹——紅黑樹，它主要是通過控制顏色來控制自身的平衡，但它的平衡沒有AVL樹的平衡那么嚴(yán)格
    2022-03-03

最新評(píng)論