I/O - 数据结构与算法
type: channel
link: https://pugqq.com/tag/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/
items: 数据结构与算法之红黑树
items: 数据结构与算法之字典树
items: 数据结构与算法之LSM树
items: 数据结构与算法之B+树
items: 数据结构与算法之堆
items: 数据结构与算法之树和二叉树
items: 数据结构与算法之线性表的排序
items: 数据结构与算法之线性表的查找
items: 数据结构与算法之栈和队列
items: 数据结构与算法之数组和链表

数据结构与算法之红黑树
type: item
date: 2022-03-12T02:29:00+08:00
description: 平衡二叉树平衡二叉树的严格定义是这样的：二叉树中任意一个节点的左右子树的高度相差不能大于 1。完全二叉树、满二叉树其实都是平衡二叉树，但是非完全二叉树也有可能是平衡二叉树。平衡二叉查找树中“平衡”的意思，其实就是让整棵树左右看起来比较“对称”、比较“平衡”，不要出现左子树很高、右子树很矮的情况。这样就能让整棵树的高度相对来说低一些，相应的插入、删除、查找等操作的效率高一些。什么是红黑树红黑树的英文是“Red-Black Tree”，简称 R-B Tree。它是一种不严格的平衡二叉查找树。红黑树中的节点，一类被标记为黑色，一类被标记为红色。除此之外，一棵红黑树还需要满足这样几个要求：根节点是黑色的；每个叶子节点都是黑色的空节点（NIL），也就是说，叶子节点不存储数据；任何相邻的节点都不能同时为红色，也就是说，红色节点是被黑色节点隔开的；每个节点，从该节点到达其可达叶子节点的所有路径，都包含相同数目的黑色节点；为什么说红黑树是“近似平衡”的？平衡二叉查找树的初衷，是为了解决二叉查找树因为动态更新导致的性能退化问题。所以，“平衡”的意思可以等价为性能不退化。“近似平衡”就等价为性能不会退化的太严重。如果我们将红色节点从红黑树中去掉，那单纯包含黑色节点的红黑树的高度是多少呢？红色节点删除之后，有些节点就没有父节点了，它们会直接拿这些节点的祖父节点（父节点的父节点）作为父节点。所以，之前的二叉树就变成了四叉树。前面红黑树的定义里有这么一条：从任意节点到可达的叶子节点的每个路径包含相同数目的黑色节点。我们从四叉树中取出某些节点，放到叶节点位置，四叉树就变成了完全二叉树。所以，仅包含黑色节点的四叉树的高度，比包含相同节点个数的完全二叉树的高度还要小。现在把红色节点加回去，高度会变成多少呢？在红黑树中，红色节点不能相邻，也就是说，有一个红色节点就要至少有一个黑色节点，将它跟其他红色节点隔开。红黑树中包含最多黑色节点的路径不会超过 log2n，所以加入红色节点之后，最长路径不会超过 2log2n，也就是说，红黑树的高度近似 2log2n。所以，红黑树的高度只比高度平衡的 AVL 树的高度（log2n）仅仅大了一倍，在性能上，下降得并不多。这样推导出来的结果不够精确，实际上红黑树的性能更好。为什么需要红黑树AVL 树是一种高度平衡的二叉树，所以查找的效率非常高，但是，有利就有弊，AVL 树为了维持这种高度的平衡，就要付出更多的代价。每次插入、删除都要做调整，就比较复杂、耗时。所以，对于有频繁的插入、删除操作的数据集合，使用 AVL 树的代价就有点高了。红黑树只是做到了近似平衡，并不是严格的平衡，所以在维护平衡的成本上，要比 AVL 树要低。所以，红黑树的插入、删除、查找各种操作性能都比较稳定。对于工程应用来说，要面对各种异常情况，为了支撑这种工业级的应用，我们更倾向于这种性能稳定的平衡二叉查找树。红黑树平衡调整插入操作的平衡调整红黑树规定，插入的节点必须是红色的。而且，二叉查找树中新插入的节点都是放在叶子节点上。如果插入节点的父节点是黑色的，那我们什么都不用做，它仍然满足红黑树的定义。如果插入的节点是根节点，那我们直接改变它的颜色，把它变成黑色就可以了。除此之外，其他情况都会违背红黑树的定义，于是我们就需要进行调整，调整的过程包含两种基础的操作：左右旋转和改变颜色。红黑树的平衡调整过程是一个迭代的过程。我们把正在处理的节点叫作关注节点。关注节点会随着不停地迭代处理，而不断发生变化。最开始的关注节点就是新插入的节点。新节点插入之后，如果红黑树的平衡被打破，那一般会有下面三种情况。我们只需要根据每种情况的特点，不停地调整，就可以让红黑树继续符合定义，也就是继续保持平衡。CASE 1：如果关注节点是 a，它的叔叔节点 d 是红色，我们就依次执行下面的操作：将关注节点 a 的父节点 b、叔叔节点 d 的颜色都设置成黑色；将关注节点 a 的祖父节点 c 的颜色设置成红色；关注节点变成 a 的祖父节点 c；跳到 CASE 2 或者 CASE 3。CASE 2：如果关注节点是 a，它的叔叔节点 d 是黑色，关注节点 a 是其父节点 b 的右子节点，我们就依次执行下面的操作：关注节点变成节点 a 的父节点 b；围绕新的关注节点 b 左旋；跳到 CASE 3。CASE 3：如果关注节点是 a，它的叔叔节点 d 是黑色，关注节点 a 是其父节点 b 的左子节点，我们就依次执行下面的操作：围绕关注节点 a 的祖父节点 c 右旋；将关注节点 a 的父节点 b、兄弟节点 c 的颜色互换。调整结束。删除操作的平衡调整针对删除节点初步调整CASE 1：如果要删除的节点是 a，它只有一个子节点 b，那我们就依次进行下面的操作：删除节点 a，并且把节点 b 替换到节点 a 的位置…

