/* 功能：编写一个函数模板来返回形参的绝对值 作者：wins 日期：2013-12-11 */ #include using namespace std; template<typename
参考链接： C++编程默认参数(参数) 假设要利用模板元编程获取位于index的参数的类型： template struct ArgTypeAt...{ // FuntionType的返回值类型和参数类型？...要把FuntionType分离成返回值类型和参数类型，方法是利用模板特化，然后参数类型是一个包，再把参数包展开就能得到各位置参数的类型： template::type, float>); 还有其他修饰符const、volatile、noexcept、引用、成员函数同理
一：二叉搜索树概念 二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树: 若它的左子树不为空，则左子树上所有节点的值都小于根节点的值 若它的右子树不为空，则右子树上所有节点的值都大于根节点的值...它的左右子树也分别为二叉搜索树 例： int a [] = {5,3,4,1,7,8,2,6,0,9}; 二： 二叉搜索树实现 节点的定义 template //模板 class...(const K & key) :_left(nullptr), _right(nullptr), _key(key) {} }; 二叉搜索树实现...cout _key << " "; Print(root->_right); } private: Node* _root; }; 三：二叉搜索树的应用...比如：给一个单词word，判断该单词是否拼写正确，具体方式如下： 以单词集合中的每个单词作为key，构建一棵二叉搜索树 在二叉搜索树中检索该单词是否存在，存在则拼写正确，不存在则拼写错误。
常见的Map和Set的底层实现原理有哈希表和二叉搜索树两种，比如 Java 的 HashMap/HashSet 和 C++ 的 unorderd_map/unordered_set 底层就是用哈希表实现...getNode： // 从节点 node 开始搜索 key，如果存在返回对应节点，否则返回 null private TrieNode getNode(TrieNode node, String...containsKey方法和get方法了： // 搜索 key 对应的值，不存在则返回 null public V get(String key) { // 从 root 开始搜索 key...return hasKeyWithPattern(root, pattern, 0); } // 函数定义：从 node 节点开始匹配 pattern[i..]...TrieNode的辅助函数，并且在递归调用的时候接收其返回值，拼接到父节点上。
make_pair 函数 由于 pair 是类模板，所以我们通常是以 显式实例化 + 匿名对象 的方式来进行使用，但是由于显式实例化比较麻烦，所以 C++ 还提供了 make_pair 函数，其定义如下...pair 的匿名对象，匿名对象会自动调用 pair 的默认构造完成初始化；但由于 make_pair 是一个函数模板，所以模板参数的类型可以根据实参来自动推导完成隐式实例化，这样我们就不用每次都显式指明参数类型了...---- 二、set 1、set 的介绍 set 是按照一定次序存储元素的容器，其底层是一棵平衡二叉搜索树，由于二叉搜索树的每个节点的值满足左孩子 < 根 < 右孩子，并且二叉搜索树中没有重复的节点，所以...的迭代器遍历 set 中的元素，可以得到有序序列，即 set 可以用来排序； set 默认使用的仿函数为 less，所以 set 中的元素默认按照小于来比较； 由于 set 底层是平衡树搜索树，所以...特别注意：map 允许修改节点中 key 对应的 value 的值，但是不允许修改 key，因为这样可能会破坏搜索树的结构。
，如果基类都没有虚函数，就是特属子类的虚函数指针 image.png image.png image.png 2、c++泛型编程 泛型在C++中的主要实现为模板函数和模板类。...template void func(T1 a,T2 b){....} 1) 函数模板并不是真正的函数，它只是C++编译生成具体函数的一个模子。...它的机制是对二进制数据进行重新的解释，不会改变原来的格式，而static_cast则会改变原来的格式。...因此访问叶子节点上关联的数据也具有更好的缓存命中率。 B+树的查询更加稳定 所有的关键字查询都会走一条从根节点到叶子结点的路径。即s所有关键字查询的长度是一样的，查询效率稳定。...B+树便于遍历和区间查找 B+树的叶子结点都是相链的，因此对整棵树的便利只需要一次线性遍历叶子结点即可。而且由于数据顺序排列并且相连，所以便于区间查找和搜索。
倒链侧注 在后向链接中，系统从结论到事实反向工作，这种方法称为目标驱动。与前向链接相比，请求的数据很少，但搜索的规则很多。...与决策树（将在后面进一步讨论）类似，这种建模方法会随着逻辑复杂性的增加而出现节点数量的指数增长。更糟糕的是，与决策树不同，我们无法将函数结果作为状态来跟踪。...复杂逻辑建模 ●结合规则中函数（观察）的多个非二进制结果 ●处理规则中的多数表决条件 ●根据先前观察结果处理函数的有条件执行 当每个变量的状态数有限时（例如二进制是/否状态），决策树很有用，但当状态数增加时...决策树不能建模不确定性和效用函数，除非像时间信息一样，在树中添加这些作为决策节点，这会使决策表更加复杂。 ....流上的StreamSQL查询通常是“连续的”，长时间执行并返回增量结果。这些操作包括：从流中选择、流关系连接、联合和合并、窗口和聚合操作。 .
由于rb_tree属于一种排序二叉树, 所以按照正确规则进行遍历的话树中的节点将以排序顺序得到. rb_tree结构只有一个指向header节点的指针和记录节点数量的值....如上图header指针除了指向根节点外, 也指向树最大和最小的节点, 迭代器从最小节点开始, 利用双向链表的特性以中序遍历的顺序遍历就能输出排序后的结果, 从最大节点也相似....前者保证key的独一无二, 当搜索中遇到相同key时直接返回不会有其它反应, 后者则表示key可重复会继续正常插入....红黑树的模板参数中给出了一个仿函数KeyOfValue是用来让在下面的set中可以放心使用value作为key, 让我们从value中取出key....尽管list是线性搜索时间, 但是只要hash函数比较合理, 每个项的元素就不会太多从而搜索时间也不会太长.
如果把 子集问题、组合问题、分割问题都抽象为一棵树的话，「那么组合问题和分割问题都是收集树的叶子节点，而子集问题是找树的所有节点！」...以示例中nums = [1,2,3]为例把求子集抽象为树型结构，如下： 从图中红线部分，可以看出「遍历这个树的时候，把所有节点都记录下来，就是要求的子集集合」。...回溯三部曲 递归函数参数 全局变量数组path为子集收集元素，二维数组result存放子集组合。（也可以放到递归函数参数里） 递归函数参数在上面讲到了，需要startIndex。...单层搜索逻辑 「求取子集问题，不需要任何剪枝！因为子集就是要遍历整棵树」。...但是要清楚子集问题和组合问题、分割问题的的区别，「子集是收集树形结构中树的所有节点的结果」。 「而组合问题、分割问题是收集树形结构中叶子节点的结果」。
本章主要内容面向接触过C++的老铁 主要内容含： 一.二叉搜索树的基本概念 二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树: 若它的左子树不为空，则 左子树 上所有节点的值都...小于 根节点的值 若它的右子树不为空，则 右子树 上所有节点的值都 大于 根节点的值 它的 左右子树 也分别为二叉搜索树 ； 二.增删查改基本操作 //结点模板 template...【※核心重点】（分析＆代码演示） 分析 首先查找元素是否在二叉搜索树中，如果不存在，则返回 否则要删除的结点可能分下面四种情况： 要删除的结点无孩子结点 要删除的结点只有左孩子结点 要删除的结点只有右孩子结点...（分析＆代码演示） 分析 中序遍历要从通过模板实例化的树中调用中序遍历函数 需要传根结点指针，但是 根结点指针是在private域中，域外不能直接传一个根结点指针 ，所以要引入_InOrder函数，在二叉搜索树模板中...，在二叉搜索树模板中再次封装一层 } //中序遍历——————————————————————————————————————————为了解决中序要传入根节点的问题，引入_InOrder函数 void
，那么如下四道leetcode上的题目，只需要修改模板的一两行代码（不能再多了）」 107.二叉树的层次遍历 II 给定一个二叉树，返回其节点值自底向上的层次遍历。...（即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历） ? 思路 相对于102.二叉树的层序遍历，就是最后把result数组反转一下就可以了。...给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。...给定一个 N 叉树，返回其节点值的层序遍历。...返回其层序遍历: [ [1], [3,2,4], [5,6] ] 思路 这道题依旧是模板题，只不过一个节点有多个孩子了 C++代码 class Solution { public: vector
---- 前言 时隔多日，又回到了二叉树的学习中，在 C++ 进阶中，我们首先要学习 二叉搜索树，重新捡起二叉树的相关知识，然后会学习 AVL 树 及 红黑树，最后会用红黑树封装实现库中的 set 和...map，作为 C++ 进阶中的难度最高峰，整个学习过程非常艰辛，但 关关难过关关过，让我们先从比较简单的 二叉搜索树 开始学习 ---- ️正文 1、什么是二叉搜索树？...后的结果为：1 3 4 6 7 8 10 13 14 因此，二叉搜索树也叫 二叉排序树，具有一定的排序价值 下面就来看看 如何从 0 开始实现一棵二叉搜索树 ---- 2、二叉搜索树的实现 注：先建出一棵二叉搜索树...，再补全剩余功能 2.1、基本框架 跟二叉树一样，二叉搜索树 也需要有单独的 节点类 表示单个节点，得益于 C++ 面向对象的特性 我们可以利用类和对象、泛型编程等特点，将二叉搜索树实现的更加全能 #pragma...搜索二叉树，但后者的英文简写比较不友好：SBTree，因此推荐叫做 二叉搜索树：BSTree 注意： 二叉搜索树的节点类需要写出构造函数，因为后面创建新节点时会用到；二叉搜索树的根可以给个缺省值
搜索容器中 Key 值为输入参数 k 的元素，并返回找到元素的数量。..."; // 输入 mom, dad, bro 中的一个，否则搜索失败返回 Not Found getline(std::cin, input); // 根据输入参数 Key 值进行搜索...内部实现机理 map： map 内部实现了一个红黑树，该结构具有自动排序的功能，因此map内部的所有元素都是有序的，红黑树的每一个节点都代表着map的一个元素，因此，对于map进行的查找，删除，添加等一系列的操作都相当于是对红黑树进行这样的操作...，故红黑树的效率决定了map的效率，map只需要提供比较函数（一般为小于函数）即可完成比较； hash_map： hash_map 需要提供 hash 函数，以及等于函数； unordered_map...，因此效率非常的高； 缺点： 空间占用率高，因为 map 内部实现了红黑树，虽然提高了运行效率，但是因为每一个节点都需要额外保存父节点，子节点以及红/黑性质，使得每一个节点都占用大量的空间； 适用于具有顺序要求的问题
说明: 叶子节点是指没有子节点的节点。 示例： 给定二叉树 [3,9,20,null,null,15,7]， ? 返回它的最大深度 3 。...思路 递归法 本题其实也要后序遍历（左右中），依然是因为要通过递归函数的返回值做计算树的高度。 按照递归三部曲，来看看如何来写。...确定递归函数的参数和返回值：参数就是传入树的根节点，返回就返回这棵树的深度，所以返回值为int类型。...层序遍历 所以这道题的迭代法就是一道模板题，可以使用二叉树层序遍历的模板来解决的。 如果对层序遍历还不清楚的话，可以看这篇：二叉树：层序遍历登场！...最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。 例如，给定一个 3叉树 : ? 我们应返回其最大深度，3。
有同学会把红黑树和二叉平衡搜索树弄分开了，其实红黑树就是一种二叉平衡搜索树，这两个树不是独立的，所以C++中map、multimap、set、multiset的底层实现机制是二叉平衡搜索树，再具体一点是红黑树...这是构造函数，这么说吧C语言中的结构体是C++中类的祖先，所以C++结构体也可以有构造函数。 构造函数也可以不写，但是new一个新的节点的时候就比较麻烦。...从时间复杂度上其实迭代法和递归法差不多（在不考虑函数调用开销和函数调用产生的堆栈开销），但是空间复杂度上，递归开销会大一些，因为递归需要系统堆栈存参数返回值等等。...「层序遍历遍历相对容易一些，只要掌握基本写法（也就是框架模板），剩下的就是在二叉树每一行遍历的时候做做逻辑修改。」 周六 在二叉树：你真的会翻转二叉树么？...总结 「本周我们都是讲解了二叉树，从理论基础到遍历方式，从递归到迭代，从深度遍历到广度遍历，最后再用了一个翻转二叉树的题目把我们之前讲过的遍历方式都串了起来。」 下周依然是二叉树，大家加油！
回溯法三部曲 递归函数的返回值以及参数 在这里要定义两个全局变量，一个用来存放符合条件单一结果，一个用来存放符合条件结果的集合。...如此我们才遍历完图中的这棵树。 for循环每次从startIndex开始遍历，然后用path保存取到的节点i。...(n, k, i + 1); // 递归：控制树的纵向遍历，注意下一层搜索要从i+1开始 path.pop_back(); // 回溯，撤销处理的节点 } 可以看出backtracking（递归函数...）通过不断调用自己一直往深处遍历，总会遇到叶子节点，遇到了叶子节点就要返回。...然后进一步把回溯法的搜索过程抽象为树形结构，可以直观的看出搜索的过程。 接着用回溯法三部曲，逐步分析了函数参数、终止条件和单层搜索的过程。
数据结构图文解析系列 数据结构系列文章 数据结构图文解析之：数组、单链表、双链表介绍及C++模板实现 数据结构图文解析之：栈的简介及C++模板实现 数据结构图文解析之：队列详解与C++模板实现 数据结构图文解析之...：树的简介及二叉排序树C++模板实现....数据结构图文解析之：AVL树详解及C++模板实现 数据结构图文解析之：二叉堆详解及C++模板实现 数据结构图文解析之：哈夫曼树与哈夫曼编码详解及C++模板实现 AVL树简介 AVL树的名字来源于它的发明作者...条件二：每个节点的左子树和右子树的高度差至多为1。 ? 图一中左边二叉树的节点45的左孩子46比45大，不满足二叉搜索树的条件，因此它也不是一棵平衡二叉树。...右边二叉树满足二叉搜索树的条件，同时它满足条件二，因此它是一棵平衡二叉树。 ?
操作结果只是简单的从一个指针到别的指针的值的二进制拷贝。在类型之间指向的内容不做任何类型的检查和转换。...即按照后进先出的原则 集合set 由节点组成的红黑树，每个节点都包含着一个元素，节点之间以某种作用于元素对的谓词排列，没有两个不同的元素能够拥有相同的次序，具有快速查找的功能。...STL的算法也是非常优秀的，它们大部分都是类属的，基本上都用到了C＋＋的模板来实现，这样，很多相似的函数就不用自己写了，只要用函数模板就可以了。...还有另一个erase()函数可以删掉一个范围的元素。 list的成员函数remove()用来从list中删除元素。...C++ STL中标准关联容器set, multiset, map, multimap内部采用的就是一种非常高效的平衡检索二叉树：红黑树，也成为RB树(Red-Black Tree)。
虚继承 虚函数 模板类、成员模板、虚函数 模板类中可以使用虚函数 一个类（无论是普通类还是类模板）的成员模板（本身是模板的成员函数）不能是虚函数 抽象类、接口类、聚合类 抽象类：含有纯虚函数的类 接口类...S2, …, Sn} 平衡二叉树（AVL树） 性质 | 左子树树高 - 右子树树高 | <= 1 平衡二叉树必定是二叉搜索树，反之则不一定 最小二叉平衡树的节点的公式：F(n)=F(n-1)+F(n-2...节点是红色或黑色。 根是黑色。 所有叶子都是黑色（叶子是 NIL 节点）。 每个红色节点必须有两个黑色的子节点。（从每个叶子到根的所有路径上不能有两个连续的红色节点。）...（新增节点的父节点必须相同） 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。...二叉搜索树查找） O(log2n) 红黑树 O(log2n) 2-3树 O(log2n - log3n) B树/B+树 O(log2n) 图搜索算法 图搜索算法 数据结构 遍历时间复杂度
二.set的介绍 set的底层是一棵搜索二叉树，搜索二叉树在构建的时候会自动排序，并且不能插入大小相同的值,如果你往树中插入大小相同的值，它会自动给你去重，所以set其实是去重+排序 set有一个模板参数...T和一个仿函数以及空间配置器（STL中的容器为了减少扩容时的效率损失都是从内存池中开空间的），表面上set只有一个参数T，但其实set内部存放的是这样的键值对 set的大部分成员函数和...第二个插入函数实在某个位置插入一个节点，但是这个接口要慎用，因为有可能会破坏到树的结构。...，如果没找到就返回set::end； count 给定一个值，该函数能帮你统计该树种拥有该值的节点有多少个。...其实operator[]调用的还是insert，所以要把这个理解了，首先要理解insert 在之前的搜索树和set中因为不允许键值冗余所以插入的返回值就是一个bool值，这里却给了一个迭代器
领取专属 10元无门槛券
手把手带您无忧上云
云服务器
即时通信 IM
ICP备案
对象存储
实时音视频
