加入收藏 | 设为首页 | 会员中心 | 我要投稿 湖南网 （https://www.hunanwang.cn/）- 科技、建站、经验、云计算、5G、大数据,站长网!
当前位置： 首页 > 创业 > 正文

数据布局 红黑树的详解

发布时间：2020-12-30 14:33:19 所属栏目：创业 来源：网络整理
导读：数据布局 红黑树的详解 红黑树是具有下列着色性子的二叉查找树： 1.每一个节点可能着赤色，可能着玄色。 2.根是玄色的。 3.假如一个节点是赤色的，那么它的子节点必需是玄色。 4.从一个节点到一个NULL指针的每一条路径必需包括沟通数量标玄色节点。 下面是一
副问题[/!--empirenews.page--]

数据布局 红黑树的详解

红黑树是具有下列着色性子的二叉查找树：

1.每一个节点可能着赤色，可能着玄色。

2.根是玄色的。

3.假如一个节点是赤色的，那么它的子节点必需是玄色。

4.从一个节点到一个NULL指针的每一条路径必需包括沟通数量标玄色节点。

下面是一棵红黑树。

数据布局 红黑树的详解


1.自底向上插入

凡是把新项作为树叶放到树中。假如我们把该项涂成玄色，那么违背前提4，由于将会成立一条更长的黑节点路径。因此这一项必需涂成赤色。假如它的父节点是玄色的，插入完成。假如父节点是赤色的，那么违背前提3。在这种环境下我们必需调解该树以满意前提3。用于完成这项目使命的根基操纵是颜色的改变和树的旋转。

假如新插入的节点的父节点是玄色，那么插入完成。

假如父节点是赤色，那么有几种气象必要思量。起首，假设这个父节点的兄弟是玄色（NULL节点约定为玄色）。这对付插入3或8是合用的，但对插入99不合用。令X是新加的树叶，P是它的父节点，S是该父节点的兄弟，G是祖父节点环境一：父节点的兄弟是玄色的。通过操纵使得达到A,B,C的玄色路径保持稳固（满意前提4），并且没有持续的赤色节点（满意前提3）.。

数据布局 红黑树的详解


数据布局 红黑树的详解


环境二：父节点的兄弟是赤色的。

数据布局 红黑树的详解


数据布局 红黑树的详解


2.自顶向下删除

红黑树中的删除可所以自顶向下举办。每一件事变都归结于可以或许删除一片树叶。这是由于，要删除一个带有两个儿子的节点，我们用右子树上的最末节点取代它；该节点最多有一个儿子，然后将该节点删除。只有一个右儿子的节点可以用沟通的方法删除，而只有一个左儿子的节点通过用其左子树上最大的节点替代，然后可将该节点删除。可是若是删除的节点不是赤色的，那么就会粉碎红黑树的均衡。办理的要领就是担保从上到下删除时代树叶是赤色的。

在整个接头中，令X为当前节点，T是它的兄弟，而P是它们的傅沧。开始时我们把根涂成赤色。当沿着树向下遍历时，我们想法担保X是赤色的。当我们达到一个新的节点时，我们要确信P是赤色的而且X和T是玄色的（由于不能有两个相连的赤色节点）。存在两种首要气象。 环境一：X有两个玄色儿子。此时有三个子环境。 （1）T有两个黑儿子，那么我们可以翻转X、T、P的颜色来保持这种稳固性。

数据布局 红黑树的详解


（2）T的左儿子是赤色的

数据布局 红黑树的详解


（3）T的右儿子是赤色的

数据布局 红黑树的详解


环境二：X的儿子之一是红的。在这种环境下，我们落到下一层，获得新的X、T、P。假如荣幸，X落在红儿子上。则我们继承前行。假如不是这样，那么我们知道T将是红的，而X和P将是黑的。我们可以旋转T和P，使得X的新父亲是红的；虽然X和它的祖父是黑的。此时我们可以回到第一种主环境。

数据布局 红黑树的详解


3.红黑树的实现 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 实现文件 

// 
// 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,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同时为红节点才举办调解 */ 
 if (X == NullNode || !(P->Color == RED && X->Color == RED)) 
 return ; 
 
 
 Sibling = GetSibling(GP,P); 
 
 if (Sibling == NULL) 
 return ; 
 
 
 /* GP,X是成字型，调解为一字型 */ 
 if ((GP->Element < Item) != (P->Element < Item)){ 
 P = Rotate(GP,&Origin,Item); 
 X = Origin; 
 } 
 
 GP = Rotate(GGP,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,R->Element); 
  
 }else if (Sibling->Right->Color == RED){ 
 X->Color = RED; 
 P->Color = BLACK; 
 Sibling->Color = RED; 
 Sibling->Right->Color = BLACK; 
  
 GP = Rotate(GP,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,Sibling->Element); 
  P = Origin; 
  GP->Color = BLACK; 
  P->Color = RED; 
  _HandleReorientForRemove(Item); 
  
 } 
  
 /* 规复X,PX,GP。因为X是当前节点 假如当前节点正是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); 
}

（编辑：湖南网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!
相关内容
    推荐文章
    站长推荐
    热点阅读

      【免责声明】本站内容转载自互联网，其发布内容言论不代表本站观点，如果其链接、内容的侵犯您的权益，烦请提交相关链接至邮箱bqsm@foxmail.com我们将及时予以处理。

      建议您使用1920×1080分辨率、谷歌浏览器Google Chrome、Microsoft Edge以获得本站的最佳浏览效果

      Copygight © 2008-2022 https://www.hunanwang.cn/ All Rights Reserved. 湖南网