数据结构与算法之字典树
type: item
date: 2022-03-02T02:28:00+08:00
description: 什么是字典树Trie 树（又叫“前缀树”或“字典树”）是一种用于快速查询“某个字符串/字符前缀”是否存在的数据结构。根节点（Root）不包含字符，除根节点外的每一个节点都仅包含一个字符；从根节点到某一节点路径上所经过的字符连接起来，即为该节点对应的字符串；任意节点的所有子节点所包含的字符都不相同；字典树的构造构建 Trie 树的过程，需要扫描所有的字符串，时间复杂度是 O(n)（n 表示所有字符串的长度和）。字典树非常耗费内存。用数组来存储一个节点的子节点的指针。如果字符串中包含从 a 到 z 这 26 个字符，那每个节点都要存储一个长度为 26 的数组，并且每个数组存储一个 8 字节指针（或者是 4 字节，这个大小跟 CPU、操作系统、编译器等有关）。而且，即便一个节点只有很少的子节点，远小于 26 个，比如 3、4 个，我们也要维护一个长度为 26 的数组。用数组来存储一个节点的子节点的指针。如果字符串中包含从 a 到 z 这 26 个字符，那每个节点都要存储一个长度为 26 的数组，并且每个数组存储一个 8 字节指针（或者是 4 字节，这个大小跟 CPU、操作系统、编译器等有关）。而且，即便一个节点只有很少的子节点，远小于 26 个，比如 3、4 个，我们也要维护一个长度为 26 的数组。用数组来存储一个节点的子节点的指针。如果字符串中包含从 a 到 z 这 26 个字符，那每个节点都要存储一个长度为 26 的数组，并且每个数组存储一个 8 字节指针（或者是 4 字节，这个大小跟 CPU、操作系统、编译器等有关）。而且，即便一个节点只有很少的子节点，远小于 26 个，比如 3、4 个，我们也要维护一个长度为 26 的数组。字典树的查找每次从根结点开始搜索；获取关键词的第一个字符，根据该字符选择对应的子节点，转到该子节点继续检索；在相应的子节点上，获取关键词的第二个字符，进一步选择对应的子节点进行检索；以此类推，进行迭代过程；在某个节点处，关键词的所有字母已被取出，则读取附在该节点上的信息，查找完成。每次查询时，如果要查询的字符串长度是 k，那我们只需要比对大约 k 个节点，就能完成查询操作。跟原本那组字符串的长度和个数没有任何关系。所以说，构建好 Trie 树后，在其中查找字符串的时间复杂度是 O(k)，k 表示要查找的字符串的长度。字典树的应用场景在一组字符串中查找字符串，Trie 树实际上表现得并不好。它对要处理的字符串有及其严苛的要求。第一，字符串中包含的字符集不能太大。我们前面讲到，如果字符集太大，那存储空间可能就会浪费很多。即便可以优化，但也要付出牺牲查询、插入效率的代价。第二，要求字符串的前缀重合比较多，不然空间消耗会变大很多。第三，如果要用 Trie 树解决问题，那我们就要自己从零开始实现一个 Trie 树，还要保证没有 bug，这个在工程上是将简单问题复杂化，除非必须，一般不建议这样做。第四，我们知道，通过指针串起来的数据块是不连续的，而 Trie 树中用到了指针，所以，对缓存并不友好，性能上会打个折扣。在一组字符串中查找字符串，Trie 树实际上表现得并不好。它对要处理的字符串有及其严苛的要求。在一组字符串中查找字符串，Trie 树实际上表现得并不好。它对要处理的字符串有及其严苛的要求。（1）自动补全（2）拼写检查（3）IP 路由 (最长前缀匹配)图 3. 使用 Trie 树的最长前缀匹配算法，Internet 协议（IP）路由中利用转发表选择路径。（4）T9 (九宫格) 打字预测（5）单词游戏Trie 树可通过剪枝搜索空间来高效解决 Boggle 单词游戏参考资料数据结构与算法之美https://leetcode-cn.com/problems/implement-trie-prefix-tree/solution/shi-xian-trie-qian-zhui-shu-by-leetcode/

