今天给各位分享c语言红黑树例子的知识，其中也会对c实现红黑树进行解释，如果能碰巧解决你现在面临的问题，别忘了关注本站，现在开始吧！
本文目录一览：
1、红黑树—简单易懂2、二叉查找树之四：红黑树删除结点3、红黑树详解
红黑树—简单易懂
这样说呢，可能大家也猜到了是【二分查找法】，通过这个例子呢，主要想引出的是树，看下面的图片：
程序中的树呢，其实是我们日常看到的树的倒影，或者发挥一下想象，倒影也可以是树根
二叉查找树，Binary Search Tree 「BST」，要想了解二叉查找树呢，首先我们需要了解一下二叉查找树都有哪些特性呢？
看个图就轻松理解上面三句话的意思了:
上图，结合二叉查找树的三条约束来看，非常好，没有什么问题。再来看一个图，依旧符合上面三条约束，感觉有问题吗？
这是一个走路一米六，一米八的树
这是一个畸形的树，大风一挂很可能被折断的树
从程序的角度来说这个树不够平衡，查找次数或时间复杂度 O(h)可能会随着一条腿长无限增长
理科生在高中学习生物时学过一个关键字「去除顶端优势」，通过去除植物顶端优势，侧芽会迅速生长，慢慢变得强壮和平衡， 红黑树其实就是去除二叉查找树顶端优势的解决方案，从而达到树的平衡
红黑树，Red-Black Tree 「RBT」是一个自平衡(不是绝对的平衡)的二叉查找树(BST)，树上的每个节点都遵循下面的规则:
可能大家还是很懵逼，不过没事，多练习几次就熟悉了。
红黑树有两大操作：
我们会先尝试recolor，如果recolor不能达到红黑树的四个要求，然后我们尝试rotation，其实红黑树的关键玩法就是弄清楚recolor和rotation的规则，接下来我们看一下详细的算法公式吧。
假设我们插入的新节点为X
接下来看下图：
跟着上面的公式走：
上面说的是X的uncle为红色的情况，接下来我们看一下X的uncle为黑色的情况
当uncle节点为黑色的时候，我们第一步考虑的是旋转，这里呢我们可以先不关注红黑树的4个规则，主要是演示如何旋转的。
这种情况很简单，想象这是一根绳子，手提起P节点，然后变色即可，如下图：
变色：X是当前节点，P是X的parent节点，U是X的uncle节点，G是grand parent节点。P节点是根节点变黑色，G变成和X一样的颜色，也就是红色。完成
先进行左旋：使X的父节点P被X取代，同时父节点P成为X的左孩子，然后在应用 左左情况 ，如下图：
像左左一样，看成一根绳子。手提起P节点，然后变色即可，如下图：
先右旋：使 X 的父节点 P 被 X 取代，同时父节点 P 成为 X 的右孩子，然后再应用 右右情况 ，如下图：
通过上述过程，想必大家对红黑树有了一定的了解。以后在提到红黑树的时候，就不会那么头大了。本文参照 日拱一兵 公众号中的文章”红黑树，超强动静图详解，简单易懂”.
参考文章
二叉查找树之四：红黑树删除结点
红黑树的特性（规则）如下：
1.结点是红色或黑色。
2.根结点是黑色。
3.每个叶子结点都是黑色的空结点（NIL结点）。
4.每个红色结点的两个子结点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色结点)
5.从任一结点到其每个叶子的所有路径都包含相同数目的黑色结点。
首先，按照二叉查找树删除结点的规则来删除结点。这样删除红黑树的结点会对规则产生影响：
上图的这颗红黑树，待删除的是黑色结点1，有一个右孩子。根据二叉查找树的删除流程，我们让右孩子结点6直接取代结点1：
显然，这颗新的二叉树打破了两个规则：
规则4. 每个红色结点的两个子结点都是黑色。
规则5. 从任一结点到其每个叶子的所有路径都包含相同数目的黑色结点。
第一步：如果待删除结点有两个非空的孩子结点，转化成待删除结点只有一个孩子（或没有孩子）的情况。
上面例子是一颗红黑树的局部，标数字的三角形代表任意形态的子树，假设结点8是待删除结点。
根据二叉查找树删除流程，由于结点8有两个孩子，我们选择仅大于8的结点10复制到8的位置，结点颜色变成待删除结点的颜色：
接下来我们需要删除红色的结点10：
红色结点10能成为仅大于8的结点，必定没有左孩子结点，所以问题转换成了待删除结点只有一个右孩子（或没有孩子）的情况。接下来我们进入第二步。
第二步：根据待删除结点和其唯一子结点的颜色，分情况处理。
情况1 ，自身是红色，子结点是黑色：
这种情况最简单，按照二叉查找树的删除操作，删除结点1即可：
情况2 ，自身是黑色，子结点是红色：
这种情况也很简单，首先按照二叉查找树的删除操作，删除结点1：
此时，这条路径凭空减少了一个黑色结点，那么我们把结点2变成黑色即可：
情况3 ，自身是黑色，子结点也是黑色，或者子结点是空叶子结点：
这种情况最复杂，涉及到很多变化。首先我们还是按照二叉查找树的删除操作，删除结点1：
显然，这条路径上减少了一个黑色结点，而且结点2再怎么变色也解决不了。
这时候我们进入第三步，专门解决父子双黑的情况。
第三步：遇到双黑结点，在子结点顶替父结点之后，分成6种子情况处理。
子情况1 ，结点2是红黑树的根结点：
此时所有路径都减少了一个黑色结点，并未打破规则，不需要调整。
子情况2 ，结点2的父亲、兄弟、侄子结点都是黑色：
此时，我们直接把结点2的兄弟结点B改为红色：
这样一来，原本结点2所在的路径少了一个黑色结点，现在结点B所在的路径也少了一个黑色结点，两边“扯平”了。
可是，结点A以下的每一条路径都减少了一个黑色结点，与结点A之外的其他路径又造成了新的不平衡啊？
没关系，我们让结点A扮演原先结点2的角色，进行递归操作，重新判断各种情况。
子情况3 ，结点2的兄弟结点是红色：
首先以结点2的父结点A为轴，进行左旋：
然后结点A变成红色、结点B变成黑色：
这样的意义是什么呢？结点2所在的路径仍然少一个黑色结点呀？
别急，这样的变化有可能转换成子情况4、5、6中的任意一种，在子情况4、5、6当中会进一步解决。
子情况4 ，结点2的父结点是红色，兄弟和侄子结点是黑色：
这种情况，我们直接让结点2的父结点A变成黑色，兄弟结点B变成红色：
这样一来，结点2的路径补充了黑色结点，而结点B的路径并没有减少黑色结点，重新符合了红黑树的规则。
子情况5 ，结点2的父结点随意，兄弟结点B是黑色右孩子，左侄子结点是红色，右侄子结点是黑色：
这种情况下，首先以结点2的兄弟结点B为轴进行右旋：
接下来结点B变为红色，结点C变为黑色：
这样的变化转换成了子情况6。
子情况6 ，结点2的父结点随意，兄弟结点B是黑色右孩子，右侄子结点是红色：
首先以结点2的父结点A为轴左旋：
接下来让结点A和结点B的颜色交换，并且结点D变为黑色：
这样是否解决了问题呢？
经过结点2的路径由（随意+黑）变成了（随意+黑+黑），补充了一个黑色结点；
经过结点D的路径由（随意+黑+红）变成了（随意+黑），黑色结点并没有减少。
所以，这时候重新符合了红黑树的规则。
以上就是红黑树删除的全过程。
给定下面这颗红黑树，待删除的是结点17：
第一步，由于结点17有两个孩子，子树当中仅大于17的结点是25，所以把结点25复制到17位置，保持黑色：
接下来，我们需要删除原本的结点25：
这个情况正好对应于第二步的情况三，即待删除结点是黑色，子结点是空叶子结点。
于是我们删除框框中结点25，进入第三步：
此时，框框中的结点虽然是空叶子结点，但仍然可以用于判断局面，当前局面符合子情况5的镜像：
于是我们通过左旋和变色，把子树转换成情况6的镜像：
再经过右旋、变色，子树最终成为了下面的样子：
这样一来，整颗二叉树又重新符合了红黑树的规则。
红黑树详解
首先，我们来了解一下二叉查找树,二叉查找树具备以下几个特点：
1、左子树上所有节点的值均小于或等于它的根节点的值；
2、右子树上所有节点的值均大于或等于它的根节点的值；
3、左右子树也分别为二叉排序树。
下面我们以一棵典型的二叉查找树来查找值为10的节点：
以上图例正是典型的二分查找的思想，查找所需的最大次数等同于二叉查找树的高度。在往树中插入新节点的时候也要用类似的方法，通过一层一层地比较大小从而找到新节点适合插入的位置。但是即便如此，二叉查找树依旧存在它的缺陷，并且此缺陷恰恰体现在插入新节点的时候。请看下面图例展示：
这样的瘸腿形态虽然也符合二叉查找树的特性，但是查找的性能却大打折扣，几乎变成了线性数据结构。为了解决二叉查找树多次插入新节点而导致的不平衡问题，红黑树便应运而生了。
红黑树是一种自平衡的二叉查找树，除了符合二叉查找树的特性外，还具有下列性质：
1、根节点是黑色，节点是红色或黑色；
2、每个叶子节点都是黑的空节点；（nil节点）
3、每个红色节点的两个子节点都是黑色；（也就是说从每个叶子到根的所有路径上不能有两个连续的红色节点）
4、从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
这些规则的限制，保证了红黑树的平衡，红黑树从根到叶子的最长路径不会超过最短路径的两倍。当红黑树插入或者删除节点的时候，红黑树的规则可能被打破，这时候就需要做出调整来维持它的平衡了。请看下面的例子（注意：新插入的节点必须是红色，否则就没有意义了）：
由于父节点22是也是红色节点，因此打破了红黑树的规则（每个红黑树的两个子节点都是黑色），所以必须进行调整，使之重新符合规则。那么我们需要作出怎样的调整才能保证一棵红黑树始终是符合规则的标准红黑树呢？调整有两种方法：“变色”和“旋转”，其中，旋转又分为两种形式：“左旋转”和“右旋转”。
为了重新符合红黑树的规则，尝试把红色节点变成黑色，或者把黑色节点变成红色。
下图是摘自上面红黑树的一部分，节点25并非根节点。正如上面所说因为新节点21和节点22连续出现了红色，不符合规则，所以把节点22从红色变成黑色。
但这样并不算完，节点22变成黑色后，凭空多出的黑色节点又打破了规则，发生连锁反应，需要继续把节点25从黑色变为红色。
此时仍未结束，节点25变为红色后，又和节点27形成了两个连续的红色，规则又被打破，需要继续把节点27从红色变为黑色。
如此一路走下来，完成变色调整。
逆时针旋转红黑树的两个节点，使得父节点被自己的右孩子取代，而自己成为左孩子。
顺时针旋转红黑树的两个节点，使得父节点被自己的左孩子取代，而自己成为右孩子。
这几种方法究竟怎么使用呢？红黑树的插入和删除包含很多种情况，每种情况都有不同的处理方式，下面举一个典型的例子，可以体会一下这个过程。
还以刚才插入节点21为例：
首先我们变色处理，把节点25及其下方的节点变色：
此时节点17和节点25是连续的两个红色节点，那么此时再把节点17变成黑色节点可以吗？显然是不可以的，这样依然不符合规则，更不可以把根节点13变成红色。
既然变色已经无法解决问题，我们此时就要使用旋转了，我们把节点13看作X，把节点17看作Y，进行左旋转：
旋转完成后，由于根节点必须是黑色，所以还需要进行变色：
至此并没有结束，因为其中两条路径（17-8-6-NIL）的黑色节点数是4，其他路径的黑色节点数是3，依旧不符合规则。这时我们需要把节点13看成X，节点8看成Y，做右旋转：
然后再进行变色：
经过上面一系列的调整，我们的红黑树终于变得重新符合规则，整个过程有点复杂，经历了：变色–左旋转–变色–右旋转–变色这样的一系列步骤。
经过上面细致的步骤演示，想必大家对二叉查找树和红黑树有所了解了吧，对红黑树结构插入新节点所触发的一系列的变化流程也有了大概印象。实际中红黑树的应用是很多的，比如JDK（Java开发工具包）的集合类TreeMap和TreeSet底层就是红黑树实现的，在Java8中，HashMap也用到了红黑树。其实关于红黑树自平衡的调整，插入和删除节点时涉及到的情形一一展开讲解还是很多很多的，但是万变不离其中，红黑树自平衡调整的主体思想都是上面所叙述的，大家有兴趣可以再进行深入的探究。
c语言红黑树例子的介绍就聊到这里吧，感谢你花时间阅读本站内容，更多关于c实现红黑树、c语言红黑树例子的信息别忘了在本站进行查找喔。
微信扫一扫 
支付宝扫一扫 
