一、什么是Trie Trie不同于二分搜索树、堆、线段树等二叉树结构,Trie是一个多叉树。使用场景:通讯录高效搜索,专为处理字符串设计的。   比如字典中有n条数据,如果使用树结构,查询的时间复杂度是O(logn),如果有100万条数据的话,logn大约是20,如果有1亿条数据的话,logn大约是30(参考2的N次方计算器) 如果使用Trie这种数据结构,查询每条数据的时间复杂度和字典中一共有多少条数据没有关系!是不是屌炸天呢? Trie查询的时间复杂度与查询的字符长度有关,时间复杂度为:O(w),w为…

2018年10月28日 0条评论 0点热度 阅读全文

最短路径(DP的应用) 单源最短路径,不允许出现负环 核心思想:更新估算距离,松弛 δ ( u , v ) ≤ δ ( u , x ) + δ ( x , v ) \delta(u, v) \leq \delta(u, x) + \delta(x, v) δ(u,v)≤δ(u,x)+δ(x,v) 时间复杂度与采用的数据结构有关,标准的dijkstra应该是用堆实现的。 Array O( v 2 v^2 v2) Binary heap O( ( V + E ) l g V (V+E)lgV (V+E)lgV) Fib…

2018年10月21日 0条评论 0点热度 阅读全文

B-树 B-树是一种多路搜索树(并不一定是二叉的) 1970年,R.Bayer和E.mccreight提出了一种适用于外查找的树,它是一种平衡的多叉树,称为B树(或B-树、B_树)。 一棵m阶B树(balanced tree of order m)是一棵平衡的m路搜索树。它或者是空树,或者是满足下列性质的树: 1、根结点至少有两个子女; 2、每个非根节点所包含的关键字个数 j 满足:┌m/2┐ - 1 <= j <= m - 1; 3、除根结点以外的所有结点(不包括叶子结点)的度数正好是关键字总数加1,…

2018年10月20日 0条评论 0点热度 阅读全文

上一篇我们介绍了图的基础,接下来介绍图的遍历 图的遍历是指从图中的任一顶点出发,对图中的所有顶点访问一次且只访问一次。图的遍历操作和树的遍历操作功能相似。图的遍历是图的一种基本操作,图的其它算法如求解图的连通性问题,拓扑排序,求关键路径等都是建立在遍历算法的基础之上。 由于图结构本身的复杂性,所以图的遍历操作也较复杂,主要表现在以下四个方面: ① 在图结构中,没有一个“自然”的首结点,图中任意一个顶点都可作为第一个被访问的结点。 ② 在非连通图中,从一个顶点出发,只能够访问它所在的连通分量上的所有顶点,因此,还需考…

2018年10月18日 0条评论 0点热度 阅读全文

上一篇我们介绍了二叉查找树,尽管其实现简单,但也有其明显的局限性 一、从二叉查找树到平衡二叉树 一个二叉查找树是由n个节点随机构成,所以,对于某些情况,二叉查找树会退化成一个有n个节点的线性链.如下图:  b图为一个普通的二叉查找树,a图中,如果我们的根节点选择不恰当如最小或者最大的数,那么二叉查找树就完全退化成了线性结构链表,因此,在二叉查找树的基础上,又出现了AVL树,红黑树,它们都是基于二叉查找树,只是在二叉查找树基础上对其做了限制。 二、平衡二叉树(Balanced Binary Tree)AVL…

2018年10月17日 0条评论 0点热度 阅读全文

B树是一种平衡的多路查找树,包括B-树以及B+树。一个节点可以拥有多个key以及多个孩子节点。一棵d+1阶(又称为branch factor)的B树满足如下条件: 根节点非空,则至少两个孩子 内部节点最少含有d个key,最多2*d个key B-树 B-树的每个节点均存储key以及相应的value。B-树还具有如下特点: 节点中key升序排列,并作为其子树的分离点(separator),因此m个key对应m+1个孩子节点 节点中key的个数大于2*d就要对节点进行劈裂,位于中位数左边及右边的key分别构成新孩子节点,…

2018年10月16日 0条评论 0点热度 阅读全文

文章目录 原理 算法中的数据结构 path[]数组深入解释 求单点到其余各点的最短路径 函数:单点到多点的最短路径 完整代码 求两点最短路径 函数:两点的最短路径 完整代码 原理 【迪杰斯特拉Dijkstra】是一种贪心思想 每次从子图(绿色的顶点)中找到一条通往未知顶点(白色)的最短路径(D->E) 将此路中的未知顶点E加入子图(涂绿) 【贪心思想的核心】把刚加入子图的顶点E当成中转站,考虑子图(C、D)经过中转站E到其他顶点的路会不会更近 重复以上步骤,直到子图成长为完整的图 算法中的数据结构 数组 值含…

2018年10月13日 0条评论 0点热度 阅读全文

本文符号意义 q: 插入节点 M: 实际删除节点(后继节点) P: 当前节点的父节点 G: 当前节点的爷爷节点 S: 当前节点的叔叔节点(即父节点的兄弟节点) L: 左孩子 R: 右孩子 非空:节点的key值不为空 二叉搜索树 二叉搜索树的基本操作有search(搜索)、insert(插入)、delete(删除) 搜索 key值小于当前节点,则搜索当前节点的左子树,反之右子树,直到叶节点(左右孩子不存在)。若遇到相同key则返回True。 二叉搜索树的搜索的时间复杂度最好是O(logn),但在以下两种情况下,将和线…

2018年10月13日 0条评论 0点热度 阅读全文

版权声明:本文为博主原创文章,转载请注明出处,https://blog.csdn.net/u014165620/article/details/82976882 B树(B-Tree) 在介绍什么是B树(B-Tree)之前,先看看为什么存在B树结构? B树(B-Tree)是为磁盘或者其他辅助存储设备而设计的一种平衡搜索树,如有的数据库系统使用B树或者B树的变种来存储信息。B树的节点可以有很多孩子,从数个到数千个,不同于一般的二叉树(每个节点最多只有两个孩子)。 下面以磁盘为例说明B树的设计目的。下图是一个典型的磁盘驱…

2018年10月9日 0条评论 0点热度 阅读全文

大多数据结构课本中,串涉及的内容即串的模式匹配,需要掌握的是朴素算法、KMP算法及next值的求法。在考研备考中,参考严奶奶的教材,我也是在关于求next值的算法中卡了一下午时间,感觉挺有意思的,把一些思考的结果整理出来,与大家一起探讨。 本文的逻辑顺序为 1、最基本的朴素算法 2、优化的KMP算法 3、应算法需要定义的next值 4、手动写出较短串的next值的方法 5、最难理解的、足足有5行的代码的求next值的算法 所有铺垫为了最后的第5点,我觉得以这个逻辑下来,由果索因还是相对好理解的,下面写的很通俗,略显…

2018年10月6日 0条评论 0点热度 阅读全文
1345672000