数据结构与算法之LSM树
type: item
date: 2022-02-24T02:23:00+08:00
description: 什么是 LSM 树LSM 树具有以下 3 个特点：将索引分为内存和磁盘两部分，并在内存达到阈值时启动树合并（Merge Trees）；用批量写入代替随机写入，并且用预写日志 WAL 技术（Write AheadLog，预写日志技术）保证内存数据，在系统崩溃后可以被恢复；数据采取类似日志追加写的方式写入（Log Structured）磁盘，以顺序写的方式提高写入效率。LSM 树的这些特点，使得它相对于 B+ 树，在写入性能上有大幅提升。所以，许多 NoSQL 系统都使用 LSM 树作为检索引擎，而且还对 LSM 树进行了优化以提升检索性能。LSM 树就是根据这个思路设计了这样一个机制：当数据写入时，延迟写磁盘，将数据先存放在内存中的树里，进行常规的存储和查询。当内存中的树持续变大达到阈值时，再批量地以块为单位写入磁盘的树中。因此，LSM 树至少需要由两棵树组成，一棵是存储在内存中较小的 C0 树，另一棵是存储在磁盘中较大的 C1 树。如何将内存数据与磁盘数据合并可以参考两个有序链表归并排序的过程，将 C0 树和 C1 树的所有叶子节点中存储的数据，看作是两个有序链表，那滚动合并问题就变成了我们熟悉的两个有序链表的归并问题。不过由于涉及磁盘操作，那为了提高写入效率和检索效率，我们还需要针对磁盘的特性，在一些归并细节上进行优化。由于磁盘具有顺序读写效率高的特性，因此，为了提高 C1 树中节点的读写性能，除了根节点以外的节点都要尽可能地存放到连续的块中，让它们能作为一个整体单位来读写。这种包含多个节点的块就叫作多页块（Multi-Pages Block）。第一步，以多页块为单位，将 C1 树的当前叶子节点从前往后读入内存。读入内存的多页块，叫作清空块（Emptying Block），意思是处理完以后会被清空。第二步，将 C0 树的叶子节点和清空块中的数据进行归并排序，把归并的结果写入内存的一个新块中，叫作填充块（Filling Block）。第三步，如果填充块写满了，我们就要将填充块作为新的叶节点集合顺序写入磁盘。这个时候，如果 C0 树的叶子节点和清空块都没有遍历完，我们就继续遍历归并，将数据写入新的填充块。如果清空块遍历完了，我们就去 C1 树中顺序读取新的多页块，加载到清空块中。第四步，重复第三步，直到遍历完 C0 树和 C1 树的所有叶子节点，并将所有的归并结果写入到磁盘。这个时候，我们就可以同时删除 C0 树和 C1 树中被处理过的叶子节点。这样就完成了滚动归并的过程。LSM 树是如何检索因为同时存在 C0 和 C1 树，所以要查询一个 key 时，我们会先到 C0 树中查询。如果查询到了则直接返回；如过没有查询到，则查询 C1 树。需要注意一种特殊情况：删除操作。假设某数据在 C0 树中被删除了，但是在 C1 树中仍存在。这此时查询时，可以在 C1 树中查到这个 key，这其实是过期数据了，如何应对这种情况呢？对于被删除的数据，可以将这些数据的 key 插入到 C0 树中，并标记一个删除标志。如果查到了一个带着删除标志的 key，就直接返回查询失败。为什么需要 LSM 树在关系型数据库中，通常使用 B+ 树作为索引。B+ 树的数据都存储在叶子节点中，而叶子节点一般都存储在磁盘中。因此，每次插入的新数据都需要随机写入磁盘，而随机写入的性能非常慢。如果是一个日志系统，每秒钟要写入上千条甚至上万条数据，这样的磁盘操作代价会使得系统性能急剧下降，甚至无法使用。操作系统对磁盘的读写是以块为单位的，我们能否以块为单位写入，而不是每次插入一个数据都要随机写入磁盘呢？这样是不是就可以大幅度减少写入操作了呢？解决方案就是：LSM 树（Log Structured Merge Trees）。WAL 技术LSM 树至少需要由两棵树组成，一棵是存储在内存中较小的 C0 树，另一棵是存储在磁盘中较大的 C1 树。如果机器断电或系统崩溃了，那内存中还未写入磁盘的数据岂不就永远丢失了？这种情况我们该如何解决呢？为了保证内存中的数据在系统崩溃后能恢复，可以使用 WAL 技术（Write Ahead Log，预写日志技术）将数据第一时间高效写入磁盘进行备份。WAL 技术保存和恢复数据的具体步骤如下：内存中的程序在处理数据时，会先将对数据的修改作为一条记录，顺序写入磁盘的 log 文件作为备份。由于磁盘文件的顺序追加写入效率很高，因此许多应用场景都可以接受这种备份处理。在数据写入 log 文件后，备份就成功了。接下来，该数据就可以长期驻留在内存中了。系统会周期性地检查内存中的数据是否都被处理完了（比如，被删除或者写入磁盘），并且生成对应的检查点（Check Point）记录在磁盘中。然后，我们就可以随时删除被处理完的数据了。这样一来，log 文件就不会无限增…

