平衡二叉树平衡二叉树的严格定义是这样的：二叉树中任意一个节点的左右子树的高度相差不能大于 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 的位置，这一部分操作跟普通的二叉查找树的删除操作一样；节点 a 只能是黑色，节点 b 也只能是红色，其他情况均不符合红黑树的定义。这种情况下，我们把节点 b 改为黑色；调整结束，不需要进行二次调整。CASE 2：如果要删除的节点 a 有两个非空子节点，并且它的后继节点就是节点 a 的右子节点 c。我们就依次进行下面的操作：如果节点 a 的后继节点就是右子节点 c，那右子节点 c 肯定没有左子树。我们把节点 a 删除，并且将节点 c 替换到节点 a 的位置。这一部分操作跟普通的二叉查找树的删除操作无异；然后把节点 c 的颜色设置为跟节点 a 相同的颜色；如果节点 c 是黑色，为了不违反红黑树的最后一条定义，我们给节点 c 的右子节点 d 多加一个黑色，这个时候节点 d 就成了“红 - 黑”或者“黑 - 黑”；这个时候，关注节点变成了节点 d，第二步的调整操作就会针对关注节点来做。CASE 3：如果要删除的是节点 a，它有两个非空子节点，并且节点 a 的后继节点不是右子节点，我们就依次进行下面的操作：找到后继节点 d，并将它删除，删除后继节点 d 的过程参照 CASE 1；将节点 a 替换成后继节点 d；把节点 d 的颜色设置为跟节点 a 相同的颜色；如果节点 d 是黑色，为了不违反红黑树的最后一条定义，我们给节点 d 的右子节点 c 多加一个黑色，这个时候节点 c 就成了“红 - 黑”或者“黑 - 黑”；这个时候，关注节点变成了节点 c，第二步的调整操作就会针对关注节点来做。针对关注节点进行二次调整CASE 1：如果关注节点是 a，它的兄弟节点 c 是红色的，我们就依次进行下面的操作：围绕关注节点 a 的父节点 b 左旋；关注节点 a 的父节点 b 和祖父节点 c 交换颜色；关注节点不变；继续从四种情况中选择适合的规则来调整。CASE 2：如果关注节点是 a，它的兄弟节点 c 是黑色的，并且节点 c 的左右子节点 d、e 都是黑色的，我们就依次进行下面的操作：将关注节点 a 的兄弟节点 c 的颜色变成红色；从关注节点 a 中去掉一个黑色，这个时候节点 a 就是单纯的红色或者黑色；给关注节点 a 的父节点 b 添加一个黑色，这个时候节点 b 就变成了“红 - 黑”或者“黑 - 黑”；关注节点从 a 变成其父节点 b；继续从四种情况中选择符合的规则来调整。CASE 3：如果关注节点是 a，它的兄弟节点 c 是黑色，c 的左子节点 d 是红色，c 的右子节点 e 是黑色，我们就依次进行下面的操作：围绕关注节点 a 的兄弟节点 c 右旋；节点 c 和节点 d 交换颜色；关注节点不变；跳转到 CASE 4，继续调整。CASE 4：如果关注节点 a 的兄弟节点 c 是黑色的，并且 c 的右子节点是红色的，我们就依次进行下面的操作：围绕关注节点 a 的父节点 b 左旋；将关注节点 a 的兄弟节点 c 的颜色，跟关注节点 a 的父节点 b 设置成相同的颜色；将关注节点 a 的父节点 b 的颜色设置为黑色；从关注节点 a 中去掉一个黑色，节点 a 就变成了单纯的红色或者黑色；将关注节点 a 的叔叔节点 e 设置为黑色；调整结束。参考资料数据结构与算法之美
什么是字典树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 树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 文件就不会无限增长了。系统崩溃重启，我们只需要从磁盘中读取检查点，就能知道最后一次成功处理的数据在 log 文件中的位置。接下来，我们就可以把这个位置之后未被处理的数据，从 log 文件中读出，然后重新加载到内存中。参考资料检索技术核心 20 讲
什么是 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+树的应用场景参考资料数据结构与算法之美
什么是堆？堆（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 类
树什么是树在计算机科学中，树（英语：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 的位置），这样就可以通过下标计算，把整棵树都串起来。如果是非完全二叉树，其实会浪费比较多的数组存储空间。所以，如果某棵二叉树是一棵完全二叉树，那用数组存储无疑是最节省内存的一种方式。因为数组的存储方式并不需要像链式存储法那样，要存储额外的左右子节点的指针。这也是 为什么完全二叉树要求最后一层的子节点都靠左的原因。二叉树的遍历二叉树的遍历有三种方式：前序遍历：对于树中的任意节点来说，先打印这个节点，然后再打印它的左子树，最后打印它的右子树。中序遍历：对于树中的任意节点来说，先打印它的左子树，然后再打印它本身，最后打印它的右子树。后序遍历是指，对于树中的任意节点来说，先打印它的左子树，然后再打印它的右子树，最后打印这个节点本身。二叉查找树二叉查找树是二叉树中最常用的一种类型，也叫二叉搜索树。顾名思义，二叉查找树是为了实现快速查找而生的。不过，它不仅仅支持快速查找一个数据，还支持快速插入、删除一个数据。二叉查找树要求，在树中的任意一个节点，其左子树中的每个节点的值，都要小于这个节点的值，而右子树节点的值都大于这个节点的值。二叉查找树的查找首先，我们看如何在二叉查找树中查找一个节点。我们先取根节点，如果它等于我们要查找的数据，那就返回。如果要查找的数据比根节点的值小，那就在左子树中递归查找；如果要查找的数据比根节点的值大，那就在右子树中递归查找。二叉查找树的插入如果要插入的数据比节点的数据大，并且节点的右子树为空，就将新数据直接插到右子节点的位置；如果不为空，就再递归遍历右子树，查找插入位置。同理，如果要插入的数据比节点数值小，并且节点的左子树为空，就将新数据插入到左子节点的位置；如果不为空，就再递归遍历左子树，查找插入位置。二叉查找树的删除第一种情况是，如果要删除的节点没有子节点，我们只需要直接将父节点中，指向要删除节点的指针置为 null。第二种情况是，如果要删除的节点只有一个子节点（只有左子节点或者右子节点），我们只需要更新父节点中，指向要删除节点的指针，让它指向要删除节点的子节点就可以了。第三种情况是，如果要删除的节点有两个子节点，这就比较复杂了。我们需要找到这个节点的右子树中的最小节点，把它替换到要删除的节点上。然后再删除掉这个最小节点，因为最小节点肯定没有左子节点（如果有左子结点，那就不是最小节点了），所以，我们可以应用上面两条规则来删除这个最小节点。二叉查找树的时间复杂度不管操作是插入、删除还是查找，时间复杂度其实都跟树的高度成正比，也就是 O(log n)。二叉查找树的形态各式各样。比如这个图中，对于同一组数据，我们构造了三种二叉查找树。它们的查找、插入、删除操作的执行效率都是不一样的。图中第一种二叉查找树，根节点的左右子树极度不平衡，已经退化成了链表，所以查找的时间复杂度就变成了 O(n)。为什么需要二叉查找树第一，哈希表中的数据是无序存储的，如果要输出有序的数据，需要先进行排序。而对于二叉查找树来说，我们只需要中序遍历，就可以在 O(n) 的时间复杂度内，输出有序的数据序列。第二，哈希表扩容耗时很多，而且当遇到散列冲突时，性能不稳定，尽管二叉查找树的性能不稳定，但是在工程中，我们最常用的平衡二叉查找树的性能非常稳定，时间复杂度稳定在 O(logn)。第三，笼统地来说，尽管哈希表的查找等操作的时间复杂度是常量级的，但因为哈希冲突的存在，这个常量不一定比 logn 小，所以实际的查找速度可能不一定比 O(logn) 快。加上哈希函数的耗时，也不一定就比平衡二叉查找树的效率高。第四，哈希表的构造比二叉查找树要复杂，需要考虑的东西很多。比如散列函数的设计、冲突解决办法、扩容、缩容等。平衡二叉查找树只需要考虑平衡性这一个问题，而且这个问题的解决方案比较成熟、固定。最后，为了避免过多的散列冲突，哈希表装载因子不能太大，特别是基于开放寻址法解决冲突的哈希表，不然会浪费一定的存储空间。参考资料数据结构与算法之美
冒泡排序要点冒泡排序是一种交换排序。什么是交换排序呢？交换排序：两两比较待排序的关键字，并交换不满足次序要求的那对数，直到整个表都满足次序要求为止。算法思想它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端，故名。假设有一个大小为 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--) { // 比较相邻的元素，如果前面的数大于后面的数，则交换 if (list[j - 1] > list[j]) { temp = list[j - 1]; list[j - 1] = list[j]; list[j] = temp; bChange = true; } } // 如果标志为false，说明本轮遍历没有交换，已经是有序数列，可以结束排序 if (false == bChange) break; System.out.format("第 %d 趟：\t", i); printAll(list); } }快速排序要点快速排序是一种交换排序。快速排序由 C. A. R. Hoare 在 1962 年提出。算法思想它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分：分割点左边都是比它小的数，右边都是比它大的数。然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。详细的图解往往比大堆的文字更有说明力，所以直接上图：上图中，演示了快速排序的处理过程：初始状态为一组无序的数组：2、4、5、1、3。经过以上操作步骤后，完成了第一次的排序，得到新的数组：1、2、5、4、3。新的数组中，以 2 为分割点，左边都是比 2 小的数，右边都是比 2 大的数。因为 2 已经在数组中找到了合适的位置，所以不用再动。2 左边的数组只有一个元素 1，所以显然不用再排序，位置也被确定。（注：这种情况时，left 指针和 right 指针显然是重合的。因此在代码中，我们可以通过设置判定条件 left 必须小于 right，如果不满足，则不用排序了）。而对于 2 右边的数组 5、4、3，设置 left 指向 5，right 指向 3，开始继续重复图中的一、二、三、四步骤，对新的数组进行排序。核心代码public int division(int[] list, int left, int right) { // 以最左边的数(left)为基准 int base = list[left]; while (left < right) { // 从序列右端开始，向左遍历，直到找到小于base的数 while (left < right && list[right] >= base) right--; // 找到了比base小的元素，将这个元素放到最左边的位置 list[left] = list[right]; // 从序列左端开始，向右遍历，直到找到大于base的数 while (left < right && list[left] <= base) left++; // 找到了比base大的元素，将这个元素放到最右边的位置 list[right] = list[left]; } // 最后将base放到left位置。此时，left位置的左侧数值应该都比left小； // 而left位置的右侧数值应该都比left大。 list[left] = base; return left; } private void quickSort(int[] list, int left, int right) { // 左下标一定小于右下标，否则就越界了 if (left < right) { // 对数组进行分割，取出下次分割的基准标号 int base = division(list, left, right); System.out.format("base = %d:\t", list[base]); printPart(list, left, right); // 对“基准标号“左侧的一组数值进行递归的切割，以至于将这些数值完整的排序 quickSort(list, left, base - 1); // 对“基准标号“右侧的一组数值进行递归的切割，以至于将这些数值完整的排序 quickSort(list, base + 1, right); } }算法分析快速排序算法的性能参数结果排序类别交换排序排序方法快速排序时间复杂度平均情况O(Nlog2N)时间复杂度最坏情况O(N2)时间复杂度最好情况O(Nlog2N)空间复杂度O(Nlog2N)稳定性不稳定复杂性较复杂时间复杂度当数据有序时，以第一个关键字为基准分为两个子序列，前一个子序列为空，此时执行效率最差。而当数据随机分布时，以第一个关键字为基准分为两个子序列，两个子序列的元素个数接近相等，此时执行效率最好。所以，数据越随机分布时，快速排序性能越好；数据越接近有序，快速排序性能越差。空间复杂度快速排序在每次分割的过程中，需要 1 个空间存储基准值。而快速排序的大概需要 Nlog2N 次的分割处理，所以占用空间也是 Nlog2N 个。算法稳定性在快速排序中，相等元素可能会因为分区而交换顺序，所以它是不稳定的算法。插入排序要点直接插入排序是一种最简单的插入排序。插入排序：每一趟将一个待排序的记录，按照其关键字的大小插入到有序队列的合适位置里，知道全部插入完成。算法思想在讲解直接插入排序之前，先让我们脑补一下我们打牌的过程。先拿一张 5 在手里，再摸到一张 4，比 5 小，插到 5 前面，摸到一张 6，嗯，比 5 大，插到 5 后面，摸到一张 8，比 6 大，插到 6 后面，。。。最后一看，我靠，凑到的居然是同花顺，这下牛逼大了。以上的过程，其实就是典型的直接插入排序，每次将一个新数据插入到有序队列中的合适位置里。很简单吧，接下来，我们要将这个算法转化为编程语言。假设有一组无序序列 R0, R1, ... , RN-1。我们先将这个序列中下标为 0 的元素视为元素个数为 1 的有序序列。然后，我们要依次把 R1, R2, ... , RN-1 插入到这个有序序列中。所以，我们需要一个外部循环，从下标 1 扫描到 N-1 。接下来描述插入过程。假设这是要将 Ri 插入到前面有序的序列中。由前面所述，我们可知，插入 Ri 时，前 i-1 个数肯定已经是有序了。所以我们需要将 Ri 和 R0 \~ Ri-1 进行比较，确定要插入的合适位置。这就需要一个内部循环，我们一般是从后往前比较，即从下标 i-1 开始向 0 进行扫描。核心代码public void insertSort(int[] list) { // 打印第一个元素 System.out.format("i = %d:\t", 0); printPart(list, 0, 0); // 第1个数肯定是有序的，从第2个数开始遍历，依次插入有序序列 for (int i = 1; i < list.length; i++) { int j = 0; int temp = list[i]; // 取出第i个数，和前i-1个数比较后，插入合适位置 // 因为前i-1个数都是从小到大的有序序列，所以只要当前比较的数(list[j])比temp大，就把这个数后移一位 for (j = i - 1; j >= 0 && temp < list[j]; j--) { list[j + 1] = list[j]; } list[j + 1] = temp; System.out.format("i = %d:\t", i); printPart(list, 0, i); } }算法分析直接插入排序的算法性能参数结果排序类别插入排序排序方法直接插入排序时间复杂度平均情况O(N2)时间复杂度最坏情况O(N2)时间复杂度最好情况O(N)空间复杂度O(1)稳定性稳定复杂性简单时间复杂度当数据正序时，执行效率最好，每次插入都不用移动前面的元素，时间复杂度为 O(N)。当数据反序时，执行效率最差，每次插入都要前面的元素后移，时间复杂度为 O(N2)。所以，数据越接近正序，直接插入排序的算法性能越好。空间复杂度由直接插入排序算法可知，我们在排序过程中，需要一个临时变量存储要插入的值，所以空间复杂度为 1 。算法稳定性直接插入排序的过程中，不需要改变相等数值元素的位置，所以它是稳定的算法。希尔排序要点希尔(Shell)排序又称为缩小增量排序，它是一种插入排序。它是直接插入排序算法的一种威力加强版。该方法因 DL．Shell 于 1959 年提出而得名。算法思想希尔排序的基本思想是：把记录按步长 gap 分组，对每组记录采用直接插入排序方法进行排序。随着步长逐渐减小，所分成的组包含的记录越来越多，当步长的值减小到 1 时，整个数据合成为一组，构成一组有序记录，则完成排序。我们来通过演示图，更深入的理解一下这个过程。在上面这幅图中：初始时，有一个大小为 10 的无序序列。在第一趟排序中，我们不妨设 gap1 = N / 2 = 5，即相隔距离为 5 的元素组成一组，可以分为 5 组。接下来，按照直接插入排序的方法对每个组进行排序。在 第二趟排序中，我们把上次的 gap 缩小一半，即 gap2 = gap1 / 2 = 2 (取整数)。这样每相隔距离为 2 的元素组成一组，可以分为 2 组。按照直接插入排序的方法对每个组进行排序。在第三趟排序中，再次把 gap 缩小一半，即 gap3 = gap2 / 2 = 1。 这样相隔距离为 1 的元素组成一组，即只有一组。按照直接插入排序的方法对每个组进行排序。此时，排序已经结束。需要注意一下的是，图中有两个相等数值的元素 5 和 5 。我们可以清楚的看到，在排序过程中，两个元素位置交换了。所以，希尔排序是不稳定的算法。核心代码public void shellSort(int[] list) { int gap = list.length / 2; while (1 <= gap) { // 把距离为 gap 的元素编为一个组，扫描所有组 for (int i = gap; i < list.length; i++) { int j = 0; int temp = list[i]; // 对距离为 gap 的元素组进行排序 for (j = i - gap; j >= 0 && temp < list[j]; j = j - gap) { list[j + gap] = list[j]; } list[j + gap] = temp; } System.out.format("gap = %d:\t", gap); printAll(list); gap = gap / 2; // 减小增量 } }算法分析希尔排序的算法性能参数结果排序类别插入排序排序方法希尔排序时间复杂度平均情况O(Nlog2N)时间复杂度最坏情况O(N1.5)时间复杂度最好情况 空间复杂度O(1)稳定性不稳定复杂性较复杂时间复杂度步长的选择是希尔排序的重要部分。只要最终步长为 1 任何步长序列都可以工作。算法最开始以一定的步长进行排序。然后会继续以一定步长进行排序，最终算法以步长为 1 进行排序。当步长为 1 时，算法变为插入排序，这就保证了数据一定会被排序。Donald Shell 最初建议步长选择为 N/2 并且对步长取半直到步长达到 1。虽然这样取可以比 O(N2)类的算法（插入排序）更好，但这样仍然有减少平均时间和最差时间的余地。可能希尔排序最重要的地方在于当用较小步长排序后，以前用的较大步长仍然是有序的。比如，如果一个数列以步长 5 进行了排序然后再以步长 3 进行排序，那么该数列不仅是以步长 3 有序，而且是以步长 5 有序。如果不是这样，那么算法在迭代过程中会打乱以前的顺序，那就不会以如此短的时间完成排序了。已知的最好步长序列是由 Sedgewick 提出的(1, 5, 19, 41, 109,...)，该序列的项来自这两个算式。这项研究也表明“比较在希尔排序中是最主要的操作，而不是交换。”用这样步长序列的希尔排序比插入排序和堆排序都要快，甚至在小数组中比快速排序还快，但是在涉及大量数据时希尔排序还是比快速排序慢。算法稳定性由上文的希尔排序算法演示图即可知，希尔排序中相等数据可能会交换位置，所以希尔排序是不稳定的算法。直接插入排序和希尔排序的比较直接插入排序是稳定的；而希尔排序是不稳定的。直接插入排序更适合于原始记录基本有序的集合。希尔排序的比较次数和移动次数都要比直接插入排序少，当 N 越大时，效果越明显。在希尔排序中，增量序列 gap 的取法必须满足：最后一个步长必须是 1 。 直接插入排序也适用于链式存储结构；希尔排序不适用于链式结构。简单选择排序要点简单选择排序是一种选择排序。选择排序：每趟从待排序的记录中选出关键字最小的记录，顺序放在已排序的记录序列末尾，直到全部排序结束为止。算法思想从待排序序列中，找到关键字最小的元素；如果最小元素不是待排序序列的第一个元素，将其和第一个元素互换；从余下的 N - 1 个元素中，找出关键字最小的元素，重复 1、2 步，直到排序结束。如图所示，每趟排序中，将当前第 i 小的元素放在位置 i 上。核心代码算法分析简单选择排序算法的性能参数结果排序类别选择排序排序方法简单选择排序时间复杂度平均情况O(N2)时间复杂度最坏情况O(N2)时间复杂度最好情况O(N2)空间复杂度O(1)稳定性不稳定复杂性简单时间复杂度简单选择排序的比较次数与序列的初始排序无关。 假设待排序的序列有 N 个元素，则比较次数总是 N (N - 1) / 2 。而移动次数与序列的初始排序有关。当序列正序时，移动次数最少，为 0.当序列反序时，移动次数最多，为 3N (N - 1) / 2。所以，综合以上，简单排序的时间复杂度为 O(N2)。空间复杂度简单选择排序需要占用一个临时空间，在交换数值时使用。堆排序要点在介绍堆排序之前，首先需要说明一下，堆是个什么玩意儿。堆是一棵顺序存储的完全二叉树。其中每个结点的关键字都不大于其孩子结点的关键字，这样的堆称为小根堆。其中每个结点的关键字都不小于其孩子结点的关键字，这样的堆称为大根堆。举例来说，对于 n 个元素的序列 {R0, R1, ... , Rn} 当且仅当满足下列关系之一时，称之为堆：Ri <= R2i+1 且 Ri <= R2i+2 （小根堆）Ri >= R2i+1 且 Ri >= R2i+2 （大根堆）其中 i=1,2,…,n/2 向下取整;如上图所示，序列 R{3, 8,15, 31, 25} 是一个典型的小根堆。堆中有两个父结点，元素 3 和元素 8。元素 3 在数组中以 R[0] 表示，它的左孩子结点是 R[1]，右孩子结点是 R[2]。元素 8 在数组中以 R[1] 表示，它的左孩子结点是 R[3]，右孩子结点是 R[4]，它的父结点是 R[0]。可以看出，它们满足以下规律：设当前元素在数组中以 R[i] 表示，那么，它的左孩子结点是：R[2*i+1];它的右孩子结点是：R[2*i+2];它的父结点是：R[(i-1)/2];R[i] <= R[2*i+1] 且 R[i] <= R[2i+2]。算法思想首先，按堆的定义将数组 R[0..n]调整为堆（这个过程称为创建初始堆），交换 R[0]和 R[n]；然后，将 R[0..n-1]调整为堆，交换 R[0]和 R[n-1]；如此反复，直到交换了 R[0]和 R[1]为止。以上思想可归纳为两个操作：根据初始数组去构造初始堆（构建一个完全二叉树，保证所有的父结点都比它的孩子结点数值大）。每次交换第一个和最后一个元素，输出最后一个元素（最大值），然后把剩下元素重新调整为大根堆。当输出完最后一个元素后，这个数组已经是按照从小到大的顺序排列了。先通过详细的实例图来看一下，如何构建初始堆。设有一个无序序列 { 1, 3,4, 5, 2, 6, 9, 7, 8, 0 }。构造了初始堆后，我们来看一下完整的堆排序处理：还是针对前面提到的无序序列 { 1,3, 4, 5, 2, 6, 9, 7, 8, 0 } 来加以说明。相信，通过以上两幅图，应该能很直观的演示堆排序的操作处理。核心代码public void HeapAdjust(int[] array2, int parent, int length) { int temp = array2[parent]; // temp保存当前父节点 int child = 2 * parent + 1; // 先获得左孩子 while (child < length) { // 如果有右孩子结点，并且右孩子结点的值大于左孩子结点，则选取右孩子结点 if (child + 1 < length && array2[child] < array2[child + 1]) { child++; } // 如果父结点的值已经大于孩子结点的值，则直接结束 if (temp >= array2[child]) break; // 把孩子结点的值赋给父结点 array2[parent] = array2[child]; // 选取孩子结点的左孩子结点,继续向下筛选 parent = child; child = 2 * child + 1; } array2[parent] = temp; } public void heapSort(int[] list) { // 循环建立初始堆 for (int i = list.length / 2; i >= 0; i--) { HeapAdjust(list, i, list.length); } // 进行n-1次循环，完成排序 for (int i = list.length - 1; i > 0; i--) { // 最后一个元素和第一元素进行交换 int temp = list[i]; list[i] = list[0]; list[0] = temp; // 筛选 R[0] 结点，得到i-1个结点的堆 HeapAdjust(list, 0, i); System.out.format("第 %d 趟: \t", list.length - i); printPart(list, 0, list.length - 1); } }算法分析堆排序算法的总体情况参数结果排序类别选择排序排序方法堆排序时间复杂度平均情况O(nlog2n)时间复杂度最坏情况O(nlog2n)时间复杂度最好情况O(nlog2n)空间复杂度O(1)稳定性不稳定复杂性较复杂时间复杂度堆的存储表示是顺序的。因为堆所对应的二叉树为完全二叉树，而完全二叉树通常采用顺序存储方式。当想得到一个序列中第 k 个最小的元素之前的部分排序序列，最好采用堆排序。因为堆排序的时间复杂度是 O(n+klog2n)，若 k ≤ n/log2n，则可得到的时间复杂度为 O(n)。算法稳定性堆排序是一种不稳定的排序方法。因为在堆的调整过程中，关键字进行比较和交换所走的是该结点到叶子结点的一条路径，因此对于相同的关键字就可能出现排在后面的关键字被交换到前面来的情况。归并排序要点归并排序是建立在归并操作上的一种有效的排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。算法思想将待排序序列 R[0...n-1] 看成是 n 个长度为 1 的有序序列，将相邻的有序表成对归并，得到 n/2 个长度为 2 的有序表；将这些有序序列再次归并，得到 n/4 个长度为 4 的有序序列；如此反复进行下去，最后得到一个长度为 n 的有序序列。综上可知：归并排序其实要做两件事：“分解”——将序列每次折半划分。“合并”——将划分后的序列段两两合并后排序。我们先来考虑第二步，如何合并？在每次合并过程中，都是对两个有序的序列段进行合并，然后排序。这两个有序序列段分别为 R[low, mid] 和 R[mid+1, high]。先将他们合并到一个局部的暂存数组R2 中，带合并完成后再将 R2 复制回 R 中。为了方便描述，我们称 R[low, mid] 第一段，R[mid+1, high] 为第二段。每次从两个段中取出一个记录进行关键字的比较，将较小者放入 R2 中。最后将各段中余下的部分直接复制到 R2 中。经过这样的过程，R2 已经是一个有序的序列，再将其复制回 R 中，一次合并排序就完成了。核心代码public void Merge(int[] array2, int low, int mid, int high) { int i = low; // i是第一段序列的下标 int j = mid + 1; // j是第二段序列的下标 int k = 0; // k是临时存放合并序列的下标 int[] array2 = new int[high - low + 1]; // array2是临时合并序列 // 扫描第一段和第二段序列，直到有一个扫描结束 while (i <= mid && j <= high) { // 判断第一段和第二段取出的数哪个更小，将其存入合并序列，并继续向下扫描 if (array2[i] <= array2[j]) { array2[k] = array2[i]; i++; k++; } else { array2[k] = array2[j]; j++; k++; } } // 若第一段序列还没扫描完，将其全部复制到合并序列 while (i <= mid) { array2[k] = array2[i]; i++; k++; } // 若第二段序列还没扫描完，将其全部复制到合并序列 while (j <= high) { array2[k] = array2[j]; j++; k++; } // 将合并序列复制到原始序列中 for (k = 0, i = low; i <= high; i++, k++) { array2[i] = array2[k]; } }掌握了合并的方法，接下来，让我们来了解如何分解。在某趟归并中，设各子表的长度为 gap，则归并前 R[0...n-1] 中共有 n/gap 个有序的子表：R[0...gap-1], R[gap...2*gap-1], ... , R[(n/gap)*gap ... n-1]。调用 Merge 将相邻的子表归并时，必须对表的特殊情况进行特殊处理。若子表个数为奇数，则最后一个子表无须和其他子表归并（即本趟处理轮空）：若子表个数为偶数，则要注意到最后一对子表中后一个子表区间的上限为 n-1。核心代码public void MergePass(int[] array2, int gap, int length) { int i = 0; // 归并gap长度的两个相邻子表 for (i = 0; i + 2 * gap - 1 < length; i = i + 2 * gap) { Merge(array2, i, i + gap - 1, i + 2 * gap - 1); } // 余下两个子表，后者长度小于gap if (i + gap - 1 < length) { Merge(array2, i, i + gap - 1, length - 1); } } public int[] sort(int[] list) { for (int gap = 1; gap < list.length; gap = 2 * gap) { MergePass(list, gap, list.length); System.out.print("gap = " + gap + ":\t"); this.printAll(list); } return list; }算法分析归并排序算法的性能参数结果排序类别归并排序排序方法归并排序时间复杂度平均情况O(nlog2n)时间复杂度最坏情况O(nlog2n)时间复杂度最好情况O(nlog2n)空间复杂度O(n)稳定性稳定复杂性较复杂时间复杂度归并排序的形式就是一棵二叉树，它需要遍历的次数就是二叉树的深度，而根据完全二叉树的可以得出它的时间复杂度是 O(n*log2n)。空间复杂度由前面的算法说明可知，算法处理过程中，需要一个大小为 n 的临时存储空间用以保存合并序列。算法稳定性在归并排序中，相等的元素的顺序不会改变，所以它是稳定的算法。归并排序和堆排序、快速排序的比较若从空间复杂度来考虑：首选堆排序，其次是快速排序，最后是归并排序。若从稳定性来考虑，应选取归并排序，因为堆排序和快速排序都是不稳定的。若从平均情况下的排序速度考虑，应该选择快速排序。基数排序要点基数排序与本系列前面讲解的七种排序方法都不同，它不需要比较关键字的大小。它是根据关键字中各位的值，通过对排序的 N 个元素进行若干趟“分配”与“收集”来实现排序的。不妨通过一个具体的实例来展示一下，基数排序是如何进行的。设有一个初始序列为: R {50, 123, 543, 187, 49, 30,0, 2, 11, 100}。我们知道，任何一个阿拉伯数，它的各个位数上的基数都是以 0\~9 来表示的。所以我们不妨把 0\~9 视为 10 个桶。我们先根据序列的个位数的数字来进行分类，将其分到指定的桶中。例如：R[0] = 50，个位数上是 0，将这个数存入编号为 0 的桶中。分类后，我们在从各个桶中，将这些数按照从编号 0 到编号 9 的顺序依次将所有数取出来。这时，得到的序列就是个位数上呈递增趋势的序列。按照个位数排序： {50, 30, 0, 100, 11, 2, 123,543, 187, 49}。接下来，可以对十位数、百位数也按照这种方法进行排序，最后就能得到排序完成的序列。算法分析基数排序的性能参数结果排序类别基数排序排序方法基数排序时间复杂度平均情况O(d(n+r))时间复杂度最坏情况O(d(n+r))时间复杂度最好情况O(d(n+r))空间复杂度O(n+r)稳定性稳定复杂性较复杂时间复杂度通过上文可知，假设在基数排序中，r 为基数，d 为位数。则基数排序的时间复杂度为 O(d(n+r))。我们可以看出，基数排序的效率和初始序列是否有序没有关联。空间复杂度在基数排序过程中，对于任何位数上的基数进行“装桶”操作时，都需要 n+r 个临时空间。算法稳定性在基数排序过程中，每次都是将当前位数上相同数值的元素统一“装桶”，并不需要交换位置。所以基数排序是稳定的算法。
查找简介什么是查找？查找是根据给定的某个值，在表中确定一个关键字的值等于给定值的记录或数据元素。查找算法的分类若在查找的同时对表记录做修改操作（如插入和删除），则相应的表称之为动态查找表；否则，称之为静态查找表。此外，如果查找的全过程都在内存中进行，称之为内查找；反之，如果查找过程中需要访问外存，称之为外查找。查找算法性能比较的标准——平均查找长度 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 是分块有序的，所以索引表是一个递增有序表。下图就是一个分块查找表的存储结构示意图基本思想分块查找算法有两个处理步骤：(1) 首先查找索引表因为分块查找表是“分块有序”的，所以我们可以通过索引表来锁定关键字所在的区间。又因为索引表是递增有序的，所以查找索引可以使用顺序查找或二分查找。(2) 然后在已确定的块中进行顺序查找因为块中不一定是有序的，所以只能使用顺序查找。代码范例class BlockSearch { class IndexType { public int key; // 分块中的最大值 public int link; // 分块的起始位置 } // 建立索引方法，n 是线性表最大长度，gap是分块的最大长度 public IndexType[] createIndex(int[] list, int n, int gap) { int i = 0, j = 0, max = 0; int num = n / gap; IndexType[] idxGroup = new IndexType[num]; // 根据步长数分配索引数组大小 while (i < num) { j = 0; idxGroup[i] = new IndexType(); idxGroup[i].link = gap * i; // 确定当前索引组的第一个元素位置 max = list[gap * i]; // 每次假设当前组的第一个数为最大值 // 遍历这个分块，找到最大值 while (j < gap) { if (max < list[gap * i + j]) { max = list[gap * i + j]; } j++; } idxGroup[i].key = max; i++; } return idxGroup; } // 分块查找算法 public int blockSearch(IndexType[] idxGroup, int m, int[] list, int n, int key) { int mid = 0; int low = 0; int high = m -1; int gap = n / m; // 分块大小等于线性表长度除以组数 // 先在索引表中进行二分查找，找到的位置存放在 low 中 while (low <= high) { mid = (low + high) / 2; if (idxGroup[mid].key >= key) { high = mid - 1; } else { low = mid + 1; } } // 在索引表中查找成功后，再在线性表的指定块中进行顺序查找 if (low < m) { for (int i = idxGroup[low].link; i < idxGroup[low].link + gap; i++) { if (list[i] == key) return i; } } return -1; } // 打印完整序列 public void printAll(int[] list) { for (int value : list) { System.out.print(value + " "); } System.out.println(); } // 打印索引表 public void printIDX(IndexType[] list) { System.out.println("构造索引表如下："); for (IndexType elem : list) { System.out.format("key = %d, link = %d\n", elem.key, elem.link); } System.out.println(); } public static void main(String[] args) { int key = 85; int array2[] = { 8, 14, 6, 9, 10, 22, 34, 18, 19, 31, 40, 38, 54, 66, 46, 71, 78, 68, 80, 85 }; BlockSearch search = new BlockSearch(); System.out.print("线性表: "); search.printAll(array2); IndexType[] idxGroup = search.createIndex(array2, array2.length, 5); search.printIDX(idxGroup); int pos = search.blockSearch(idxGroup, idxGroup.length, array2, array2.length, key); if (-1 == pos) { System.out.format("查找key = %d失败", key); } else { System.out.format("查找key = %d成功，位置为%d", key, pos); } } }运行结果线性表: 8 14 6 9 10 22 34 18 19 31 40 38 54 66 46 71 78 68 80 85 构造索引表如下： key = 14, link = 0 key = 34, link = 5 key = 66, link = 10 key = 85, link = 15 查找key = 85成功，位置为19算法分析因为分块查找实际上是两次查找过程之和。若以二分查找来确定块，显然它的查找效率介于顺序查找和二分查找之间。三种线性查找的 PK(1) 以平均查找长度而言，二分查找 > 分块查找 > 顺序查找。(2) 从适用性而言，顺序查找无限制条件，二分查找仅适用于有序表，分块查找要求“分块有序”。(3) 从存储结构而言，顺序查找和分块查找既可用于顺序表也可用于链表；而二分查找只适用于顺序表。(4) 分块查找综合了顺序查找和二分查找的优点，既可以较为快速，也能使用动态变化的要求。参考资料
队列和栈都是操作受限的线性表：前者先进先出，后者先进后出。栈栈是什么在 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：栈和队列
数组和链表分别代表了连续空间和不连续空间的存储方式，它们是线性表（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 字段可以很容易地在常量时间内获得前一个结点。因为我们不再需要遍历链表来获取前一个结点，所以时间和空间复杂度都是 O(1)。循环链表循环单链表循环单链表是一种特殊的单链表。它和单链表唯一的区别就在最后结点。单链表的最后一个结点的后继指针 next 指向空地址。循环链表的最后一个结点的后继指针 next 指向第一个节点（如果有头节点，就指向头节点）。循环双链表数组 vs. 链表存储方式数组用 连续 的内存空间来存储数据。链表用 不连续 的内存空间来存储数据；并通过一个指针按顺序将这些空间串起来，形成一条链。访问方式数组支持随机访问。根据下标随机访问的时间复杂度为 O(1)链表不支持随机访问，只能顺序访问，时间复杂度为 O(n)。空间大小数组空间大小固定，扩容只能采用复制数组的方式。链表空间大小不固定，扩容灵活。效率比较数组的 查找 效率高于链表。链表的 添加、删除 效率高于数组。数组和链表的基本操作示例关于数组和链表的基本操作，网上和各种书籍、教程中已经有大量的示例，感兴趣可以自行搜索。本文只是简单展示一下数组和链表的基本操作。一维数组的基本操作public class Main { public static void main(String[] args) { // 1. Initialize int[] a0 = new int[5]; int[] a1 = {1, 2, 3}; // 2. Get Length System.out.println("The size of a1 is: " + a1.length); // 3. Access Element System.out.println("The first element is: " + a1[0]); // 4. Iterate all Elements System.out.print("[Version 1] The contents of a1 are:"); for (int i = 0; i < a1.length; ++i) { System.out.print(" " + a1[i]); } System.out.println(); System.out.print("[Version 2] The contents of a1 are:"); for (int item: a1) { System.out.print(" " + item); } System.out.println(); // 5. Modify Element a1[0] = 4; // 6. Sort Arrays.sort(a1); } }二维数组的基本操作public class TwoDimensionArray { private static void printArray(int[][] a) { for (int i = 0; i < a.length; ++i) { System.out.println(a[i]); } for (int i = 0; i < a.length; ++i) { for (int j = 0; a[i] != null && j < a[i].length; ++j) { System.out.print(a[i][j] + " "); } System.out.println(); } } public static void main(String[] args) { System.out.println("Example I:"); int[][] a = new int[2][5]; printArray(a); System.out.println("Example II:"); int[][] b = new int[2][]; printArray(b); System.out.println("Example III:"); b[0] = new int[3]; b[1] = new int[5]; printArray(b); } }单链表的基本操作单链表节点的数据结构public class ListNode<E> { E value; ListNode<E> next; // 指向后继节点 } public class SingleLinkList<E> { private ListNode<E> head; // 头节点 }（1）从头部添加节点（即头插法）void addHead(E value) { ListNode<E> newNode = new ListNode<>(value, null); newNode.next = this.head.next; this.head.next = newNode; }（2）从尾部添加节点（即尾插法）void addTail(E value) { // init new node ListNode<E> newNode = new ListNode<>(value, null); // find the last node ListNode<E> node = this.head; while (node.next != null) { node = node.next; } // add new node to tail node.next = newNode; }（3）删除节点找到要删除元素的前驱节点，将前驱节点的 next 指针指向下一个节点。public void remove(E value) { ListNode<E> prev = this.head; while (prev.next != null) { ListNode<E> curr = prev.next; if (curr.value.equals(value)) { prev.next = curr.next; break; } prev = prev.next; } }（4）查找节点从头开始查找，一旦发现有数值与查找值相等的节点，直接返回此节点。如果遍历结束，表明未找到节点，返回 null。public ListNode<E> find(E value) { ListNode<E> node = this.head.next; while (node != null) { if (node.value.equals(value)) { return node; } node = node.next; } return null; }双链表的基本操作双链表节点的数据结构：static class DListNode<E> { E value; DListNode<E> prev; // 指向前驱节点 DListNode<E> next; // 指向后继节点 } public class DoubleLinkList<E> { /** 头节点 */ private DListNode<E> head; /** 尾节点 */ private DListNode<E> tail; }（1）从头部添加节点public void addHead(E value) { DListNode<E> newNode = new DListNode<>(null, value, null); this.head.next.prev = newNode; newNode.next = this.head.next; this.head.next = newNode; newNode.prev = this.head; }（2）从尾部添加节点public void addTail(E value) { DListNode<E> newNode = new DListNode<>(null, value, null); this.tail.prev.next = newNode; newNode.prev = this.tail.prev; this.tail.prev = newNode; newNode.next = this.tail; }（3）删除节点public void remove(E value) { DListNode<E> prev = this.head; while (prev.next != this.tail) { DListNode<E> curr = prev.next; if (curr.value.equals(value)) { prev.next = curr.next; curr.next.prev = prev; curr.next = null; curr.prev = null; break; } prev = prev.next; } }（4）查找节点public DListNode<E> find(E value) { DListNode<E> node = this.head.next; while (node != this.tail) { if (node.value.equals(value)) { return node; } node = node.next; } return null; }练习数组 724. 寻找数组的中心下标 35. 搜索插入位置 56. 合并区间链表 设计链表 环形链表 环形链表 II 相交链表 删除链表的倒数第 N 个节点 反转链表 移除链表元素 奇偶链表 回文链表 合并两个有序链表 两数相加 扁平化多级双向链表 复制带随机指针的链表 旋转链表参考资料数据结构与算法之美数据结构（C 语言版）数据结构（C++语言版）Leetcode：数组和字符串Leetcode：链表