红黑树原理之添加节点
在网上看了很多写红黑树的博客，大部分写的都不是很到位，有些关于红黑树的图都是有问题的，很多都没有说清楚什么情况促发哪种操作，看完之后还是不理解，在查看了很多资料之后，决定自己写关于红黑树的理解。分为添加节点篇和删除节点篇，本文为将阐述红黑树的基本原理以及在添加节点时，各种情况下对应的操作。（在看本文前，需要先了解平衡二叉树的原理，因为红黑树的有些操作和二叉平衡树类似）
红黑树之所以被称为红黑树，是因为红黑树的节点的颜色非红即黑，通过对节点颜色的限制和一系列的限制条件来确保红黑树没有任何一条路径是其他路径的两倍长。
红黑树需要满足以下条件：
（1）每个节点非黑即红。
（2）根节点是黑色。
（3）每个叶子节点，即空节点是黑的。
（4）红色节点的两个孩子节点都是黑的
（5）每个节点到子孙节点的所有路径上包含相同数量的黑色节点
如图1所示，就是一颗红黑树：
在插入节点时，总是插入红色节点，这样可以 尽量 避免破坏红黑树的结构，为什么说插入红节点可以 尽量 避免破坏红黑树的结构，假如现在要插入6，即插入到12节点的左孩子，如果6节点是黑色的，那么就会破坏规则（5），即图2中绿色路径上的黑色节点的数量比黄色路径上黑色节点的数量多，如果6节点是红色的，则不会破坏树结构，如图3所示。
红黑树节点的添加可分为以下3种情况
分析：因为插入的是红色节点，所以违背规则（2）根节点是黑色
解决方案：只需要把这个节点的颜色改成黑色即可。
分析：因为插入节点的颜色是红色，不会破坏任何规则。
解决方案：无。
分析：这时又可分为插入节点是父节点的左孩子还是右孩子，以及父节点是祖父节点的左孩子还是右孩子，由于对称性，我们只需要考虑其中一种即可。假设插入的节点是25，即如图4所示的位置。这时破坏了规则（4）红色节点的两个孩子节点都是黑的。
解决方案：将当前节点的父节点和叔叔节点改成黑色，祖父节点改为红色，把当前节点指向祖父节点。如图5所示。
情况4：当前节点的父节点是红色，叔叔节点是黑色，当前节点是其父节点的右孩子。
分析：这时破坏了规则（4）红色节点的两个孩子节点都是黑的。如图5所示。
解决方案：将当前节点的父节点作为新的当前节点，以新的当前节点为支点进行左旋。如图6所示。
[图片上传失败...(image-c45d5d-1594949705288)]
分析：这时破坏了规则（4）红色节点的两个孩子节点都是黑的。如图6所示。
解决方案：父节点改成黑色，祖父节点改成红色，将当前节点改为祖父节点，并以新的当前节点为支点进行右旋。如图7所示。
[图片上传失败...(image-492143-1594949705288)]
以上内容就是关于红黑树添加节点时的操作，本片博客参考了 https://bbs.csdn.net/topics/350253651 。
红黑树原理之添加节点
（3）每个叶子节点，即空节点是黑的。（4）红色节点的两个孩子节点都是黑的 （5）每个节点到子孙节点的所有路径上包含相同数量的黑色节点 如图1所示，就是一颗红黑树：在插入节点时，总是插入红色节点，这样可以 尽量 避免破坏红黑树的结构，为什么说插入红节点可以 尽量 避免破坏红黑树的结构，假如现在...
红黑树(一)之 原理和算法详细介绍
着色: 保证插入节点为红色，以符合红黑树的特性。 调整: 针对可能的不平衡，通过旋转和颜色变换，确保每个路径的黑色节点数相同。 代码实践: 诸如RB-INSERT插入节点，随后通过RB-INSERT-FIXUP进行修正，维护红黑树结构。红黑树插入操作的精妙之处在于，根据父节点颜色的不同，分为三种情况：当父节点...
红黑树性质及添加删除节点的染色和旋转过程
红黑树添加节点，我们一般在叶子节点添加红色，因为添加红色节点能更快的符合上面几条性质，比如，如果添加一个黑色节点，很容易就打破规则7，本来红黑树从任意节点到子节点的路径上都包含相同的 black 节点，但是如果这时候我们添加black 节点，那么这条规则就打破了，所以我们一般添加红色节点 所以如果叶子...
彻底理解红黑树(二)之 插入
红黑树属于二叉搜索树，插入动作也与二叉搜索树一致，只不过红黑树在插入之后，多了平衡动作（旋转与涂色）。新插入的节点均为红色节点，因为红色不会影响路径上黑色节点的数量，保持性质4。如果父节点为黑色，就直接结束了；如果父节点为红色，则需要另外处理了。以新插入的节点为当前平衡节点N，插入平衡...
怎么在rbRoot上添加一个节点?
1、首先，需要定义红黑树的节点这样的结构。2、定义结构的顺序。3、然后，就能在这里定义的根节点的结构体。4、此时，可以暂时这棵红黑树的根命名为rb_root。5、这时，利用刚刚定义的红黑树节点定义新节点。6、最后，我们便可以为其重新命名为RBRoot即可。
红黑树原理讲解
注意: 插入结点,必须为 红色 ,理由很简单,红色在父节点(如果存在)为黑色节点时,红黑树的黑色平衡没被破坏,不需要做自平衡操作。如果插入结点是黑色,那么插入位置所在的子树黑色结点总是1,必须做自平衡。最简单的一种情景,直接把插入结点作为根结点就行 注意: 根据红黑树性质2: 根结点是黑色。还...
红黑树详解
3、每个红色节点的两个子节点都是黑色；（也就是说从每个叶子到根的所有路径上不能有两个连续的红色节点）4、从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。这些规则的限制，保证了红黑树的平衡，红黑树从根到叶子的最长路径不会超过最短路径的两倍。当红黑树插入或者删除节点的时候，...
红黑树的原理
首先epoll_create创建一个epoll文件描述符，底层同时创建一个 红黑树 ，和一个 就绪链表 红黑树存储所监控的文件描述符的节点数据，就绪链表存储就绪的文件描述符的节点数据epoll_ctl将会添加新的描述符，首先判断是红黑树；在调度时，多个任务调度实体会首先区分是实时任务还是普通任务，然后通过以时间为顺序...
linux红黑树详解linux红黑树
红黑树原理和算法详细介绍 红黑树定义：(1)每个节点或者是黑色，或者是红色。(2)根节点是黑色。(3)每个叶子节点是黑色。(4)如果一个节点是红色的，则它的子节点必须是黑色的。(5)从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。证明 首先定义一个节点x的黑高为bh(x)bh(x)bh(...
红黑树的原理
红黑树的原理 红黑树是一种自平衡的二叉查找树，通过在树的节点上增加额外的颜色信息，来维持树的平衡，从而确保树的性能稳定。其主要原理包括以下几点：一、红黑树的定义与特点 红黑树是一种特殊的二叉查找树，其中每个节点都有颜色属性，可以是红色或黑色。红黑树的特性保证了从根到叶子节点的所有路径...
厉戴更舒： 因为插入之前所有根至外部节点的路径上黑色节点数目都相同,所以如果插入的节点是黑色肯定错误(黑色节点数目不相同),而相对的插入红节点可能会也可能不会违反“没有连续两个节点是红色”这一条件,所以插入的节点为红色,如果违反条件再调整
庄浪县15376156164： 红黑树的简介 - ？
厉戴更舒： 红黑树是一种很有意思的平衡检索树.它的统计性能要好于平衡二叉树(有些书籍根 红黑树 据作者姓名,Adelson-Velskii和Landis,将其称为AVL-树),因此,红黑树在很多地方都有应用.在C++ STL中,很多部分(目前包括set, multiset, map...
庄浪县15376156164： 红黑树的用途 - ？
厉戴更舒： 红黑树用在关联数组、字典的实现上.需要的空间比散列表小. 任何键值对应,需要随机存储和键有序的情况都可以用.一. 基本概念 1.红黑树(Red Black Tree) 是一种自平衡二叉查找树,是在计算机科学中用到的一种数据结构,典型的用...
庄浪县15376156164： 为什么工程中都用红黑树,而不是其他平衡二叉树 - ？
厉戴更舒： 红黑树和平衡二叉树区别如下:1、红黑树放弃了追求完全平衡,追求大致平衡,在与平衡二叉树的时间复杂度相差不大的情况下,保证每次插入最多只需要三次旋转就能达到平衡,实现起来也更为简单.2、平衡二叉树追求绝对平衡,条件比较...
庄浪县15376156164： 关于算法导论 - ？
厉戴更舒： 概念: 红黑树是一种自平衡二叉查找树,是在计算机科学中用到的一种数据结构,典型的用途是实现关联数组.它是在1972年由Rudolf Bayer发明的,他称之为＂对称二叉B树＂,它现代的名字是在 Leo J. Guibas 和 Robert Sedgewick 于1978年...
庄浪县15376156164： 红黑树的各种操作的时间复杂度是多少 - ？
厉戴更舒： 红黑树的操作时间跟二叉查找树的时间复杂度是一样的,执行查找、插入、删除等操作的时间复杂度为O(logn)....
庄浪县15376156164： 红黑树的红色叶子节点一定没有兄弟节点吗?为什么? - ？
厉戴更舒： : 红黑树内部节点包含根节点叶节点. 好乱. 红黑树只有三个性质. 1:根节点和所有外部节点是黑色. 2:根至外部节点中没有两个连续的颜色是黑色
庄浪县15376156164： 红黑树算法为什么需要左旋和右旋 - ？
厉戴更舒： 红黑树是平衡二叉树的一种,它有很好的性质,树中的结点都是有序的,而且因为它本身就是平衡的,所以查找也不会出现非常恶劣的情况,基于二叉树的操作的时间复杂度是O(log(N)).Linux内核在管理vm_area_struct时就是采用了红黑树来维...
庄浪县15376156164： 算法导论讲什么 - ？
厉戴更舒： 讲的全是好东西哦,且听我一一道来:堆排序 快速排序 线性时间中的排序 中值与顺序统计 基本的数据结构 散列表 二叉查找树 红-黑树 扩充的数据结构 动态规划 贪婪算法 分摊分析 B-树 二项式堆 斐波纳契堆 不相交集的数据结构 基本的图算法 最小生成树 单源最短路径 全对的最短路径 最大流 排序网络 矩阵运算 线性规划 多项式与快速傅里叶变换 数论算法 字符串匹配 计算几何学 NP-完备性 近似算法 注:看完这本书之后你就长生不老了.
庄浪县15376156164： 数据结构的红黑树性质的一个问题 - ？
厉戴更舒： 好乱.红黑树只有三个性质.1:根节点和所有外部节点是黑色.2:根至外部节点中没有两个连续的颜色是黑色3:所有根节点至外部节点的路径上都有相同数目的黑色节点.注1:外部节点就是叶节点指向的NULL节点,只不过这里不再指向NULL,而是一个实质性的空节点.注2:红黑树还有另一种规则(路径指针),但是和上面的是一样的意思,所以不列举了.
