数据结构 红黑树的详解分享

—-想了解数据结构 红黑树的详解分享的全部内容且更多的C语言教程关注<计算机技术网>

数据结构 红黑树的详解

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

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页:
  • 上一页
  • 1
  • 2
  • 3
  • 下一页
  • 数据结构 红黑树的详解

    上一篇:C语言动态内存分配的详解

    栏    目:C语言

    下一篇:C语言数据结构实现链表去重的实例

    数据结构 红黑树的详解分享标题:数据结构 红黑树的详解

    数据结构 红黑树的详解分享地址:www.dtcnnet.com/cyuyan/42346.html

    分享到:

    更多C语言

    您可能感兴趣的文章

    • 10-15C语言数据结构实现链表去重的实例
    • 10-15C语言动态内存分配的详解
    • 10-15C++数据结构之文件压缩(哈夫曼树)实例详解
    • 10-14C++中的内存对齐实例详解
    • 10-14C语言实现静态顺序表的实例详解
    • 10-14C语言实现进制转换函数的实例详解
    • 10-14C语言模拟实现atoi函数的实例详解
    • 10-13C++中的四个默认成员函数与运算符重载详解
    • 10-13关于C++对象继承中的内存布局示例详解
    • 10-13C/C++ 浅拷贝和深拷贝的实例详解

    数据结构 红黑树的详解
    数据结构 红黑树的详解

    阅读排行

    • 1C# winform 模拟键盘输入自动接入访问网
    • 2JS实现页面数据懒加载
    • 3企业网站建设之企业网站设计分析
    • 4ASP.NET MVC3手把手教你构建Web
    • 5Java实现把文件及文件夹压缩成zip
    • 6SEO初学者必看:关于网站优化的100个
    • 7CSS中对RGB颜色的使用详解
    • 8数据库中identity字段不必是系统产生的
    • 9C语言实现静态顺序表的实例详解
    • 10CentOS 7下部署php7.1和开启MySQL扩展的方

    推荐教程

    • 10-14Angular 多模块项目构建过程
    • 10-14网站推广前先要做好3点分析
    • 10-14C#如何自动识别文件的编码
    • 10-14将MSSQL Server 导入/导出到远程服务器教
    • 10-14百度谷歌等搜索引擎的工作原理及网
    • 10-13网站主机教程(7):网站主机的数据库技
    • 10-13ASP.NET MVC5 网站开发框架模型、数据存
    • 10-13C语言实现单链表实现方法
    • 10-132014 怎么坚持做好白帽SEO?
    • 10-13c#中SqlTransaction——事务详解

    本文来自网络收集,不代表计算机技术网立场,如涉及侵权请点击右边联系管理员删除。

    如若转载,请注明出处:https://www.ctvol.com/c-cdevelopment/488352.html

    (0)
    上一篇 2020年11月12日
    下一篇 2020年11月12日

    精彩推荐