数据结构与算法之B+树
type: item
date: 2022-02-15T02:22:00+08:00
description: 什么是 B+树B+树是在二叉查找树的基础上进行了改造：树中的节点并不存储数据本身，而是只是作为索引。每个叶子节点串在一条链表上，链表中的数据是从小到大有序的。改造之后，如果我们要求某个区间的数据。我们只需要拿区间的起始值，在树中进行查找，当查找到某个叶子节点之后，我们再顺着链表往后遍历，直到链表中的结点数据值大于区间的终止值为止。所有遍历到的数据，就是符合区间值的所有数据。但是，我们要为几千万、上亿的数据构建索引，如果将索引存储在内存中，尽管内存访问的速度非常快，查询的效率非常高，但是，占用的内存会非常多。比如，我们给一亿个数据构建二叉查找树索引，那索引中会包含大约 1 亿个节点，每个节点假设占用 16 个字节，那就需要大约 1GB 的内存空间。给一张表建立索引，我们需要 1GB 的内存空间。如果我们要给 10 张表建立索引，那对内存的需求是无法满足的。如何解决这个索引占用太多内存的问题呢？我们可以借助时间换空间的思路，把索引存储在硬盘中，而非内存中。我们都知道，硬盘是一个非常慢速的存储设备。通常内存的访问速度是纳秒级别的，而磁盘访问的速度是毫秒级别的。读取同样大小的数据，从磁盘中读取花费的时间，是从内存中读取所花费时间的上万倍，甚至几十万倍。这种将索引存储在硬盘中的方案，尽管减少了内存消耗，但是在数据查找的过程中，需要读取磁盘中的索引，因此数据查询效率就相应降低很多。二叉查找树，经过改造之后，支持区间查找的功能就实现了。不过，为了节省内存，如果把树存储在硬盘中，那么每个节点的读取（或者访问），都对应一次磁盘 IO 操作。树的高度就等于每次查询数据时磁盘 IO 操作的次数。我们前面讲到，比起内存读写操作，磁盘 IO 操作非常耗时，所以我们优化的重点就是尽量减少磁盘 IO 操作，也就是，尽量降低树的高度。那如何降低树的高度呢？我们来看下，如果我们把索引构建成 m 叉树，高度是不是比二叉树要小呢？如图所示，给 16 个数据构建二叉树索引，树的高度是 4，查找一个数据，就需要 4 个磁盘 IO 操作（如果根节点存储在内存中，其他结点存储在磁盘中），如果对 16 个数据构建五叉树索引，那高度只有 2，查找一个数据，对应只需要 2 次磁盘操作。如果 m 叉树中的 m 是 100，那对一亿个数据构建索引，树的高度也只是 3，最多只要 3 次磁盘 IO 就能获取到数据。磁盘 IO 变少了，查找数据的效率也就提高了。为什么需要 B+树关系型数据库中常用 B+ 树作为索引，这是为什么呢？思考以下经典应用场景根据某个值查找数据，比如 select * from user where id=1234。根据区间值来查找某些数据，比如 select * from user where id > 1234 and id < 2345。为了提高查询效率，需要使用索引。而对于索引的性能要求，主要考察执行效率和存储空间。如果让你选择一种数据结构去存储索引，你会如何考虑？以一些常见数据结构为例：哈希表：哈希表的查询性能很好，时间复杂度是 O(1)。但是，哈希表不能支持按照区间快速查找数据。所以，哈希表不能满足我们的需求。平衡二叉查找树：尽管平衡二叉查找树查询的性能也很高，时间复杂度是 O(logn)。而且，对树进行中序遍历，我们还可以得到一个从小到大有序的数据序列，但这仍然不足以支持按照区间快速查找数据。跳表：跳表是在链表之上加上多层索引构成的。它支持快速地插入、查找、删除数据，对应的时间复杂度是 O(logn)。并且，跳表也支持按照区间快速地查找数据。我们只需要定位到区间起点值对应在链表中的结点，然后从这个结点开始，顺序遍历链表，直到区间终点对应的结点为止，这期间遍历得到的数据就是满足区间值的数据。实际上，数据库索引所用到的数据结构跟跳表非常相似，叫作 B+ 树。不过，它是通过二叉查找树演化过来的，而非跳表。B+树的应用场景参考资料数据结构与算法之美

数据结构与算法之堆
type: item
date: 2022-02-12T02:20:00+08:00
description: 什么是堆？堆（Heap）是一个可以被看成近似完全二叉树的数组。堆是一个完全二叉树。完全二叉树要求，除了最后一层，其他层的节点个数都是满的，最后一层的节点都靠左排列。堆中每一个节点的值都必须大于等于（或小于等于）其子树中每个节点的值。堆可以分为大顶堆和小顶堆。对于每个节点的值都大于等于子树中每个节点值的堆，叫作“大顶堆”。对于每个节点的值都小于等于子树中每个节点值的堆，叫作“小顶堆”。如何实现堆完全二叉树比较适合用数组来存储。用数组来存储完全二叉树是非常节省存储空间的。因为我们不需要存储左右子节点的指针，单纯地通过数组的下标，就可以找到一个节点的左右子节点和父节点。堆常见的操作：HEAPIFY 建堆：把一个乱序的数组变成堆结构的数组，时间复杂度为 $$O(n)$$。HEAPPUSH：把一个数值放进已经是堆结构的数组中，并保持堆结构，时间复杂度为 $$O(log N)$$HEAPPOP：从最大堆中取出最大值或从最小堆中取出最小值，并将剩余的数组保持堆结构，时间复杂度为 $$O(log N)$$。HEAPSORT：借由 HEAPFY 建堆和 HEAPPOP 堆数组进行排序，时间复杂度为$$ O(N log N)$$，空间复杂度为 $$O(1)$$。堆的应用场景求 TOP N堆结构的一个常见应用是建立优先队列（Priority Queue）。求 Top K 的问题抽象成两类。一类是针对静态数据集合；另一类是针对动态数据集合优先级队列在优先级队列中，数据的出队顺序不是先进先出，而是按照优先级来，优先级最高的，最先出队。堆和优先级队列非常相似：往优先级队列中插入一个元素，就相当于往堆中插入一个元素；从优先级队列中取出优先级最高的元素，就相当于取出堆顶元素。参考：Java 的 PriorityQueue 类

