数据结构 红黑树的详解

数据结构 红黑树的详解

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

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,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同时为红节点才进行调整 */
 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是当前节点 如果当前节点正是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;
} 

以上就是关于数据结构与算法中红黑二叉树的详解,如有疑问请留言或者到本站的社区讨论,感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!

(0)

相关推荐

  • 老生常谈PHP中的数据结构:DS扩展

    PHP7以上才能安装和使用该数据结构扩展,安装比较简单: 1. 运行命令 pecl install ds 2. 在php.ini中添加 extension=ds.so 3. 重启PHP或重载配置 Collection Interface:包含本库中所有数据结构通用功能的基本interface. It guarantees that all structures are traversable, countable, and can be converted to json using json_

  • C++数据结构之文件压缩(哈夫曼树)实例详解

    C++数据结构之文件压缩(哈夫曼树)实例详解 概要: 项目简介:利用哈夫曼编码的方式对文件进行压缩,并且对压缩文件可以解压 开发环境:windows vs2013 项目概述:         1.压缩 a.读取文件,将每个字符,该字符出现的次数和权值构成哈夫曼树 b.哈夫曼树是利用小堆构成,字符出现次数少的节点指针存在堆顶,出现次数多的在堆底 c.每次取堆顶的两个数,再将两个数相加进堆,直到堆被取完,这时哈夫曼树也建成 d.从哈夫曼树中获取哈夫曼编码,然后再根据整个字符数组来获取出现了得字符的编

  • 数据结构 双机调度问题的实例详解

    数据结构 双机调度问题的实例详解 1.问题描述 双机调度问题,又称独立任务最优调度:用两台处理机A和B处理n个作业.设第i个作业交给机器A处理时所需要的时间是a[i],若由机器B来处理,则所需要的时间是b[i].现在要求每个作业只能由一台机器处理,每台机器都不能同时处理两个作业.设计一个动态规划算法,使得这两台机器处理完这n个作业的时间最短(从任何一台机器开工到最后一台机器停工的总的时间). 研究一个实例:n=6, a = {2, 5, 7, 10, 5, 2}, b = {3, 8, 4, 1

  • java 数据结构之栈与队列

    java 数据结构之栈与队列 一:对列 队列是一种先进先出的数据结构 实现代码: package Queue; /* * 使用java构建队列,并模拟实现队列的入队和出对方法 */ public class Queue { //队列类 private int maxSize; //定义队列的长度 private int[] arrQueue; //队列 private int rear; //定义队列的尾指针 private int front; //定义队列的头指针 private int e

  • C数据结构中串简单实例

    C数据结构中串简单实例 运行截图: 实例代码: #include "stdio.h" #include "string.h" #include "stdlib.h" #define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 #define MAXSIZE 40 /* 存储空间初始分配量 */ typedef int Status; /* Status是函数的类型,其值是函数结果状态代码

  • 数据结构 中数制转换(栈的应用)

    数据结构 中数制转换(栈的应用) 问题描述: 将一个非负的十进制整数N转换为另一个等价的基为B的B进制数的问题. 解答:按除2取余法,得到的余数依次是1.0.1.1,则十进制数转化为二进制数为1101. 分析:由于最先得到的余数是转化结果的最低位,最后得到的余数是转化结果的最高位,因此很容易用栈来解决. 代码如下: #include<stdio.h> #include<malloc.h> #include<stdlib.h> typedef struct Node {

  • 数据结构 红黑树的详解

    数据结构 红黑树的详解 红黑树是具有下列着色性质的二叉查找树: 1.每一个节点或者着红色,或者着黑色. 2.根是黑色的. 3.如果一个节点是红色的,那么它的子节点必须是黑色. 4.从一个节点到一个NULL指针的每一条路径必须包含相同数目的黑色节点. 下面是一棵红黑树. 1.自底向上插入 通常把新项作为树叶放到树中.如果我们把该项涂成黑色,那么违反条件4,因为将会建立一条更长的黑节点路径.因此这一项必须涂成红色.如果它的父节点是黑色的,插入完成.如果父节点是红色的,那么违反条件3.在这种情况下我们

  • C++详细实现红黑树流程详解

    目录 红黑树的概念 红黑树的性质 红黑树的定义与树结构 插入 新增结点插入后维护红黑树性质的主逻辑 旋转 验证 红黑树与AVl树的比较 红黑树的应用 红黑树的概念 红黑树,是一种二叉搜索树,但在每个结点上增加一个存储位表示结点的颜色,可以是Red或Black. 通过对任何一条从根到叶子的路径上各个结点着色方式的限制,红黑树确保没有一条路径会比其他路径长出俩倍,因而是接近平衡的 概念总结: 红黑树是二叉搜索树的升级,结点里面存放的成员col标记当前结点的颜色,它的最长路径最多是最短路径的二倍,红黑

  • Java数据结构之散列表详解

    目录 介绍 1 散列表概述 1.1 散列表概述 1.2 散列冲突(hash collision) 2 散列函数的选择 2.1 散列函数的要求 2.2 散列函数构造方法 3 散列冲突的解决 3.1 分离链接法 3.2 开放定址法 3.3 再散列法 4 散列表的简单实现 4.1 测试 介绍 本文详细介绍了散列表的概念.散列函数的选择.散列冲突的解决办法,并且最后提供了一种散列表的Java代码实现. 数组的特点是寻址容易,插入和删除困难:而链表的特点是寻址困难,插入和删除容易.而对于tree结构,它们

  • ES6新增数据结构WeakSet的用法详解

    WeakSet和Set类似,同样是元素不重复的集合,它们的区别是WeakSet内的元素必须是对象,不能是其它类型. 特性: 1.元素必须是对象. 添加一个number类型的元素. const ws = new WeakSet() ws.add(1) 结果是报类型错误. TypeError: Invalid value used in weak set 添加一个对象. const ws = new WeakSet() var a = {p1:'1', p2:'2'} ws.add(a) conso

  • python算法与数据结构之冒泡排序实例详解

    一.冒泡排序介绍 冒泡排序(英语:Bubble Sort)是一种简单的排序算法.它重复地遍历要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来.遍历数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成.这个算法的名字由来是因为越小的元素会经由交换慢慢"浮"到数列的顶端. 二.冒泡排序原理 比较相邻的元素.如果第一个比第二个大,就交换他们两个. 对每一对相邻元素做同样的工作,从开始第一对到结尾的最后一对.这一步做完,最后的元素应该会是最大的数. 针对所有的

  • c++ 数据结构map的使用详解

    map的常用用法 map 表示映射,可以将任何基本类型(包括 STL 容器)映射到任何基本类型(包括 STL 容器),例如可以建立如 int 到 double,string 到 int 的映射等. map 提供一对一的 hash,该功能类似 Python 的字典: 第一个称为键( key ),每个关键字只能在 map 中出现一次: 第二个称为该键的值( value ): 1. 头文件 <bits/stdc++.h> 头文件已经包括了该头文件. 2. 定义 定义 map 如下,参数的第一个为 k

  • Java数据结构之单链表详解

    一.图示 二.链表的概念及结构 链表是一种物理存储结构上非连续存储结构,数据元素的逻辑顺序是通过链表中的引用链接次序实现的 . 实际中链表的结构非常多样,以下情况组合起来就有8种链表结构: 单向.双向 带头.不带头 循环.非循环 今天,我们实现的是一个 单向 无头 非循环的链表. 下面是此链表的结构组成. 三.单链表的实现 (1)定义一个节点类型 我们创建一个 ListNode 的类作为节点类型,那么我们如何定义成员属性呢? 通过上面的结构分析,我们需要定义两个成员变量 val --作为该节点的

  • Java数据结构顺序表用法详解

    目录 1.什么是顺序表 2.顺序表的基本功能和结构 3.顺序表基本功能的实现和解析 1.判断线性表是否为空 2.获取指定位置的元素 3.向线性表表添加元素 4.在位置i处插入元素 5.删除指定位置的元素,并返回该元素 6.查找t第一次出现的位置 7.手动扩容方法 1.什么是顺序表 在程序中,经常需要将一组(通常是同为某个类型的)数据元素作为整体管理和使用,需要创建这种元素组,用变量记录它们,传进传出函数等.一组数据中包含的元素个数可能发生变化(可以增加或删除元素). 对于这种需求,最简单的解决方

  • C语言数据结构之单向链表详解分析

    链表的概念:链表是一种动态存储分布的数据结构,由若干个同一结构类型的结点依次串连而成. 链表分为单向链表和双向链表. 链表变量一般用指针head表示,用来存放链表首结点的地址. 每个结点由数据部分和下一个结点的地址部分组成,即每个结点都指向下一个结点.最后一个结点称为表尾,其下一个结点的地址部分的值为NULL(表示为空地址). 特别注意:链表中的各个结点在内存中是可以不连续存放的,具体存放位置由系统分配. 例如:int *ptr ; 因此不可以用ptr++的方式来寻找下一个结点. 使用链表的优点

  • C语言数据结构之二分法查找详解

    问题:在有序数组中查找给定元素的下标goal. 在查找一个数组元素的下标,可以用循环来解决,但是如果一个数足够大,比如说手机的价格,用循环来查找,就相当于叫一个人猜,从0开始,需要猜很久.这时候就出现了二分查找,也叫对半查找. 对半查找顾名思义就是猜一次,下次猜的内容就减少一半              这时候定义一个变量left表示最左边元素的下标,在定义一个right表示最右边元素的下标,而mid就表示中间元素的下标. 当中间值小于目标值,left重新定义. if (mid < goal)

随机推荐