树形结构主要有四种：map,set,multimap,multiset。这四种容器的共同点是使用平衡搜索树即红黑树作为底层结构，容器中的元素是一个有序的序列。...map支持下标访问符，即在[]中放入key，就可以找到与key对应的value并且可以修改value。map通常被实现为二叉搜索树(更准确的说：平衡二叉搜索树(红黑树))。...用红黑树封装set和map先实现RBTree的迭代器迭代器类框架template//依次是T，T&，T*class __RBTreeIterator...和set同时调用红黑树的普通迭代器时，红黑树应该如何区分上层的value是允许被修改是不许被修改呢？？？...红黑树，红黑树封装map和set的介绍就到这里拉，如果这篇文章对你有帮助的话，请给博主点赞＋收藏，感谢看官的大力支持~
在源码里面，对于map和set的实现，底层是用同一棵红黑树封装出来的，并不是用了两棵红黑树 那么大家肯定会有疑问了，一棵红黑树这么能两用呢，况且map和set的底层存储的节点类型不一样啊，map是存储的键值对...，set只是存储key 这时设计map和set的大佬就想到了一个极佳的办法，在红黑树底层中用了一个模板参数Value来代表红黑树结点存储对象的类型，这个类型可能是pair键值对，也有可能是key类型。...我们就可以根据value的类型来去确定是map还是set了，但是大家可能会有一点小疑问，既然有了value就可以实现红黑树了，那我们还要关键码key有什么用呢？ 这里的关键码key是必不可少的！...因为在红黑树搜索的时候，依靠的还是关键码进行搜索，通过所传关键码和红黑树结点中的关键码的大小关系，确定到红黑树中要搜索的某个结点。 红黑树的find函数的参数类型必须是key！...在实现map和set之前，我们先想一想，上一篇博文的红黑树有哪些地方需要进行改进的？
我们之前在学习 set 和 map 基本使用时就介绍了 set 和 map 底层都是红黑树，但这里有一个问题 – set 是K模型的容器，而 map 是KV模型的容器，那它们底层为什么能同样都使用红黑树呢...的插入删除查找等各种功能都是封装复用的红黑树的接口，对于 map来说，key_type 就是我们平常所理解的 K，但是 value_type 却是 pair 类型，它的两个参数分别是模板参数 _Key...，而 set 中用于接受返回值的 iterator 其本质封装的是红黑树的 const 迭代器，所以这里报错的原因是 将红黑树的普通迭代器赋值给红黑树的 const 迭代器； 这个问题的解决办法有很多，...，但是 value 是运行修改的，所以 map 的普通迭代器封装红黑树的普通迭代器即可，而不用将其封装为红黑树的 const 迭代器； 同时，我们也不用担心 map 的 key 被修改的问题，因为 map...const迭代器就是set的普通迭代器 return std::pair(p.first, p.second); } 至此，我们使用红黑树来封装 set 和 map
---- 前言 红黑树的基本情况我们已经在上一篇文章中学习过了，本文主要研究的是红黑树的实际应用：封装实现 set 和 map，看看如何通过一棵红黑树满足两个不同的数据结构；在正式封装之前，先要对之前的红黑树进行完善...set 和 map 红黑树的封装实现会涉及部分代码改动 为了进行区分，红黑树的完善代码名为 RBTree - 副本.hpp 存放在 Gitee 仓库中 2.1、解决 k 与 k/v 的参数冲突...，会去调用 红黑树 中相应的函数，所以我们不需要实现 还是那句话：底层的数据结构足够强大，封装的时候就不需要操太多心 对于 set 和 map 都需要的函数，可以在 红黑树 中统一实现，两者分别调用即可...---- 4、完整源码 关于本次完善的红黑树、封装实现 set 和 map 的相关代码在下面这个 Gitee 仓库中 《 封装set和map博客 》 ---- 总结 以上就是本次关于 C++【一棵红黑树封装...set 和 map】的全部内容了，在本文中，我们首先将 红黑树 进行了完善，解决了一些深拷贝问题，新增了迭代器，同时还用反向迭代器适配器适配出了 反向迭代器，当红黑树完善后，我们用同一棵红黑树同时封装实现了
红黑树封装map和set 前言 一.改良红黑树的数据域结构 1.1 改良后的结点 1.2 改良后的类 二. 封装的set和map 2.1 set.h 2.2 map.h 三....迭代器 3.1 迭代器封装 3.2 const迭代器 四.完整代码实现 4.1 RBTree.h 4.2 set.h 4.3 map.h 4.4 Test.cpp 前言 上一节中，说到了红黑树的实现...，并且已经知道map和set的底层共用了同一套红黑树的结构。...但这样就会出现一个问题，map的数据域和set不一样，比较大小的方式自然也就不一样。因此上一篇中的红黑树还需要做出一些改变才能用来实现map和set。...一.改良红黑树的数据域结构 对于如何设计针对map、set的红黑树结构，看源码的实现无疑是最好的方式： 对于源码的实现，我们知道set是的键值对，但是在使用时却只显示一个k，map是
所以，就先介绍Map集合、散列表和红黑树吧！ 看这篇文章之前最好是有点数据结构的基础： Java实现单向链表 栈和队列就是这么简单 二叉树就这么简单 ? ?...红黑树是对2-3查找树的改进，它能用一种统一的方式完成所有变换。 红黑树是一种平衡二叉树,因此它没有3-节点。那红黑树是怎么将3-节点来改进成全都是二叉树呢？...很好理解：红黑树也是平衡树的一种，在插入元素的时候它也得保持树的平衡，那红黑树是以什么的方式来保持树的平衡的呢？...，遵守这些约束的才能叫做红黑树： 红黑树是二叉搜索树。...集合的基础知识，了解Map的常用子类~ 简单介绍了散列表和红黑树，他俩作为Hashxxx和Treexxx的底层，了解其整体思想和相关基础在后续看源码也不至于那么懵~
这一篇文章就来看看如何构建红黑树 对于平衡二叉树的构建，可以参考小程序中的文章(C++版)。...平衡二叉树 红黑树 红黑树属于平衡二叉树，但是并非严格意义上的平衡二叉树，因为平衡二叉树要求节点的左右子树高度差不超过1， 而红黑树放弃了这种高度平衡，利用对结点上色的操作来保证树相对平衡，这其中原因大概是维护一个绝对平衡的二叉树代价太大...但如果插入频率小或者只有一次构建，那么平衡二叉树的查询性能还是比红黑树高。...此时红黑树构建平衡分为4种情况: 情况一:红黑树为空树，此时插入结点充当根结点，上色为黑 情况二:插入结点已经存在，此时替换插入结点值即可 情况三:插入结点的位置，其父结点是黑色，此时平衡未打破，插入完成...到这里就构建完成了 相对于构建新增，红黑树的删除情况更为复杂，由于时间关系(这周只有一天休息加上绘图太费劲)，留到下一次分享。 构建代码 红黑树构建源码
红黑树概念 红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或 Black。...通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的。...红黑树的性质 每个结点不是红色就是黑色 根节点是黑色的 如果一个节点是红色的，则它的两个孩子结点是黑色的，树中没有连续的红节点 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点...每个叶子结点都是黑色的(此处的叶子结点指的是空结点) 为什么满足上面的性质，红黑树就能保证：其最长路径中节点个数不会超过最短路径中节点个数的两倍？...插入 红黑树的叔叔是关键 u存在且为红，变色继续向上处理 u不存在或存在且为黑，旋转（单旋+双旋）+变色 情况一：cur为红，parent为红，grandfather为黑（固定），uncle存在且为红
前言 红黑树的应用还是比较广泛的。比如Java8的HashMap的底层就用到了红黑树，还有TreeMap和TreeSet也用到了。 下面主要以下几个方面学习一下红黑树。...1）二叉查找树BST 2）红黑树RBTree的规则、增删查 3）红黑树的Java实现。...其中两款具有代表性的平衡树分别为AVL树和红黑树。AVL树由于实现比较复杂，而且插入和删除性能差，在实际环境下的应用不如红黑树。...下图中这棵树，就是一颗典型的红黑树： ? 什么情况下会破坏红黑树的规则，什么情况下不会破坏规则呢？我们举两个简单的栗子： 添加节点 1.向原红黑树插入值为14的新节点： ?...由于父节点15是黑色节点，因此这种情况并不会破坏红黑树的规则，无需做任何调整。 2.向原红黑树插入值为21的新节点： ?
，因此就出现了很多自平衡的二叉查找树，这些自平衡二叉查找树的查询效率都会稳定在O(logN)，红黑树就是一种自平衡的二叉查找树。...下面我们会红黑树的特征、插入以及删除来分析红黑树是如何进行自平衡的。...特征 想要了解红黑树如何自平衡，就必须了解红黑树的特征，因为自平衡操作都是围绕这些特征来的，一旦一个红黑树因为插入和删除节点打破了自身的特征，那么他就需要进行自平衡(变色、旋转)来使得二叉树重新满足红黑树的特征...通过上述特征，决定了红黑树的一个重要特性：从根到叶子的最长的可能路径不多于最短路径的两倍长。 下图是一张红黑树示意图： ?...，需要我们细细揣摩，并且反复的研究，在了解红黑树的基本概念以后，我们后续会分析一下HashMap中红黑树的实现以及着手自己实现一个红黑树。
在源码里面，对于map和set的实现，底层是用同一棵红黑树封装出来的，并不是用了两棵红黑树，一个红黑树结点存key，一个红黑树结点存的键值对，这样的方式太不符合大佬的水准了，实际上在红黑树底层中用了一个模板参数...如果Value是键值对，那红黑树此时封装的就是map，如果Value是key，那红黑树此时封装的就是set。...在拥有仿函数类型后，我们实例化一个仿函数对象，这个对象的功能就是帮助我们取得结点中的key关键码，方便我们在红黑树Insert的实现里面进行结点中关键码的比较 二、封装第二层：红黑树的普通迭代器 1...其实map和set的表层迭代器实现都很简单，他们都是直接调用了底层红黑树的普通迭代器，所以难点其实是在红黑树的迭代器实现上。 2....map底层的红黑树存的是的键值对，set底层的红黑树存的是key关键码，我当时觉得为什么一定要设计成这样呢？我们让map的红黑树结点只存储value不可以吗？
这样就能让整棵树的高度相对来说低一些，相应的插入、删除、查找等操作的效率高一些。 # 什么是红黑树 红黑树的英文是 “Red-Black Tree”，简称 R-B Tree。...红黑树中包含最多黑色节点的路径不会超过 log2n，所以加入红色节点之后，最长路径不会超过 2log2n，也就是说，红黑树的高度近似 2log2n。...所以，红黑树的高度只比高度平衡的 AVL 树的高度（log2n）仅仅大了一倍，在性能上，下降得并不多。这样推导出来的结果不够精确，实际上红黑树的性能更好。...# 红黑树平衡调整 # 插入操作的平衡调整 红黑树规定，插入的节点必须是红色的。而且，二叉查找树中新插入的节点都是放在叶子节点上。...# 参考资料 数据结构与算法之美 数据结构 树 二叉树 红黑树
红黑树的介绍 红黑树(Red-Black Tree，简称R-B Tree)，它一种特殊的二叉查找树。...红黑树是特殊的二叉查找树，意味着它满足二叉查找树的特征：任意一个节点所包含的键值，大于等于左孩子的键值，小于等于右孩子的键值。 除了具备该特性之外，红黑树还包括许多额外的信息。...红黑树的每个节点上都有存储位表示节点的颜色，颜色是红(Red)或黑(Black)。 红黑树的特性: (1) 每个节点或者是黑色，或者是红色。 (2) 根节点是黑色。 (3) 每个叶子节点是黑色。...因而，红黑树是相对是接近平衡的二叉树。...红黑树示意图如下： AVL树的介绍 https://www.cnblogs.com/skywang12345/p/3577479.html AVL树是高度平衡的而二叉树。
什么是红黑树 红黑树依然是一棵二分搜索树，《算法导论》中的红黑树定义如下： 每个节点或者是红色的，或者是黑色的 根节点是黑色的 每一个叶子节点（最后的空节点）是黑色的 如果一个节点是红色的，那么他的孩子节点都是黑色的...从任意一个节点到叶子节点，经过的黑色节点是一样的 在学习红黑树之前，我们有必要先学习一下什么是2-3树，学习2-3树不仅对于理解红黑树有帮助，对于理解B类树，也是有巨大帮助的。...如下图所示： 红黑树与2-3树的等价性 我们在这里定义所有的红色节点都是向左倾斜的，红色节点代表与父亲节点相融合，由于我们可以通过2-3树画出一个棵红黑树： 由此可知，红黑树是保持“...红黑树和AVL树：由于红黑树的最大高度是2logn,所以在查找时，相比于AVL树会慢一些，而红黑树的添加和删除元素比AVL树更快一些，如果只是用于查询，AVL树的性能要更高一些。 ...向红黑树中添加一个新元素，类比于2-3树中添加一个新元素，就是或者添加进2-节点，形成3-节点；或者添加进3-节点，暂时形成一个4-节点，这样我们可以让我们的红黑树，永远添加红节点。
在JDK8之前其实就已经有红黑树的应用，比如TreeMap的底层就是用了红黑树的数据结构。本文主要是为了讲解JDK8中HashMap底层数据结构的铺垫。...一、二叉查找树BST 红黑树的本质就是一颗二叉查找树，二叉查找树的特点如下： （1）左节点的值都小于或等于其父类（父类或根节点）的值。...二、红黑树RBTree 红黑树其实是基于二叉查找树的一颗平衡二叉查找树，具有以下特点： （1）结点是红色或黑色的，在hashMap实现中用boolean的true和false表示红色或黑色。...再经过变色后，形成最终的红黑树： ? 三、总结 个人觉得红黑树是一个挺不错的思想，红黑树在BST的基础上还引入了颜色的特点，通过变色和旋转来保持红黑树的特点，保证树的平衡。...红黑树的前身其实是234树，有兴趣的小伙伴可以了解下234树，234树和红黑树的操作完全是等价的。之所以在java中使用红黑树的数据结构是因为如果直接使用234树实现会非常繁琐。
但它是如何保证一棵n个结点的红黑树的高度始终保持在logn的呢？这就引出了红黑树的5个性质： 每个结点要么是红的要么是黑的。 根结点是黑的。...正是红黑树的这5条性质，使一棵n个结点的红黑树始终保持了logn的高度（红黑树的高度至多为2log(n+1)证明略），从而也就解释了上面所说的“红黑树的查找、插入、删除的时间复杂度最坏为O(log n)...对于树的旋转，能保持不变的只有原树的搜索性质，而原树的红黑性质则不能保持，在红黑树的数据插入和删除后可利用旋转和颜色重涂来恢复树的红黑性质。...三、红黑树的插入 将一个节点插入到红黑树中，需要执行哪些步骤呢？首先，将红黑树当作一颗二叉查找树，将节点插入；然后，将节点着色为红色；最后，通过旋转和重新着色等方法来修正该树，使之重新成为一颗红黑树。...五、Java中的红黑树 TreeMap 和 TreeSet 是 Java Collection Framework 的两个重要成员，其中 TreeMap 是 Map 接口的常用实现类，而 TreeSet
历史上AVL树流行的另一变种是红黑树(red black tree)。...对于红黑树的操作在最坏情形下花费O(log N)时间，而且我们将看到，(对于插入操作的)一种慎重的非递归实现可以相对容易地完成(与AVL树相比)。...这种情形只有X和P是红的，G是黑的，因为否则就会在插入前有两个相连的红色节点，违反了红黑树的法则。采用伸展树的术语，X、P和G可以形成一个一字形链或之字形链(两个方向中的任一个方向)。...2、自顶向下红黑树上滤的实现需要用一个栈或用一些父指针保存路径。我们看到，如果我们使用一个自顶向下的过程，实际上是对红黑树应用从顶向下保证S不会是红的过程，则伸展树会更有效。这个过程在概念上是容易的。...注意，对于红黑树带有一个儿子的节点的情形，我们不想使用这种方法进行，因为这可能在树的中部连接两个红色节点，为红黑条件的实现增加苦难。
在STL的源代码中，map和set的底层原理都是红黑树。但这颗红黑树跟我们单独写的红黑树不一样，它需要改造一下： 改造红黑树 节点的定义 因为map和set的底层都是红黑树。...而且map是拥有键值对pair的，而set是没有键值对，只有一个K。因此，为了应对这两种不同的情况，就使用模板参数T。 当map使用这棵红黑树的时候，T就会变成pair。...红黑树的模板参数有三个：K、valueType和仿函数KeyOfValue。...，因为它是一棵树，节点地址不连续，因此需要封装起来。...，并没有什么技术含量，问题都在红黑树中解决了。
插入 红黑树的插入操作包括二叉搜索树的插入操作（左小右大）和红黑树平衡插入操作，平衡操作主要是为了让红黑树重新满足红黑树属性。...插入操作 1、类似于二叉搜索树，按照左小右大原则，插入新元素 2、将新元素着成红色（根据红黑树的性质，着成红色，破坏的性质较少，可以更快调整平衡） 插入平衡操作 3、平衡新树 新树可能不满足红黑树的性质...，此时破坏了性质4，将父结点、叔结点的颜色着为黑色、祖父结点着为红色，就能使其祖父之下的子树满足红黑树，将其祖父结点作为新结点，继续判断祖父以上的红黑树是否满足红黑树； ?...下面分析一下平衡删除的场景： 3.1、平衡结点是树的根结点 根据性质2，直接着为黑色，满足红黑树性质； 3.2、平衡结点是红色（红-黑），2.2情况之后 直接将其着为黑色，满足红黑树性质； 3.3、...HashMap的红黑树删除平衡算法 ?
那么问题来了，如何在删除和插入数据的时候保证以上性质呢，红黑树的策略就是改变颜色和旋转，改变颜色很好理解，那么旋转是什么呢？...（1）把父结点变为黑色 （2）把祖父结点变为红色 （爷爷） （3）以祖父结点旋转（爷爷） 插入数据示例 假设有如下的红黑树，符合红黑树的特征 ?...现在插入数据6，颜色假设为红色，这样就不符合红黑树的特征，所以就要对其进行变换 ?...变为黑色，祖父结点15变为红色，那么再对祖父结点15进行右旋操作，同样当前结点变为祖父结点15，至此现在的红黑树已经符合特征，变换完成 可以看出变换完的红黑树结构依然稳定，所以红黑树就解决了插入和删除的问题...红黑树的应用 JDK HashMap JDK TreeMap JDK TreeSet Windows文件搜索
领取专属 10元无门槛券
手把手带您无忧上云
云服务器
即时通信 IM
ICP备案
对象存储
实时音视频
