数据结构

　　数据结构红黑树
　　和AVL树一样，红黑树也是自平衡二叉搜索树。红黑树同样解决了在特定情况下二叉搜索树会退化成链表的问题。但是红黑树又不像AVL树那样高度平衡，这就让红黑树在插入删除频繁的场合效率优于AVL树。但是在插入和删除操作较少，而查找频繁的场合AVL树则更胜一筹。实际上linux内核中实现了红黑树（linuxrbtree。h）。linux内核使用红黑树来管理和调度进程。C标准库的map也是用红黑树来实现的，而nginx中也使用红黑树来实现了定时器。下面我们就来学习一下这个作为很多牛X软件的底层数据结构红黑树（redblacktree）。红黑树的定义和特性
　　首先红黑树是一颗BST（二分查找树），但是红黑树每一个节点包含一个额外的域用来存储颜色属性（每一个节点要么为红色，要么为黑色）。一棵红黑树必须满足下面的性质：每一个节点都有颜色，或者为黑色或者为红色红黑树的根节点必须是黑色的叶子节点（叫做nil或者NULL节点）都是黑色的如果一个红色的节点有子节点，那么子节点必须是黑色的从任意一个节点出发沿着其子节点的所有路径到达叶子节点的黑色深度相同（这里的黑色深度指的是黑色节点的数量）。
　　如下图所示的例子就是一颗红黑树：
　　对于红黑树的每一个节点都至少包含下面列出的属性：颜色（color）键值（key）左孩子指针（lchild）右孩子指针（rchild）父节点指针（parent，根节点parent为空）
　　正是由于红黑树（redblacktree）的五条性质的约束，这使得红黑树从根节点出发到叶子节点的任何一条路径都不可能超过其他从根节点出发到叶子节点路径的两倍，这使得红黑树可以维持平衡。红黑树的基本操作
　　和AVL数类似，红黑树在调整平衡时也需要旋转操作。左旋
　　左旋操作步骤如下：
　　1）。初始状态：
　　2）。如果y有左子树，那么将x设为y的左子树的父节点
　　3）。将x的右子树设为
　　4）。如果x的父节点为NULL，那么将y设为根节点
　　5）。否则，如果x是其父节点p的左孩子，那么将p的左孩子设为y
　　6）。否则，将p的右孩子设为y
　　7）。将y的父节点设为p
　　7）。将x的父节点设为y
　　8）。将y的左子树设为x
　　右旋
　　右旋的操作步骤如下：
　　1）。初始状态
　　2）。如果x有右子树，将y设为x右子树的父节点
　　3）。将y的左子树设为
　　4）。如果y的父节点p是NULL，那么将x设为父节点
　　5）。否则，如果y是其父节点p的右孩子，那么将x设为p的右孩子
　　6）。否则，将x设为p的左孩子
　　7）。将x的父节点设为p
　　8）。将y的父节点设为x
　　9）。将x的右子树设为y
　　左右（LeftRight）旋转和右左（RightLeft）旋转
　　在左右旋转时，我们先进行左旋，然后再进行右旋，如下步骤：
　　1）。先左旋（如下图，对xy进行左旋）
　　2）。再进行右旋（再对yz进行右旋）
　　而我们在进行右左旋转时，是先进行右旋，然后再进行左旋，如下步骤：
　　1）。先右旋（如下图，对xy进行右旋）
　　2）。再进行左旋（如下图，对zy进行左旋）
　　红黑树的插入
　　对红黑树的插入操作，我们希望插入后对红黑树的5条性质违反越少越好，基于此，我将待插入的节点先标记为红色。然后按照BST的插入方法插入该节点。这里之所以将节点标为红色，是因为这样做可以保证两点，该节点插入后，如果插入位置是根节点，那么违反性质3，但是这种情况非常容易处理，直接将颜色设为黑色即可。如果插入位置不是根节点，那么它只违反性质4。只要针对性质4进行调整即可，反之标为黑色就会违背5，对性质5的调整要比性质4困难得多。
　　插入完成后，我进行调整使其满足红黑树的性质。具体的调整主要是做下面两件事：
　　1）。对节点进行颜色调整
　　2）。旋转操作
　　下面是插入操作的具体步骤：
　　1）。将待插入节点标为红色
　　2）。首先安装BST插入方法将待插入节点插入，不清楚BST插入方法的同学可以参考我之前的文章数据结构二叉搜索树。
　　3）。对插入后的树进行调整（insertfixup）使其仍然保持红黑树的性质。
　　我们这里重点来看看insertfixup算法：
　　我们假设插入的节点为x，p是x的父节点，z是x的祖父节点，那么fixup的步骤如下：
　　1）。如果p的颜色为黑色，那么不需要调整，fixup结束。
　　2）。如果p的颜色为红色，那么违反了4，做如下调整：
　　3）。如果p是z的左孩子，那么又分为下面三种情况：
　　Case1：如果z的右孩子是红色，那么将z的左孩子和右孩子的节点设为黑色，并将z的颜色设为红色。将x（当前调整的节点）设为z
　　Case2：否则如果当前调整节点x是p的右孩子，那么将x设为p对x进行左右（LeftRight）旋转。
　　Case3：将p的颜色设置为黑色，同时将z的颜色设置为红色对z进行右旋
　　4）。否则，做如下调整：如果x的祖父节点z的左孩子是红色的，那么将z的左孩子和右孩子设为黑色，同时将z设为红色将当前调整节点设为z否则如果当前调整节点x是其父节点p的左孩子，那么将p设为当前调整节点x，并且对x做右旋操作。将x的父节点p设为黑色，祖父节点z设为红色对z进行左旋操作。
　　5）。将根节点设为黑色。红黑树的删除
　　在红黑树中删除一个节点后，我们依然要保持其红黑树的性质。删除操作要比插入操作更为复杂一些。删除操作步骤如下：
　　1）。如果待删除节点z的左孩子和右孩子节点其中一个不是nil节点，那么将y设为待删除节点z的后继节点，否则将y设为z。（y临时保存待删除节点）
　　2）。如果y的左孩子不是nil节点，那么将y的左孩子赋给临时节点x，否则将y的右孩子赋给临时节点x。
　　3）。如果y的父节点为NULL，那么将x设为root节点
　　4）。将y节点从树上移除
　　5）。如果z跟y不是同一个节点，那么将z的key设为y的key
　　6）。如果y的颜色是黑色，那么需要调用deletefixup算法进行调整。
　　一个黑色节点的删除会违反红黑树性质5，因此需要调整，但是违反性质5调整起来非常困难，我们可以假想节点x（就是在上面删除步骤中替代了y位置的节点）多出来一个黑色，这样的话x就变成要么两个黑色，要么一红一黑，这就是违反了性质4了。但是毕竟x本身只有一种颜色，我们硬生生给它增加了另一种颜色，所以，这个新增加的颜色还是需要去除的，在满足下面三个条件后，新增加的颜色和去掉：x是根节点如果x是红黑复合节点，那么这个时候将x节点设为黑色即可经过适当的旋转和颜色调整后
　　下面是deletefixup算法的步骤：
　　1）。如果x不是根节点并且x的颜色是黑色的，那么重复下面的步骤：
　　2）。如果x是它的父节点的左孩子那么将w设为x的兄弟节点如果x的父节点的右孩子是红色的：
　　Case1：将x父节点的右孩子设为黑色将x父节点设为红色对x的父节点执行左旋操作将x父节点的右孩子赋给w如果w的左孩子和右孩子都是黑色：
　　Case2：将w的颜色设为红色将x的父节点赋给x否则如果w的右孩子的颜色是黑色的：
　　Case3：将w左孩子的颜色设为黑色将w设为红色对w执行右旋操作将x父节点的右孩子赋给w如果上面的所有情形都没有发生，那么执行下面Case4：
　　Case4：将w的颜色设为x父节点的颜色将x父节点的颜色设为黑色将w右孩子的颜色设为黑色对x执行左旋操作将x设为树的根节点
　　3）。如果x是它的父节点右孩子，那么操作步骤与2）中描述相同，只是将其中的左孩子改为右孩子，将其中的右孩子改为左孩子即可。
　　4）。将x的颜色设为黑色。
　　上面介绍了红黑树的插入和删除操作。对于红黑树的遍历与二叉搜索树相同，这里不再介绍。对于上面提到的后继节点的求法，文中没有介绍，其实也比较简单，可以看我下面用C语言实现的红黑树的源码。希望本文对大家理解红黑树有所帮助。rbtreeheaderfilerbtree。hauthor：程序驱动世界reversion：1。020210608ifndefRBTREEHdefineRBTREEHifdefcplusplusexternC｛endifincludestdint。hincludestdio。hincludestdlib。hincludestdarg。hdefineASSERT（condition）do｛if（condition）｛NULL；｝else｛fflush（stdout）；fprintf（stderr，ASSERTfailed：s，line：u，FILE，LINE）；fflush（stderr）；abort（）；｝｝while（0）defineRBRED0defineRBBLACK1typedefuint32structrbtreeiterator｛｝；structrbtreerbtreecreate（）；voidrbtreepreordertraversal（structrbtreetree）；voidrbtreeinordertraversal（structrbtreetree）；voidrbtreepostordertraversal（structrbtreetree）；voidrbtreeprint（structrbtreetree）；int32trbtreeexist（structrbtreetree，keytypekey）；rbtreeiteratortrbtreeinsert（structrbtreetree，keytypekey）；int32trbtreedelete（structrbtreetree，keytypekey）；voidrbtreedestory（structrbtreetree）；uint32trbtreenodecount（structrbtreetree）；rbtreeiteratortrbtreebegin（structrbtreetree）；rbtreeiteratortrbtreeend（structrbtreetree）；rbtreeiteratortrbtreenext（structrbtreetree，structrbtreeiteratoriter）；ifdefcplusplus｝endifendifRBTREEHrbtreecfilerbtree。cauthor：程序驱动世界reversion：1。020210608includestdio。hincludestdlib。hincludestring。hincludemath。hincluderbtree。hstructrbnode｛uint8｝；structrbtree｛uint32｝；xyayxcbcabstaticvoidrbtreeleftrotate（structrbtreetree，structrbnodex）｛settheparentofytotheparentofxif（！xparent）｛iftheparentofxisNULL，｝elseif（xxparentlchild）｛settheleftchildofxsparenttoy｝else｛settherightchildofxsparenttoy｝settheparentofxtoy｝yxaxycbcabstaticvoidrbtreerightrotate（structrbtreetree，structrbnodex）｛settheparentofytotheparentofxif（！xparent）｛iftheparentofxisNULL，｝elseif（xxparentrchild）｛setyastherightchildofxsparent｝else｛settheleftchildofxsparenttoy｝settheparentofxtoy｝staticvoidrbtreeinsertfixup（structrbtreetree，structrbnodez）｛Case2：thecoloroftheparentofthecurrentnodeisBLACKif（zparentcolorRBBLACK）｛Donotneedtofixup｝Case3：thecoloroftheparentofthecurrentnodeisREDwhile（zparentzparentcolorRBRED）｛if（zparentzparentparentlchild）｛if（yycolorRBRED）｛Case3。1thecoloroftheunclenodeofthecurrentnodeisREDzparentcolorRBBLACK；setthecolorofcurrentnodesparenttoBLACKycolorRBBLACK；settheunclescolortoBLACKzparentparentcolorRBRED；setthecolorofgrandparenttoRED｝elseif（zzparentrchild）｛Case3。2thecoloroftheunclenodeisBLACKsetthecurrentnodetoitsparentrbtreeleftrotate（tree，z）；leftrotate｝zparentcolorRBBLACK；Case3。3thecoloroftheunclenodeisBLACK，andthecurrentnodeistheleftchildofitsparentzparentparentcolorRBRED；setthegrandparentscolortoREDrbtreerightrotate（tree，zparentparent）；rightrotatewithgrandparentasthepivot｝else｛if（yycolorRBRED）｛Case3。1thecoloroftheunclenodeofthecurrentnodeisREDzparentcolorRBBLACK；setthecolorofcurrentnodesparenttoBLACKycolorRBBLACK；settheunclescolortoBLACKzparentparentcolorRBRED；setthecolorofgrandparenttoRED｝elseif（zzparentlchild）｛Case3。2thecoloroftheunclenodeisBLACKsetthecurrentnodetoitsparentrbtreerightrotate（tree，z）；leftrotate｝zparentcolorRBBLACK；Case3。3thecoloroftheunclenodeisBLACK，andthecurrentnodeistheleftchildofitsparentzparentparentcolorRBRED；setthegrandparentscolortoREDrbtreeleftrotate（tree，zparentparent）；rightrotatewithgrandparentasthepivot｝｝treerootcolorRBBLACK；｝staticvoidrbtreeinsertimpl（structrbtreetree，structrbnodez）｛ASSERT（tree！NULLz！NULL）；Case1：Thetreenodeisnil，justsetthetreenodetonodeAndmarkeditscolortoblack。if（treeroottreenil）｛treerootcolorRBBLACK；treenodecount1；｝while（x！treenil）｛if（zrbiter。keyxrbiter。key）｛｝else｛｝｝if（zrbiter。keyyrbiter。key）｛｝else｛｝zcolorRBRED；rbtreeinsertfixup（tree，z）；treenodecount1；｝staticstructrbnoderbtreeminimum（structrbtreetree，structrbnodex）｛ASSERT（tree！NULL）；if（！node）｛｝while（nodelchild！treenil）｛｝｝staticstructrbnoderbtreemaximum（structrbtreetree，structrbnodex）｛ASSERT（tree！NULL）；if（！node）｛｝while（noderchild！treenil）｛｝｝staticstructrbnoderbtreesuccessor（structrbtreetree，structrbnodex）｛ASSERT（tree！NULLx！NULL）；if（xrchild！treenil）｛returnrbtreeminimum（tree，xrchild）；｝while（yy！treenilxyrchild）｛｝if（！y）｛｝｝staticstructrbnoderbtreepredecessor（structrbtreetree，structrbnodex）｛ASSERT（tree！NULLx！NULL）；if（xlchild！treenil）｛returnrbtreemaximum（tree，xlchild）；｝while（yy！treenilxyrchild）｛｝if（！y）｛｝｝staticvoidrbtreedeletefixup（structrbtreetree，structrbnodex）｛while（x！treerootxcolorRBBLACK）｛xscolorisBLACKandxisnottherootofthetreeif（xxparentlchild）｛ifxistheleftchildofitsparent，setthewasxssiblingchildif（wcolorRBRED）｛Case1：xssiblingcolorisRED，soxsparentandwschildsareallBLACKwcolorRBBLACK；1），setxssiblingnodetoBLACKxparentcolorRBRED；2），setxsparentcolortoREDrbtreeleftrotate（tree，xparent）；3），4），resetthexssiblingnodeaftertherotation｝elseif（wlchildcolorRBBLACKwrchildcolorRBBLACK）｛Case2：xssiblingcolorisBLACK，andthechildrenofxssiblingareallBLACKwcolorRBRED；1），setthesiblingnodecolortoRED2），setthexequaltoitsparent｝else｛if（wrchildcolorRBBLACK）｛Case3：xssiblingcolorisBLACK，andtherightchildofwisBLACKwhileitsleftchildisREDwlchildcolorRBBLACK；1），settheleftchildofwtoBLACKwcolorRBRED；2），setthewscolottoREDrbtreerightrotate（tree，w）；3），4），resetthesiblingnodeafterrotation｝Case4：xssiblingcolorisBLACK，therightchildofwisRED，1），settheparentcolortowxparentcolorRBBLACK；2），setxparentcolortoBLACKwrchildcolorRBBLACK；3），setthecolorofrightchildofsiblingnodetoBLACKrbtreeleftrotate（tree，xparent）；4），5），setxasrootnodeofthetree｝｝else｛ifxistherightchildofitsparent，setthewasxssiblingchildif（wcolorRBRED）｛Case1：xssiblingcolorisRED，soxsparentandwschildsareallBLACKwcolorRBBLACK；1），setxssiblingnodetoBLACKxparentcolorRBRED；2），setxsparentcolortoREDrbtreerightrotate（tree，xparent）；3），4），resetthexssiblingnodeaftertherotation｝elseif（wrchildcolorRBBLACKwlchildcolorRBBLACK）｛Case2：xssiblingcolorisBLACK，andthechildrenofxssiblingareallBLACKwcolorRBRED；1），setthesiblingnodecolortoRED2），setthexequaltoitsparent｝else｛Case3：xssiblingcolorisBLACK，andtheleftchildofwisBLACKwhileitsrightchildisREDif（wlchildcolorRBBLACK）｛wrchildcolorRBBLACK；1），settherightchildofwtoBLACKwcolorRBRED；2），setthewscolottoREDrbtreeleftrotate（tree，w）；3），4），resetthesiblingnodeafterrotation｝Case4：xssiblingcolorisBLACK，theleftchildofwisRED，1），settheparentcolortowxparentcolorRBBLACK；2），setxparentcolortoBLACKwlchildcolorRBBLACK；3），setthecolorofleftchildofsiblingnodetoBLACKrbtreerightrotate（tree，xparent）；4），5），setxasrootnodeofthetree｝｝｝xcolorRBBLACK；setthecolorofxtoBLACK｝staticstructrbnoderbtreedeleteimpl（structrbtreetree，structrbnodez）｛ASSERT（tree！NULLz！NULL）；if（zlchildtreenilzrchildtreenil）｛theleftandrightchildofthezisnil，setytoz｝else｛yrbtreesuccessor（tree，z）；setytothezssuccessornode｝if（ylchild！treenil）｛｝else｛otherwisesettherightchildofytox｝settheparentofytotheparentofxif（yparentNULL）｛theparentofyisNULL，｝elseif（yyparentlchild）｛ifyisitsparentsleftchild，｝else｛setxastherightchildofysparent｝if（y！z）｛ifyisnotequaltozzrbiter。keyyrbiter。copythekeyofytothekeyofz，herewewontchangethecolor｝if（ycolorRBBLACK）｛rbtreedeletefixup（tree，x）；ifthecolorofyisBLACK，thenneedtofixupx｝treenodecount1；｝staticvoidrbtreepreordertraversalimpl（structrbtreetree，structrbnodenode）｛ASSERT（node！NULL）；if（node！treenil）｛printf（ld，noderbiter。key）；rbtreepreordertraversalimpl（tree，nodelchild）；rbtreepreordertraversalimpl（tree，noderchild）；｝｝staticvoidrbtreeinordertraversalimpl（structrbtreetree，structrbnodenode）｛ASSERT（node！NULL）；if（node！treenil）｛rbtreeinordertraversalimpl（tree，nodelchild）；printf（ld，noderbiter。key）；rbtreeinordertraversalimpl（tree，noderchild）；｝｝staticvoidrbtreepostordertraversalimpl（structrbtreetree，structrbnodenode）｛ASSERT（tree！NULLnode！NULL）；if（node！treenil）｛rbtreepostordertraversalimpl（tree，nodelchild）；rbtreepostordertraversalimpl（tree，noderchild）；printf（ld，noderbiter。key）；｝｝defineSPACECOUNT10staticvoidrbtreeprintimpl（structrbtreetree，structrbnodenode，intspace）｛if（treeNULL）｛｝spaceSPACECOUNT；if（nodetreenil）｛for（intiSPACECOUNT；i）｛printf（）；｝printf（s：s，nil，black）；｝rbtreeprintimpl（tree，noderchild，space）；printf（）；for（intiSPACECOUNT；i）｛printf（）；｝printf（ld：s，noderbiter。key，nodecolorRBRED？red：black）；rbtreeprintimpl（tree，nodelchild，space）；｝staticstructrbnoderbtreesearch（structrbtreetree，keytypekey）｛while（node！treenilnoderbiter。key！key）｛if（keynoderbiter。key）｛｝else｛｝｝｝staticstructrbnoderbtreecreatenode（structrbtreetree，keytypekey）｛structrbnodenode（structrbnode）malloc（sizeof（structrbnode））；if（！node）｛｝noderbiter。nodeparentNULL；nodecolorRBBLACK；｝staticvoidrbtreedestroyimpl（structrbtreetree，structrbnodenode）｛if（nodetreenil）｛｝if（nodelchild！treenil）｛rbtreedestroyimpl（tree，nodelchild）；｝if（noderchild！treenil）｛rbtreedestroyimpl（tree，noderchild）；｝free（node）；｝structrbtreerbtreecreate（）｛structrbtreetree（structrbtree）malloc（sizeof（structrbtree））；ASSERT（tree！NULL）；treenil（structrbnode）malloc（sizeof（structrbnode））；ASSERT（treenil！NULL）；treenillchildNULL；treenilrchildNULL；treenilparentNULL；treenilcolorRBBLACK；treenodecount0；｝voidrbtreepreordertraversal（structrbtreetree）｛rbtreepreordertraversalimpl（tree，treeroot）；｝voidrbtreeinordertraversal（structrbtreetree）｛rbtreeinordertraversalimpl（tree，treeroot）；｝voidrbtreepostordertraversal（structrbtreetree）｛rbtreepostordertraversalimpl（tree，treeroot）；｝voidrbtreeprint（structrbtreetree）｛ASSERT（tree！NULL）；rbtreeprintimpl（tree，treeroot，0）；｝int32trbtreeexist（structrbtreetree，keytypekey）｛ASSERT（tree！NULL）；if（treeroot！treenil）｛returnrbtreesearch（tree，key）？0：1；｝return1；｝rbtreeiteratortrbtreeinsert（structrbtreetree，keytypekey）｛ASSERT（tree！NULL）；structrbnodefnoderbtreesearch（tree，key）；if（rbtreesearch（tree，key）！treenil）｛keyalreadyexist。｝structrbnodenoderbtreecreatenode（tree，key）；if（node！treenil）｛rbtreeinsertimpl（tree，node）；｝return0；erroroccurred｝int32trbtreedelete（structrbtreetree，keytypekey）｛ASSERT（tree！NULL）；structrbnodenoderbtreesearch（tree，key）；if（nodetreenil）｛return1；doesnotexist｝noderbtreedeleteimpl（tree，node）；free（node）；return0；｝voidrbtreedestory（structrbtreetree）｛ASSERT（tree！NULL）；rbtreedestroyimpl（tree，treeroot）；free（treenil）；free（tree）；｝uint32trbtreenodecount（structrbtreetree）｛ASSERT（tree！NULL）；｝rbtreeiteratortrbtreebegin（structrbtreetree）｛ASSERT（tree！NULL）；structrbnodenoderbtreeminimum（tree，treeroot）；if（nodetreenil）｛returnNULL；｝｝rbtreeiteratortrbtreeend（structrbtreetree）｛returnNULL；｝rbtreeiteratortrbtreenext（structrbtreetree，structrbtreeiteratoriter）｛ASSERT（tree！NULL）；if（！iter）｛returnNULL；｝structrbnodex（structrbnode）（（（char）iter）（（sizet）（（（structrbnode）0）rbiter）））；structrbnodenoderbtreesuccessor（tree，x）；if（nodetreenil）｛returnNULL；｝｝