数据结构与算法之树和二叉树
type: item
date: 2022-02-09T02:18:00+08:00
description: 树什么是树在计算机科学中，树（英语：tree）是一种抽象数据类型（ADT）或是实现这种抽象数据类型的数据结构，用来模拟具有树状结构性质的数据集合。它是由 n（n>0）个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：每个节点都只有有限个子节点或无子节点。树有且仅有一个根节点。根节点没有父节点；非根节点有且仅有一个父节点。每个非根节点可以分为多个不相交的子树。树里面没有环路。树的术语节点的度：一个节点含有的子树的个数称为该节点的度；树的度：一棵树中，最大的节点度称为树的度；叶子节点或终端节点：度为零的节点；非终端节点或分支节点：度不为零的节点；父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点；子节点：一个节点含有的子树的根节点称为该节点的子节点；兄弟节点：具有相同父节点的节点互称为兄弟节点；堂兄弟节点：父节点在同一层的节点互为堂兄弟；节点的祖先：从根到该节点所经分支上的所有节点；子孙：以某节点为根的子树中任一节点都称为该节点的子孙。森林：由 m（m>=0）棵互不相交的树的集合称为森林；节点的高度：节点到叶子节点的最长路径。高度是从下往上度量。节点的深度：根节点到该节点的最长路径。深度是从上往下度量。节点的层次：节点的深度 + 1。树的高度：根节点的高度。树的性质树中的节点数等于所有节点的度数加 1。度为 m 的树中第 i 层上至多有 $$m^{i-1}$$ 个节点（$$i ≥ 1$$）。高度为 h 的 m 次树至多有 $$(m^h-1)/(m-1)$$ 个节点。具有 n 个节点的 m 次树的最小高度为 $$\log_m{(n(m-1)+1)}$$ 。树的种类无序树：树中任意节点的子节点之间没有顺序关系，这种树称为无序树，也称为自由树；有序树：树中任意节点的子节点之间有顺序关系，这种树称为有序树；二叉树：每个节点最多含有两个子树的树称为二叉树；完全二叉树：对于一颗二叉树，假设其深度为 d（d>1）。除了第 d 层外，其它各层的节点数目均已达最大值，且第 d 层所有节点从左向右连续地紧密排列，这样的二叉树被称为完全二叉树；满二叉树：所有叶节点都在最底层的完全二叉树；平衡二叉树（AVL 树）：当且仅当任何节点的两棵子树的高度差不大于 1 的二叉树；排序二叉树(二叉查找树（英语：Binary Search Tree))：也称二叉搜索树、有序二叉树；霍夫曼树：带权路径最短的二叉树称为哈夫曼树或最优二叉树；B 树：一种对读写操作进行优化的自平衡的二叉查找树，能够保持数据有序，拥有多于两个子树。二叉树二叉树中的每个节点最多有两个子节点，分别是左子节点和右子节点。二叉树的性质二叉树第 i 层上的结点数目最多为 2i-1 (i≥1)。深度为 k 的二叉树至多有 2k-1 个结点(k≥1)。包含 n 个结点的二叉树的高度至少为 log2(n+1)。在任意一棵二叉树中，若终端结点的个数为 n0，度为 2 的结点数为 n2，则 n0=n2+1。满二叉树除了叶子节点之外，每个节点都有左右两个子节点，这种二叉树就叫作满二叉树。完全二叉树叶子节点都在最底下两层，最后一层的叶子节点都靠左排列，并且除了最后一层，其他层的节点个数都要达到最大，这种二叉树叫作完全二叉树。特点：叶子结点只能出现在最下层和次下层，且最下层的叶子结点集中在树的左部。显然，一棵满二叉树必定是一棵完全二叉树，而完全二叉树未必是满二叉树。存储一棵二叉树，有两种方法，一种是基于指针或者引用的二叉链式存储法，一种是基于数组的顺序存储法。二叉链式存储法每个节点有三个字段，其中一个存储数据，另外两个是指向左右子节点的指针。顺序存储法如果节点 X 存储在数组中下标为 i 的位置，下标为 2 i 的位置存储的就是左子节点，下标为 2 i + 1 的位置存储的就是右子节点。反过来，下标为 i/2 的位置存储就是它的父节点。通过这种方式，我们只要知道根节点存储的位置（一般情况下，为了方便计算子节点，根节点会存储在下标为 1 的位置），这样就可以通过下标计算，把整棵树都串起来。如果是非完全二叉树，其实会浪费比较多的数组存储空间。所以，如果某棵二叉树是一棵完全二叉树，那用数组存储无疑是最节省内存的一种方式。因为数组的存储方式并不需要像链式存储法那样，要存储额外的左右子节点的指针。这也是 为什么完全二叉树要求最后一层的子节点都靠左的原因。二叉树的遍历二叉树的遍历有三种方式：前序遍历：对于树中的任意节点来说，先打印这个节点，然后再打印它的左子树，最后打印它的右子树。中序遍历：对于树中的任意节点来说，先打印它的左子树，然后再打印它本身，最后打印它的右子树。后序遍历是指，对于树中的任意节点来说，先打印它的左子树，然后再打印它的右…

