概念 B树,是普遍运用于文件系统和数据库的一种多叉(即,每个非叶子结点可以有多个孩子)平衡查找树。 数据库索引为什么采用B树/B+树结构? 数据库索引存储在磁盘上,当数据库的数据量比较大时,索引可能高达几G,甚至更多。所以在利用索引查找时,不会一次性把整个索引加载到内存,而是每次只加载一个磁盘页(这里的磁盘页对应索引树的结点)。 若索引树采用二叉树结构,则一个页面只能存放一个值。因此在最坏的情况下,查找一个值的磁盘IO次数 = 索引树的高度。 由1可看出,磁盘IO次数由索引树的高度决定。因此,为了减少磁盘IO次数,…

2021年5月3日 0条评论 102点热度 阅读全文

使用Trie树实现网站对用户输入的敏感词打码 什么是Trie树? Trie树,又称单词查找树,Trie树,是一种树形结构,是一种哈希树的变种。典型应用是用于统计,排序和保存大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。它的优点是:利用字符串的公共前缀来减少查询时间,最大限度地减少无谓的字符串比较,查询效率比哈希树高。 Trie树的核心思想是空间换时间,利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。 使用Trie树数据结构可以匹配多个关键词,速度快。Trie树的最坏空间复杂…

2021年5月3日 0条评论 97点热度 阅读全文

Trie树,前缀树,字典树,又称单词查找树或键树,是一种树形结构。 典型应用是用于统计和排序大量的字符串(但不仅限于字符串),可以用于搜索引擎系统,用于文本词频统计。 Trie利用字符串的公共前缀来避免无谓的查找,从而降低查询时间的开销以达到提高效率的目的。 Trie性质: 1.根节点不包含字符,除根节点外每一个节点都只包含一个字符。 2.每一个节点与它所在树中的位置一起决定了它所代表的字符串(虽然它自身只保存一个char)。 也可以这样理解,每条边对应着一个字符char(事实上是该边指向的节点保存的这个char)…

2021年5月3日 0条评论 78点热度 阅读全文

博客思路 1.通过二叉排序树引出平衡二叉树 2.如何判断是不是一棵平衡二叉树 3.平衡因子 4.左旋  右旋   双旋 5.通过画图创建一棵二叉排序树 6.二叉排序树的代码思路和整体框架   1.二叉排序树 二叉排序树,又叫二叉查找树,它或者是一棵空树;或者是具有以下性质的二叉树: 1. 若它的左子树不空,则左子树上所有节点的值均小于它的根节点的值; 2. 若它的右子树不空,则右子树上所有节点的值均大于它的根节点的值; 3. 它的所有结点的左右子树也分别为二叉排序树。 讲平衡二叉树之前…

2021年5月3日 0条评论 89点热度 阅读全文

https://www.cnblogs.com/onepixel/articles/7674659.html http://www.cnblogs.com/eniac12/p/5329396.html Bubble Sort #include <stdio.h> // 分类 -------------- 内部比较排序 // 数据结构 ---------- 数组 // 最差时间复杂度 ---- O(n^2) // 最优时间复杂度 ---- 如果能在内部循环第一次运行时,使用一个旗标来表示有无需要交换的可能…

2021年5月3日 0条评论 133点热度 阅读全文

一、ICA原理 独立成分分析(Independent Component Analysis, ICA),来源于著名的“鸡尾酒会”事件。关于它的背景不再过多赘述,只是在一场所,有N个人同时说话,并且有N个话筒同时录音,如何从这N段录音中分离出原始N个人单独的语音呢? 对于我们所得到的观测信号,每一路都是由这几种独立源成分组成的,只是不同通道采出的观测信号中各项信源的权重系数不同。假设只有两个独立源,分别代表母体心电和胎儿心电,由于电极片位置的不同,靠近母体心脏的电极采出的混合信号与靠近腹部的电极采出的混合信号中的独立…

2021年4月14日 0条评论 84点热度 阅读全文

思路:维护一个数组,代表以某个结点为根的树的结点数目,初始化为全1。在合并两个集合时,将秩较小的集合的元素数目加到秩较大的集合上。这里需要注意一下,就是Union过程处理两个祖先相同的结点,此时实际上没有真正的合并这两个结点,所以不需要更新集合的元素数目。至于统计集合个数就比较简单了,直接扫描一遍所有的结点,如果某个结点的祖先结点不是它自己,说明该结点是某个集合的祖先元素,统计这种结点个数即可。 代码: // 1389.cpp : 定义控制台应用程序的入口点。 // 并查集,求每个集合中的元素个数 // 在合并时将…

2021年4月5日 0条评论 22点热度 阅读全文

广义表的深度:近似于形成树的高度,表面上就是查左括号的个数 长度:元素的个数,元素指的是相对于表面的表而言(元素也可以是表) head&tail运算:根据表头、表尾的定义可知:任何一个非空广义表的表头是表中第一个元素,它可以是原子,也可以是子表,而其表尾必定是子表。 也就是说,广义表的head操作,取出的元素是什么,那么结果就是什么。但是tail操作取出的元素外必须加一个表——“ ()“ 举一个简单的列子:已知广义表LS=((a,b,c),(d,e,f)),如果需要取出这个e这个元素,那么使用tail和he…

2021年3月12日 0条评论 20点热度 阅读全文

  分支限界法通常是是广度优先或者以最小消耗(最大效益)优先的方式搜索问题的解控键树。 FIFO分支限界法   按照先进先出的原则选择下一个活结点作为扩展结点,即从节点中取出的顺序与加入结点的顺序相同。 分支限界法算法策略 (1活节点一旦成为扩展结点,就一次性产生其所有儿子结点 (2)在这些儿子结点中,导致不可行或者非最优解的儿子结点将会被舍弃,其余儿子结点加入活节点表中。 (3)从活结点表中取下一结点当做当前扩展结点,并重复上述结点扩展操作 这个过程一直持续到所需的解或者活节点表为空为止。 提…

2021年1月31日 0条评论 21点热度 阅读全文

本题参考力扣题解写的理解思路,原文请参照力扣官网242题 https://leetcode-cn.com/problems/valid-anagram/ 题目: 给定两个字符串 s 和 t ,编写一个函数来判断 t 是否是 s 的字母异位词。 示例 1: 输入: s = “anagram”, t = “nagaram” 输出: true 示例 2: 输入: s = “rat”, t = “car” 输出: false 说明: 你可以假设字符串只包含小写字母。 进阶: 如果输入字符串包含 unicode 字符怎么办?…

2021年1月15日 0条评论 169点热度 阅读全文