C++红黑树
C++精通之路：红黑树迭代器的模拟实现和讲解
持续创作，加速成长！这是我参与「掘金日新计划 · 10 月更文挑战」的第8天，点击查看活动详情一：红黑树的迭代器需要注意的是：迭代器本质上是指针的一个封装的类，其底层就是指针；好处是可以方便遍历，是数据结构的底层实现与用户透明对于string,vector,list等容器，其本身的结构上是比较简单的，迭代器的实现也很简单；但是对于二叉树结构的红黑树来说需要考虑很多的问题1.begin()与end(
日期 2023-06-12 10:48:40
C++精通之路：红黑树的概念和实现方法的解析
持续创作，加速成长！这是我参与「掘金日新计划 · 10 月更文挑战」的第11天，点击查看活动详情红黑树一：红黑树的概念红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。 通过 对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩 倍，因而是接近平衡的。二：红黑树的性质每个结点不是红色就是黑色根节点是黑色的如果一个
日期 2023-06-12 10:48:40
【C++修炼之路】20.手撕红黑树
红黑树实现:RBTree 前言一.红黑树的概念及性质1.1 红黑树的概念1.2 红黑树的性质二.红黑树的结构2.1 红黑树节点的定义2.2 红黑树类的封装三.红黑树的插入情况1：只变色情况2：变色+单旋情况3：双旋插入的代码实现：四.红黑树的验证五.红黑树实现代码（完整）RBTree.hTest.cpp六.红黑树与AVL树的比较前言 在上一节中我们学到了AVL树的结构及其相关性质，对于平衡树来说，
日期 2023-06-12 10:48:40
【C++修炼之路】21.红黑树封装map和set
红黑树封装map和set前言一.改良红黑树的数据域结构1.1 改良后的结点1.2 改良后的类二. 封装的set和map2.1 set.h2.2 map.h三. 迭代器3.1 迭代器封装3.2 const迭代器四.完整代码实现4.1 RBTree.h4.2 set.h4.3 map.h4.4 Test.cpp前言 上一节中，说到了红黑树的实现，并且已经知道map和set的底层共用了同一套红黑树的结
日期 2023-06-12 10:48:40
C++:红黑树
红黑树的概念红黑树是一棵二叉搜索树，但是红黑树通过增加一个存储位表示结点的颜色RED或BLACK。通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出2倍，因而是接近平衡的。 红黑树的性质⭐1.每个节点不是红色就是黑色。⭐2.根节点是黑色的。⭐3.如果一个节点是红色的，则它的两个孩子结点是黑色的。也就意味着，红黑树没有连续的红色节点。⭐4.对于每个结点，从
日期 2023-06-12 10:48:40【C++】手撕红黑树
文章目录前言一、红黑树的概念二、红黑树的节点结构三、红黑树的插入四、红黑树的调整1、叔叔存在且为红2、叔叔不存在或存在且为黑3、插入完整代码4、总结五、红黑树的验证六、红黑树的删除七、红黑树与 AVL 树的比较八、红黑树的代码实现前言在网络上流传着这样一张图片：这张图片表达的侧面意思是：红黑树非常难！！！但如果认真阅读了这篇的博客，并且你有 AVL 树的基础的话 (重点是 AVL 树的旋转)，其实
日期 2023-06-12 10:48:40【C++】红黑树封装实现 map 和 set
文章目录一、源码剖析二、红黑树的迭代器三、模拟实现 set四、模拟实现 map五、完整代码 (最终实现)1、RBTree.h2、set.h3、map.h4、test.cpp一、源码剖析我们之前在学习 set 和 map 基本使用时就介绍了 set 和 map 底层都是红黑树，但这里有一个问题 – set 是K模型的容器，而 map 是KV模型的容器，那它们底层为什么能同样都使用红黑树呢？我们可以通
日期 2023-06-12 10:48:40【C++】AVL树和红黑树的插入
一、AVL树1.AVL树的介绍1. 虽然二叉搜索树的搜索效率很高，当搜索树接近满二叉树时，搜索效率可以达到logN，但是如果数据是有序的，则二叉搜索树会退化为单支树，搜索效率和普通的序列式容器相同了就，所以在搜索树的基础上，两位俄罗斯数学家研究出了平衡搜索树。2. 平衡搜索树要求任一结点的左右子树的高度差不超过|1|，这个高度差简称为平衡因子，balance factor，计算方式为右子树高度
日期 2023-06-12 10:48:40【C++】用一棵红黑树同时封装出map和set
一、封装第一层：仿函数取结点中的key关键码1. 在源码里面，对于map和set的实现，底层是用同一棵红黑树封装出来的，并不是用了两棵红黑树，一个红黑树结点存key，一个红黑树结点存<key,value>的键值对，这样的方式太不符合大佬的水准了，实际上在红黑树底层中用了一个模板参数Value来代表红黑树结点存储对象的类型，这个类型可能是pair键值对，也有可能是key类型。 所以在
日期 2023-06-12 10:48:40【C/C++学院】0828-STL入门与简介/STL容器概念/容器迭代器仿函数算法STL概念例子/栈队列双端队列优先队列/数据结构堆的概念/红黑树容器
for_each (myvector.begin(), myvector.end(),print); for_each(myarray.begin(), myarray.end(), print); cin.get(); //算法可以适用于任何容器，for_each是一个算法 } STL容器概念 数组线性容器 #include iostream #include ve
日期 2023-06-12 10:48:40【C++】红黑树
文章目录 红黑树的概念红黑树的性质特征红黑树结点的定义红黑树的插入操作情况1情况2情况3特殊情况代码实现 红黑树的验证红黑树的删除红黑树和AVL树的比较红黑树的应用 红黑树的概念 红黑树&
日期 2023-06-12 10:48:40