数据结构与算法之线性表的排序
type: item
date: 2022-02-08T02:14:00+08:00
description: 冒泡排序要点冒泡排序是一种交换排序。什么是交换排序呢？交换排序：两两比较待排序的关键字，并交换不满足次序要求的那对数，直到整个表都满足次序要求为止。算法思想它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端，故名。假设有一个大小为 N 的无序序列。冒泡排序就是要每趟排序过程中通过两两比较，找到第 i 个小（大）的元素，将其往上排。以上图为例，演示一下冒泡排序的实际流程：假设有一个无序序列 { 4. 3. 1. 2, 5 }第一趟排序：通过两两比较，找到第一小的数值 1 ，将其放在序列的第一位。第二趟排序：通过两两比较，找到第二小的数值 2 ，将其放在序列的第二位。第三趟排序：通过两两比较，找到第三小的数值 3 ，将其放在序列的第三位。至此，所有元素已经有序，排序结束。要将以上流程转化为代码，我们需要像机器一样去思考，不然编译器可看不懂。假设要对一个大小为 N 的无序序列进行升序排序（即从小到大）。每趟排序过程中需要通过比较找到第 i 个小的元素。所以，我们需要一个外部循环，从数组首端(下标 0) 开始，一直扫描到倒数第二个元素（即下标 N - 2) ，剩下最后一个元素，必然为最大。假设是第 i 趟排序，可知，前 i-1 个元素已经有序。现在要找第 i 个元素，只需从数组末端开始，扫描到第 i 个元素，将它们两两比较即可。所以，需要一个内部循环，从数组末端开始（下标 N - 1），扫描到 (下标 i + 1)。核心代码public void bubbleSort(int[] list) { int temp = 0; // 用来交换的临时数 // 要遍历的次数 for (int i = 0; i < list.length - 1; i++) { // 从后向前依次的比较相邻两个数的大小，遍历一次后，把数组中第i小的数放在第i个位置上 for (int j = list.length - 1; j > i; j--) { // 比较相邻的元素，如果前面的数大于后面的数，则交换 if (list[j - 1] > list[j]) { temp = list[j - 1]; list[j - 1] = list[j]; list[j] = temp; } } System.out.format("第 %d 趟：\t", i); printAll(list); } }算法分析冒泡排序算法的性能参数结果排序类别交换排序排序方法冒泡排序时间复杂度平均情况O(N2)时间复杂度最坏情况O(N3)时间复杂度最好情况O(N)空间复杂度O(1)稳定性稳定复杂性简单时间复杂度若文件的初始状态是正序的，一趟扫描即可完成排序。所需的关键字比较次数 C 和记录移动次数 M 均达到最小值：Cmin = N - 1, Mmin = 0。所以，冒泡排序最好时间复杂度为 O(N)。若初始文件是反序的，需要进行 N -1 趟排序。每趟排序要进行 N - i 次关键字的比较(1 ≤ i ≤ N - 1)，且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下，比较和移动次数均达到最大值：Cmax = N(N-1)/2 = O(N2)Mmax = 3N(N-1)/2 = O(N2)冒泡排序的最坏时间复杂度为 O(N2)。因此，冒泡排序的平均时间复杂度为 O(N2)。总结起来，其实就是一句话：当数据越接近正序时，冒泡排序性能越好。算法稳定性冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较，交换也发生在这两个元素之间。所以相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定排序算法。优化对冒泡排序常见的改进方法是加入标志性变量 exchange，用于标志某一趟排序过程中是否有数据交换。如果进行某一趟排序时并没有进行数据交换，则说明所有数据已经有序，可立即结束排序，避免不必要的比较过程。核心代码// 对 bubbleSort 的优化算法 public void bubbleSort_2(int[] list) { int temp = 0; // 用来交换的临时数 boolean bChange = false; // 交换标志 // 要遍历的次数 for (int i = 0; i < list.length - 1; i++) { bChange = false; // 从后向前依次的比较相邻两个数的大小，遍历一次后，把数组中第i小的数放在第i个位置上 for (int j = list.length - 1; j > i; j--) { // 比较相邻的元素，如果前面…

数据结构与算法之线性表的查找
type: item
date: 2022-02-07T02:11:00+08:00
description: 查找简介什么是查找？查找是根据给定的某个值，在表中确定一个关键字的值等于给定值的记录或数据元素。查找算法的分类若在查找的同时对表记录做修改操作（如插入和删除），则相应的表称之为动态查找表；否则，称之为静态查找表。此外，如果查找的全过程都在内存中进行，称之为内查找；反之，如果查找过程中需要访问外存，称之为外查找。查找算法性能比较的标准——平均查找长度 ASL（Average Search Length）由于查找算法的主要运算是关键字的比较过程，所以通常把查找过程中对关键字需要执行的平均比较长度（也称为平均比较次数）作为衡量一个查找算法效率优劣的比较标准。选取查找算法的因素(1) 使用什么数据存储结构（如线性表、树形表等）。(2) 表中的次序，即对无序表还是有序表进行查找。顺序查找要点它是一种最简单的查找算法，效率也很低下。存储结构没有存储结构要求，可以无序，也可以有序。基本思想从数据结构线形表的一端开始，顺序扫描，依次将扫描到的结点关键字与给定值 k 相比较，若相等则表示查找成功；若扫描结束仍没有找到关键字等于 k 的结点，表示查找失败。核心代码public int orderSearch(int[] list, int length, int key) { // 从前往后扫描list数组，如果有元素的值与key相等，直接返回其位置 for (int i = 0; i < length; i++) { if (key == list[i]) { return i; } } // 如果扫描完，说明没有元素的值匹配key，返回-1，表示查找失败 return -1; }算法分析顺序查找算法最好的情况是，第一个记录即匹配关键字，则需要比较 1 次；最坏的情况是，最后一个记录匹配关键字，则需要比较 N 次。所以，顺序查找算法的平均查找长度为ASL = (N + N-1 + ... + 2 + 1) / N = (N+1) / 2顺序查找的平均时间复杂度为O(N)。二分查找二分查找针对的是一个有序的数据集合，查找思想有点类似分治思想。每次都通过跟区间的中间元素对比，将待查找的区间缩小为之前的一半，直到找到要查找的元素，或者区间被缩小为 0。存储结构使用二分查找需要两个前提：(1) 必须是顺序存储结构。(2) 必须是有序的表。基本思想首先，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。核心代码public int binarySearch(int[] list, int length, int key) { int low = 0, mid = 0, high = length - 1; while (low <= high) { mid = (low + high) / 2; if (list[mid] == key) { return mid; // 查找成功，直接返回位置 } else if (list[mid] < key) { low = mid + 1; // 关键字大于中间位置的值，则在大值区间[mid+1, high]继续查找 } else { high = mid - 1; // 关键字小于中间位置的值，则在小值区间[low, mid-1]继续查找 } } return -1; }算法分析二分查找的过程可看成一个二叉树。把查找区间的中间位置视为树的根，左区间和右区间视为根的左子树和右子树。由此得到的二叉树，称为二分查找的判定树或比较树。由此可知，二分查找的平均查找长度实际上就是树的高度O(log2N)。二分查找的局限性二分查找依赖的是顺序表结构，简单点说就是数组二分查找针对的是有序数据数据量太小不适合二分查找数据量太大也不适合二分查找分块查找要点分块查找(Blocking Search)又称索引顺序查找。它是一种性能介于顺序查找和二分查找之间的查找方法。分块查找由于只要求索引表是有序的，对块内节点没有排序要求，因此特别适合于节点动态变化的情况。存储结构分块查找表是由“分块有序”的线性表和索引表两部分构成的。所谓“分块有序”的线性表，是指：假设要排序的表为 R[0...N-1]，将表均匀分成 b 块，前 b-1 块中记录个数为 s=N/b，最后一块记录数小于等于 s；每一块中的关键字不一定有序，但前一块中的最大关键字必须小于后一块中的最小关键字。注：这是使用分块查找的前提条件。如上将表均匀分成 b 块后，抽取各块中的最大关键字和起始位置构成一个索引表 IDX[0...b-1]。由于表 R …

数据结构与算法之栈和队列
type: item
date: 2022-02-05T02:08:00+08:00
description: 队列和栈都是操作受限的线性表：前者先进先出，后者先进后出。栈栈是什么在 LIFO(后进先出) 数据结构中，将首先处理添加到队列中的最新元素。栈是一个 LIFO(后进先出) 数据结构。栈是一种“操作受限”的线性表，只允许在一端插入和删除数据。通常，插入操作在栈中被称作入栈 push 。与队列类似，总是在堆栈的末尾添加一个新元素。但是，删除操作，退栈 pop ，将始终删除队列中相对于它的最后一个元素。当某个数据集合只涉及在一端插入和删除数据，并且满足后进先出、先进后出的特性，我们就应该首选“栈”这种数据结构。从栈的定义可以看出，栈只支持两个基本操作：入栈 push() 和 出栈 pop() ，也就是在栈顶插入一个数据和从栈顶删除一个数据。在入栈和出栈过程中，只需要一两个临时变量存储空间，所以空间复杂度是 O(1)。栈既可以用数组来实现，也可以用链表来实现。用数组实现的栈，我们叫作顺序栈，用链表实现的栈，我们叫作链式栈。为什么需要栈相比数组和链表，栈只是对操作进行了限制，似乎并没有任何优势。为什么不直接使用数组或者链表？为什么还要用这个“操作受限”的“栈”呢？特定的数据结构是对特定场景的抽象，而且，数组或链表暴露了太多的操作接口，操作上的确灵活自由，但使用时就比较不可控，自然也就更容易出错。栈的应用场景（1）函数调用栈（2）表达式求值（3）表达式匹配可以借助栈来检查表达式中的括号是否匹配队列在 FIFO 数据结构中，将首先处理添加到队列中的第一个元素。队列是典型的 FIFO 数据结构。插入（insert）操作也称作入队（enqueue），新元素始终被添加在队列的末尾。 删除（delete）操作也被称为出队（dequeue)。 你只能移除第一个元素。什么是队列队列：先进先出的线性表。队列是一种“操作受限”的线性表，只允许在一端插入数据，在另一端删除数据。队列的最基本操作：入队 enqueue()，放一个数据到队列尾部；出队 dequeue()，从队列头部取一个元素。队列可以用数组来实现，也可以用链表来实现。用数组实现的队列叫作顺序队列，用链表实现的队列叫作链式队列。队满的判断条件是 tail == n，队空的判断条件是 head == tail。循环队列循环队列是一种较为特殊的队列。循环队列的要点是确定好 队空和队满的判定条件。在用数组实现的非循环队列中，队满的判断条件是 (tail+1) % n == head，队空的判断条件是 head == tail。为什么需要队列为什么需要队列和为什么需要栈，是同样的道理，参考 为什么需要栈队列的应用场景（1）阻塞队列阻塞队列其实就是在队列基础上增加了阻塞操作。简单来说，就是：在队列为空的时候，从队头取数据会被阻塞。因为此时还没有数据可取，直到队列中有了数据才能返回；如果队列已经满了，那么插入数据的操作就会被阻塞，直到队列中有空闲位置后再插入数据，然后再返回。（2）并发队列线程安全的队列我们叫作并发队列。最简单直接的实现方式是直接在 enqueue()、dequeue() 方法上加锁，但是锁粒度大并发度会比较低，同一时刻仅允许一个存或者取操作。实际上，基于数组的循环队列，利用 CAS 原子操作，可以实现非常高效的并发队列。这也是循环队列比链式队列应用更加广泛的原因。参考资料数据结构与算法之美Leetcode：栈和队列

数据结构与算法之数组和链表
type: item
date: 2022-02-05T02:05:00+08:00
description: 数组和链表分别代表了连续空间和不连续空间的存储方式，它们是线性表（Linear List）的典型代表。其他所有的数据结构，比如栈、队列、二叉树、B+ 树等，实际上都是这两者的结合和变化。数组数组用 连续 的内存空间来存储数据。数组的访问数组元素的访问是以行或列索引的单一下标表示。在上面的例子中，数组 a 中有 5 个元素。也就是说，a 的长度是 6 。我们可以使用 a[0] 来表示数组中的第一个元素。因此，a[0] = A 。类似地，a[1] = B，a[2] = C，依此类推。数组的插入数组的删除数组的特性数组设计之初是在形式上依赖内存分配而成的，所以必须在使用前预先分配好空间大小。这使得数组有以下特性：用连续的内存空间来存储数据。数组支持随机访问，根据下标随机访问的时间复杂度为 O(1)。数组的插入、删除操作，平均时间复杂度为 O(n)。空间大小固定，一旦建立，不能再改变。扩容只能采用复制数组的方式。在旧式编程语言中（如有中阶语言之称的 C），程序不会对数组的操作做下界判断，也就有潜在的越界操作的风险。多维数组数组是有下标和值组成集合。如果数组的下标有多个维度，即为多维数组。比如：二维数组可以视为“数组元素为一维数组”的一维数组；三维数组可以视为“数组元素为二维数组”的一维数组；依次类推。下图是由 M 个行向量，N 个列向量组成的二维数组.链表链表用不连续的内存空间来存储数据；并通过一个指针按顺序将这些空间串起来，形成一条链。区别于数组，链表中的元素不是存储在内存中连续的一片区域，链表中的数据存储在每一个称之为“结点”复合区域里，在每一个结点除了存储数据以外，还保存了到下一个节点的指针（Pointer）。由于不必按顺序存储，链表在插入数据的时候可以达到 O(1) 的复杂度，但是查找一个节点或者访问特定编号的节点则需要 O(n) 的时间。链表具有以下特性：链表允许插入和移除任意位置上的节点，其时间复杂度为 O(1)链表没有数组的随机访问特性，链表只支持顺序访问，其时间复杂度为 O(n)。数组的空间大小是固定的，而链表的空间大小可以动态增长。相比于数组，链表支持扩容，显然更为灵活，但是由于多了指针域，空间开销也更大。链表相比于数组，多了头指针、尾指针（非必要），合理使用可以大大提高访问效率。链表有多种类型：单链表双链表循环链表单链表单链表中的每个结点不仅包含数据值，还包含一个指针，指向其后继节点。通过这种方式，单链表将所有结点按顺序组织起来。与数组不同，我们无法在常量时间内访问单链表中的随机元素。 如果我们想要获得第 i 个元素，我们必须从头结点逐个遍历。 我们按 索引 来 访问元素 平均要花费 O(N) 时间，其中 N 是链表的长度。单链表插入如果我们想在给定的结点 prev 之后添加新值，我们应该：（1）使用给定值初始化新结点 cur；（2）将 cur 的 next 字段链接到 prev 的下一个结点 next ；（3）将 prev 中的 next 字段链接到 cur 。与数组不同，我们不需要将所有元素移动到插入元素之后。因此，您可以在 O(1) 时间复杂度中将新结点插入到链表中，这非常高效。单链表删除如果我们想从单链表中删除现有结点 cur，可以分两步完成：（1）找到 cur 的上一个结点 prev 及其下一个结点 next ；（2）接下来链接 prev 到 cur 的下一个节点 next 。在我们的第一步中，我们需要找出 prev 和 next。使用 cur 的参考字段很容易找出 next，但是，我们必须从头结点遍历链表，以找出 prev，它的平均时间是 O(N)，其中 N 是链表的长度。因此，删除结点的时间复杂度将是 O(N)。空间复杂度为 O(1)，因为我们只需要常量空间来存储指针。双链表双链表中的每个结点不仅包含数据值，还包含两个指针，分别指向指向其前驱节点和后继节点。单链表的访问是单向的，而双链表的访问是双向的。显然，双链表比单链表操作更灵活，但是空间开销也更大。双链表以类似的方式工作，但还有一个引用字段，称为“prev”字段。有了这个额外的字段，您就能够知道当前结点的前一个结点。双链表插入如果我们想在给定的结点 prev 之后添加新值，我们应该：（1）使用给定值初始化新结点 cur；（2）链接 cur 与 prev 和 next，其中 next 是 prev 原始的下一个节点；（3）用 cur 重新链接 prev 和 next。与单链表类似，添加操作的时间和空间复杂度都是 O(1)。双链表删除如果我们想从双链表中删除一个现有的结点 cur，我们可以简单地将它的前一个结点 prev 与下一个结点 next 链接起来。与单链表不同，使用 prev 字段可以很容易地在常量时间内获得前一个结点。因为我们不再需要遍历链…