红黑树的概念和性质红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的。性质：每个结点不是红色就是黑色根节点是黑色的如果一个节点是红色的，则它的两个孩子结点是黑色的。（这说明不可以有连续的红色结点）对于每个结点，从该结点到其所有后代结点的简单路径上，均包含相同数目的黑色结点。每个叶子结点都是黑色的（此处的叶子结点指的是空结点，用NIL表示，不影响黑色结点个数）红黑树结点定义enumColour{ RED, BLACK,};templat

目录1.概述2.线性结构3.时间复杂度4.查找算法5.树6.图1.概述博主之前写过一个完整的关于数据结构的系列文章，一共十三篇，内容包含，数组、链表、堆栈、队列、时间复杂度、顺序查找、二分查找、二叉树、二叉搜索树、平衡二叉树、红黑树、B树、B+树、大顶堆、小顶堆、图、DFS、BFS、最短路径算法。由于各篇文章分的比较散，本文中将对做一次清单式的总结，这是一份属于你的数据结构大全，请签收。2.线性结构文章链接：数据结构（1）线性结构——数组、链表、堆栈、队列（介绍和JAVA代码实现）_线性结构中队列、数组、栈结构__BugMan的博客-CSDN博客在线性数据结构中，数据元素之间存在一对一的关系，

大纲在了解B树、B+树、AVL树、红黑树之前，我们先看一下各种树型结构的大致实际应用场景：B和B+树：主要用在文件系统以及数据库中做索引等AVL树：平衡二叉树之一，应用相对其他数据结构比较少，windows对进程地址空间的管理用到了AVL红黑树：平衡二叉树，广泛应用在C++STL中，比如map和set，Java的TreeMap树结构已经有了很多种形式，为何出现B树、B+树、AVL树、红黑树？下面我们按照这个大纲来看一下这些问题？二叉搜索树概念二叉搜索树(平衡二叉树)是采用二分法思维把数据按规则组装成一个树形结构的数据，用这个树形结构的数据减少无关数据的检索，大大的提升了数据检索的速度。我们在二

漫谈红黑树：红黑树的奇妙演化一、红黑树的提出二、红黑树性质的简单推导三、结论博主简介💡一个热爱分享高性能服务器后台开发知识的博主，目标是通过理论与代码实践的结合，让世界上看似难以掌握的技术变得易于理解与掌握。技能涵盖了多个领域，包括C/C++、Linux、Nginx、MySQL、Redis、fastdfs、kafka、Docker、TCP/IP、协程、DPDK等。👉🎖️CSDN实力新星、CSDN博客专家、华为云云享专家、阿里云专家博主👉一、红黑树的提出追溯起来的话，红黑树的启蒙最早应该是由计算机科学家RudolfBayer和VolkerWeber在1972年的一篇论文《Maintaininga

文章目录前言1.对之前实现的红黑树进行一些补充和完善1.1析构1.2查找2.STL源码中map和set的实现3.改造红黑树+封装map和set3.1红黑树结构修改3.2map、set的结构定义3.3insert的封装3.4insert测试3.5发现问题并解决3.6红黑树迭代器实现3.7封装set和map的迭代器并测试3.8map的[]重载3.9元素可以修改的问题解决4.代码展示4.1RBTree.h4.2Map.h4.3Set.h4.4Test.cpp前言前面的文章我们学习了红黑树，也提到了C++STL中的map和set的底层其实就是用的红黑树来实现的（而map和set的使用我们前面也学过了）

文章目录前言1.红黑树的概念及性质1.1红黑树的概念1.2红黑树的性质1.3已经学了AVL树，为啥还要学红黑树2.红黑树结构的定义3.插入（仅仅是插入过程）4.插入结点之后根据情况进行相应调整4.1cur为红，p为红，g为黑，u存在且为红（无需旋转，变色即可）情况分析及处理代码实现4.2cur为红，p为红，g为黑，u不存在/u存在且为黑（单旋+变色）情况分析及处理代码实现4.3cur为红，p为红，g为黑，u不存在/u存在且为黑（双旋+变色）情况分析及处理4.4（单/双）旋转+变色代码统一实现5.红黑树的测试5.1验证其为搜索二叉树5.2验证其是否平衡且满足红黑树性质5.3大量随机数构建红黑树进

文章目录一.红黑树的定义二.红黑树的插入1.红黑树节点的定义2.红黑树的插入操作3.总结：三.红黑树与AVL树的比较四.检验手写的红黑树五.源码一.红黑树的定义红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的。红黑树的性质：每个结点不是红色就是黑色根节点是黑色的如果一个节点是红色的，则它的两个孩子结点是黑色的对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点每个叶子结点都是黑色的(此处的叶子结点指的是空结

 文章目录一、引言二、红黑树的概念与性质2、1红黑树的概念2、2红黑树的性质三、红黑树的定义与实现3、1红黑树的定义3、2插入新节点3、2、1默认插入红色节点3、3 插入情况分类3、3、1情况一（根据颜色向上调整）3、3、2情况二（单次旋转+变色）3、3、3情况三（两次旋转+变色）3、4插入的完整代码实现四、红黑树的检验五、性能分析六、总结🙋‍♂️ 作者：@Ggggggtm 🙋‍♂️👀 专栏：C++、数据结构 👀💥 标题：红黑树💥 ❣️ 寄语：与其忙着诉苦，不如低头赶路，奋路前行，终将遇到一番好风景 ❣️ 一、引言 红黑树是一种自平衡的二叉搜索树，它在计算机科学中扮演着重要的角色。由于其高效的

目录什么时候才会转换为红黑树？为什么要转换为红黑树？为什么不一开始就用红黑树，反而要经历一个转换的过程呢？从链表转化为红黑树的阈值为什么是8？什么时候才会转换为红黑树？当Map链表长度大于或等于阈值TREEIFY_THRESHOLD（默认为8）的时候，如果同时还满足容量(数组的长度)大于或等于MIN_TREEIFY_CAPACITY（默认为64）的要求，就会把链表转换为红黑树。同样，后续如果由于删除或者其他原因调整了大小，当红黑树的节点小于或等于6个以后，又会恢复为链表形态。为什么要转换为红黑树？每次遍历一个链表，平均查找的时间复杂度是O(n)，n是链表的长度。红黑树有和链表不一样的查找性能，

🐱作者：一只大喵咪1201🐱专栏：《数据结构与算法》🔥格言：你只管努力，剩下的交给时间！在学习AVL树的时候，我们知道，当修改AVL树的结构(插入，删除)时，会通过旋转来保证平衡因子不超过1，所以频繁的修改结构会导致效率低下，今天我们学习的红黑树就完美解决了这个问题。红黑树🍧红黑树🍨节点的定义🍧红黑树的插入🍧红黑树的调整🍨cur为红，p为红，g为黑，u存在且为红🍨cur红且为左子树，p为红，g为黑，u不存在/u存在且为黑🍨cur红且为右子树，p为红，g为黑，u不存在/u存在且为黑🍧红黑树的验证🍧红黑树与AVL树的比较🍧总结🍧红黑树红黑树：是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的