数据结构

典型回答 B树（B- Tree）和B+树（B+ Tree）是两种常用的树结构，B是Balanced首字母，平衡的意思，他们经常用在各种数据库中，比如MySQL的InnoDB引擎使用的就是B+树，而MongoDB使用的就是B树存储。 B树属于多叉树又名平衡多路查找树，B树的设计目的是为了减少磁盘访问次数，提高查询性能。 B树是一种平衡的多叉树，通常我们说m阶的B树，它必须满足如下条件： 每个节点最多只有m个子节点。 每个非叶子节点（除了根）具有至少⌈ m/2⌉子节点。 如果根不是叶节点，则根至少有两个子节点。 具有k个子节点的非叶节点包含k -1个键。 所有叶子都出现在同一水平，没有任何信息（高度一致）。 B树具有以下特点： B树是一种多路搜索树，每个节点可以包含多个子节点。相对于二叉搜索树，B树可以存储更多的关键字和子节点，从而降低了树的高度，减少了磁盘访问次数。 B树通过在插入和删除操作时进行节点分裂和合并，保持树的平衡状态。这样可以确保树的高度始终保持在可接受的范围内，保证了较快的查询性能。 B树的节点中的关键字按照升序排列，使得范围查询操作更加高效。通过遍历树中的叶子节点，可以顺序获取连续的数据。 B树的关键字和数据项可以存储在叶子节点和非叶子节点上。并且每个关键字出现且只出现在一个节点中。 B树的搜索可能在非叶子节点上结束，他的搜索性能相当于在关键字全集中做二分查找。 B+树是B-树的变体，也是一种多路搜索树, 它与 B- 树的不同之处在于以下2个方面 数据存储位置：在B树中，数据项存储在叶子节点和非叶子节点上，而在B+树中，数据项只存储在叶子节点上。非叶子节点只包含键值信息。 叶子节点指针：B树的叶子节点之间没有指针连接，每个叶子节点独立存储数据项。而B+树的叶子节点通过指针连接成一个链表，可以方便地进行范围查询。 由于B+树的叶子节点之间通过双向指针链接进而形成了链表，所以B+树在范围查询时更加高效。通过遍历叶子节点链表，可以获取连续的数据项，而不需要回溯到非叶子节点。

典型回答 位图（BitMap），基本思想就是用一个bit来标记元素，bit是计算机中最小的单位，也就是我们常说的计算机中的0和1，这种就是用一个位来表示的。 所谓位图，其实就是一个bit数组，即每一个位置都是一个bit，其中的取值可以是0或者1 像上面的这个位图，可以用来表示1，,4，6： 如果不用位图的话，我们想要记录1，4，,6 这三个整型的话，就需要用三个unsigned int，已知每个unsigned int占4个字节，那么就是34 = 12个字节，一个字节有8 bit，那么就是 128 = 96 个bit。 所以，位图最大的好处就是节省空间。 位图有很多种用途，特别适合用在去重、排序等场景中，著名的布隆过滤器就是基于位图实现的。 ✅什么是布隆过滤器，实现原理是什么？ 但是位图也有着一定的限制，那就是他只能表示0和1，无法存储其他的数字。所以他只适合这种能表示true or false的场景。 知识扩展 什么是BitSet ✅Set是如何保证元素不重复的

典型回答 前缀树（Trie，又称字典树或键树）是一种树形结构，它是一种用于快速检索字符串集合中字符串的高效数据结构。前缀树的每个节点代表一个字符串（或字符串的一部分），从根节点到某一节点的路径上经过的字符连接起来，就是该节点对应的字符串。 前缀树的特点： 根节点不包含字符，除根节点外的每个节点都只包含一个字符。 从根节点到某一节点的路径上经过的字符连接起来，为该节点对应的字符串。 每个节点的所有子节点包含的字符都不相同。 举个例子：有以下字符串： abc,bac,bbc,ca， 通过字典树形成的结构如下所示： 从上图我们可以看出，通过字典树，在查询的时候，原来的时间复杂度是O(n*m)，优化后的时间复杂度就会变成O(m)。同时，如果有很多字符串，字典树还可以大大减少存储的空间。 字典树的java实现如下所示： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 class Trie { private Trie[] children; private boolean isWord; public Trie() { this.isWord = false; this.children = new Trie[26]; } public void insert(String word) { Trie next = this; for(char c : word.toCharArray()) { if(next.children[c - 'a'] == null) { next.children[c - 'a'] = new Trie(); } next = next.children[c - 'a']; } next.isWord = true; } public boolean search(String word) { Trie next = this; for(char c : word.toCharArray()) { if(next.children[c - 'a'] == null) { return false; } next = next.children[c - 'a']; } return next.isWord; } public boolean startsWith(String prefix) { Trie next = this; for(char c : prefix.toCharArray()) { if(next.children[c - 'a'] == null) { return false; } next = next.children[c - 'a']; } return true; } } 知识扩展 前缀树有哪些应用？ 字符串检索 给出N 个单词组成的熟词表，以及一篇全用小写英文书写的文章，请你按最早出现的顺序写出所有不在熟词表中的生词。 ...

典型回答 图是一种复杂的数据结构，用于有效地表示和处理由一组元素（称为顶点或节点）及其相互关联的信息（称为边）组成的集合。它表明了物件与物件之间的“多对多”的一种复杂关系。图数据结构非常适合用来表示任何形式的网络，例如社交网络、交通网络、通信网络等。 图可以分为两大类：有向图和无向图 无向图 在无向图中，边没有方向。如果顶点A与顶点B通过一条边相连，那么我们可以说A和B是互相连接的，这条边没有方向性，表示A到B和B到A都是可达的。无向图的边通常表示双向的或者双方等同的关系，如友谊、合作等。 有向图 与无向图不同，有向图中的边具有方向。如果顶点A指向顶点B（A→B），那么这个方向表明从A到B有一条路径，而从B到A则不一定有路径。有向图的边可以表示如权限、流程控制或一种单向关系等更复杂的关系。 扩展知识 有权图和无权图 有权图和无权图是图数据结构的两种类型，它们主要区别在于边是否具有权重。这种权重通常代表了连接两个节点之间的一种度量，如距离、时间、成本或资源使用量等。 在无权图中，边没有权重，即所有的边都被视为等同。在这种图中，两个顶点之间的连接仅表示它们之间存在一种关系，而不提供关于这种关系的任何额外信息。 在有权图中，边附带一个权重（或成本、标签），这可以用来表示从一个顶点到另一个顶点的代价或资源消耗。权重可以是任何有意义的量度，如距离、时间、费用等。 图的存储方式 图通常可以通过以下几种方式在计算机中表示和存储： 邻接矩阵：一个二维数组，其中的元素表示顶点之间是否存在边。对于有向图，矩阵不对称；对于无向图，矩阵是对称的。 邻接表：为每个顶点创建一个列表，存储与该顶点直接相连的其他顶点。这种方法在稀疏图中比邻接矩阵更节省空间。 图的遍历 图的遍历是指从图中的一个顶点开始，访问图中的所有顶点，并且保证每个顶点仅被访问一次的过程。图的遍历主要有两种基本的图遍历方式：深度优先搜索（Depth-First Search, DFS）和广度优先搜索（Breadth-First Search, BFS）。 深度优先搜索是一种沿着图的边遍历顶点，尽可能深地搜索图的分支的算法。当到达一个顶点而这个顶点没有未访问的邻接顶点时，搜索将回溯到发现该顶点的那条边的起始顶点。这一过程一直进行到已发现从原始顶点可达的所有顶点为止。 广度优先搜索是从图的一个顶点开始，访问所有可从此顶点出发通过一条边直接到达的邻接顶点，然后对每一个已访问的邻接顶点，再访问它们的邻接点，并以此类推，层层扩展直到图中所有可达的顶点都被访问。

典型回答 这里的堆是指数据结构中的堆，和操作系统内存的堆没有半毛钱关系！ 堆一般是一个完全二叉树，所谓的完全二叉树就是指除了叶子节点外，其他节点都是满二叉树，也就是其他节点都是既有左节点，又有右节点的，完全二叉树如下所示： 堆是一种特殊的完全二叉树，一般分为大顶堆（大根堆）和小顶堆（小根堆）。所谓的大根堆，就是指任意节点都大于它所有的子节点，而小根堆则恰恰相反，指的是任意节点都小于它所有的子节点。如下图是一个大根堆所示： 这样的性质有什么作用呢？当我们维护好一个堆之后，我们可以很容易的找到一个集合的最大值或者前K大的值，进一步思考，我们可以通过堆来实现优先队列，毕竟堆中每个元素都是权重的。Java中的优先队列PriorityQueue就是通过堆实现的。 同时，因为堆是可以动态构建的，在一些有动态数据且需要排序的场景下，堆的速度要比快排的速度快很多。譬如，TP99问题就可以通过堆来快速解决。 实现 堆可以用数组或者链表实现，对于数组来说，因为堆一定是一个完全二叉树，所以堆中的每个元素一定会满足以下规律： 设当前节点的 cur[index] = x, 那么 parent[index] = (x-1)/2, 左孩子 left[index] = 2*x + 1, 右孩子 right[index] = 2*x + 2 知识扩展 什么是TP99问题，如何快速计算？ 所谓的TP99，指的是在一个时间段内，统计某个接口（或方法）每次调用所消耗的时间，并将这些时间按从小到大的顺序进行排序，取第99%的那个值作为TP99值。 举个例子， 假设某个方法在5分钟内调用消耗时间的TP99为10ms，那么就说明该接口5分钟内前99%的调用时间都是10ms，看起来接口性能还不错。所以TP99一般是统计性能的一个指标。 计算TP99也需要用到堆，思路如下： 创建一个大顶堆和一个小顶堆，大顶堆的堆顶元素比小顶堆的堆顶元素更小，大顶堆维护 99% 的请求时间，小顶堆维护 1% 的请求时间 每产生一个元素（请求时间），如果它比大顶堆的堆顶元素小，则将其放入到大顶堆中，如果它比小顶堆的堆顶元素大，则将其插入到小顶堆中，插入后当然要堆化以让其符合大小顶堆的要求。 上一步在插入的过程中需要注意一下，可能会导致大顶堆和小顶堆中元素的比例不为 99:1，此时就要做相应的调整，如果在将元素插入大顶堆之后，发现比例大于 99：1，将需将大顶堆的堆顶元素移到小顶堆中，再对两个堆堆化以让其符合大小顶堆的要求，同理，如果发现比例小于99: 1，则需要将小顶堆的堆顶元素移到大顶堆来，再对两者进行堆化。 以上的大小顶堆调整后，则大顶堆的堆顶元素值就是所要求的 TP99值。 用排序也可以解决该问题，但是堆是可以实时获取TP99的，使用排序只能在时间结束后堆所有数据进行排序才可以。

典型回答 小顶堆（Min Heap）是一种特殊的二叉堆数据结构，它满足以下性质：对于堆中的任意节点i，其父节点的值小于等于节点i的值。换句话说，堆中的最小值总是位于堆的根节点上。 小顶堆是一种二叉堆数据结构，它可以使用数组来实现。 小顶堆常用于解决与最小值相关的问题，所以在实际应用中非常的广泛，比如： 1、查找最小值，在一群数字中，查找最小值，可以利用小顶堆，小顶堆的根节点就是最小值。 如：从10亿个数字中，取出最小的10个数 2、排序，小顶堆可以用于堆排序，可以把一个数组构建成小顶堆，那么就是实现了从小到大的排序。 3、定时器，在定时器的实现中，可以使用小顶堆来管理即将触发的定时事件。每个定时事件可以表示为一个包含触发时间戳的数据结构。从堆顶不断取出需要执行的定时任务即可。 4、Dijkstra算法：在最短路径问题中，Dijkstra算法使用优先级队列来选择当前最短路径的下一个节点，而小顶堆可以用作实现该优先级队列。 5、优先级队列：小顶堆可以用作优先级队列的底层数据结构，在O(log n)时间内进行插入和删除操作，O(1)时间内获取最小优先级元素。如Java 中的 PriorityQueue 6、查找最大值，有的时候，为了节省空间，也么用小顶堆实现海量数据的最大值查找。 ✅海量数据查找最大的 k 个值，用什么数据结构？ 扩展知识 插入过程 小顶堆的插入主要有两个步骤： 1、将新元素添加到小顶堆的最后一个位置（数组的末尾）。 2、执行"上浮"（Heapify Up）操作：将新插入的元素与其父节点进行比较。如果新元素的值比父节点的值小，则交换它们，并继续向上比较和交换，直到满足小顶堆的性质（即新元素的值不小于其父节点的值），或者到达堆的根节点。 加入有一个以下小顶堆，当我们插入一个元素3的时候。 将3添加到堆的最后位置： 执行上浮操作，将3上浮到正确位置： 删除过程 小顶堆的删除主要有两个步骤： 1：将堆顶元素（最小值）删除，并用堆的最后一个元素（数组的最后一个元素）来替换它。 2：执行"下沉"（Heapify Down）操作：将新的根节点与其较小的子节点进行比较。如果新根节点的值比其子节点的值大，则交换它们，并继续向下比较和交换，直到满足小顶堆的性质（即新根节点的值不大于其子节点的值），或者到达叶子节点。 以下是删除3这个元素的过程： 经过几轮下沉后：

典型回答 从定义上来说，所谓的树，就是由节点和边组成，且不存在环的一种数据结构。 从实现上来讲，树一般通过链表来实现。 从结构上分，树可分为二叉树和多叉树。一般我们在写算法的时候，使用二叉树和字典树比较多。 除此之外， B*树一般用于数据库的索引，特点是由多个子树，高度很低，可以减少磁盘IO； 霍夫曼树一般通过哈夫曼编码做数据的无损压缩；（这个是大学数据结构的必修内容，但是面试一般不考） 红黑树和平衡二叉树因为是有序的，所以经常用于二分查找，红黑树相对于平衡二叉树的优点是，不要求树完全平衡，这就会降低数据更新时候的时间复杂度。Java中的HashMap就会通过红黑树来进行查找； 字典树一般是针对一组字符串进行维护的数据结构，它可以将共同前缀的字符串进行优化，节省存储空间，同时可以快速查询某个字符串是否出现。（在LeetCode Hard中比较常见） 树的分类如下所示： 注意：上图中的字典树就是Tire树， 平衡二叉树（AVL树）：一种自平衡的二叉搜索树，其中任何节点的两个子树的高度差都不超过1。 红黑树：一种自平衡的二叉搜索树，它通过节点颜色（红色或黑色）和特定的性质来维持大致平衡，以确保操作的时间复杂度保持在对数级别。 B树和B+树：常用于数据库和文件系统中的多路搜索树，它们通过保持树的平衡和低高度来优化磁盘访问。 前缀树（Trie树）：一种用于快速检索字符串集合的树形数据结构，节点路径形成的字符串可以快速定位。 知识扩展 二叉查找树的演变和区别？ 参考该文章中第二条：为什么是红黑树 ✅为什么在JDK8中HashMap要转成红黑树 什么是字典树？ ✅什么是前缀树，有什么作用？ 什么是前缀树？ ✅什么是前缀树，有什么作用？

典型回答 红黑树是一种自平衡的二叉查找树。 在红黑树中，每个节点是红色或黑色。通过一些规则和颜色的约束，红黑树确保了从根节点到叶子节点的最长路径不会超过最短路径的两倍，因此近似于平衡。这种近似平衡保证了红黑树操作的时间复杂度在最坏情况下仍为对数级别**（O(log n)），**使得红黑树在各种场景中，如关联数组、优先队列等数据结构中非常有用。 节点颜色：每个节点要么是红的，要么是黑的。 根节点：根节点总是黑色的。 红色节点规则：红色节点的子节点必须是黑色的（即红色节点不能相邻）。这条规则也被称为"红色节点不能有红色的孩子"或"红色节点必须有黑色的父节点和黑色的孩子"。 每个叶子节点（NIL节点，空节点）是黑色的：这里的叶子节点是指树末端的NIL指针，而不是树中的实际叶子节点。它们通常表示为空（null）。 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点：这个性质保证了没有任何路径能够有两倍于其他路径的长度，从而保持了树的大致平衡。 红黑树有以下优点： 保证最坏情况下的性能：红黑树通过维持树的大致平衡，而不是完美平衡。这样确保了在插入、删除和查找操作中最坏情况下的时间复杂度均为 O(log n)。这比普通的二叉搜索树（在最坏情况下可能退化为链表，时间复杂度为 O(n)）要好得多。 自平衡：每次插入或删除操作后，红黑树通过旋转和重新着色的方法自动维持平衡，无需额外的操作或维护。 数据结构简洁：节点只需要额外存储一个颜色位，因此相比于其他平衡树（如AVL树）来说，内存的额外开销较小。 扩展知识 红黑树在插入和删除操作中通过旋转和重新着色来保持上述性质，以维护树的平衡。插入或删除节点可能会违反红黑树的性质，因此可能需要进行以下操作之一或组合： 颜色变更：改变某个节点的颜色来维持红黑树的性质。 左旋和右旋：通过旋转操作来重新组织树的结构，从而保持或恢复红黑树的性质。 插入过程 红黑树的插入操作首先按照二叉查找树的规则插入新节点，然后为了维护红黑树的性质，新插入的节点被着色为红色。之后可能需要进行以下一些调整： 情况1：新节点是根节点。 如果新插入的节点是根节点，直接将其重新着色为黑色即可。 情况2：新节点的父节点是黑色。 不需要做任何调整，因为插入红色节点不会破坏红黑树的性质。 情况3：新节点的父节点和叔叔节点都是红色。 将父节点和叔叔节点着色为黑色，并将祖父节点着色为红色，然后将祖父节点视为新插入的节点，对其递归地应用这些调整规则。 如此变化之后，需要将祖父节点设置为当前节点，继续插入动作，做自平衡处理。 如我们的例子，新节点是根节点了，那么就按照情况1，直接把他染色成黑色即可： 情况4：****父节点是红色但叔叔节点是黑色或缺失，新节点是其父节点的右子节点而父节点是祖父节点的左子节点（或镜像情况）。 这时候，需要进行一次左旋转（或右旋转）使之转变为情形 情况5：父节点是红色，叔叔节点是黑色或缺失，且新节点位于父节点的外侧。 进行旋转并重新着色以保持红黑树的性质。 ...

典型回答 从定义上讲： 数组和链表都是数据的集合。 数组中每个元素都是连续的，通过下标进行访问，当我们获取到下标后，就可以随意访问数组中的值 链表中的元素则是不连续的，必须获得链表中某个元素后，才能顺序访问该元素的周围元素，我们没办法随意访问链表中的元素。链表分为单向链表，双向链表，环形链表等 从实现上来讲： 数组可以由一块连续区域的内存实现，其中，内存地址可以作为数组的下标，该地址中的值就是数组中元素的值。因为数组占用的是一块空间，所以数组的大小申请之后就会固定； 链表可以由不连续的内存存储实现，每个元素都会存储下一个元素的地址。（如果是双向链表的话，元素则会还会存储上个元素的地址）。因为链表中存储了元素的地址，所以链表可以在内存足够的情况下随意申请空间 如下图所示： 数组和链表的区别如下所示： 比较项 数组 链表 内存中是否连续 是 否 查询效率 1. 通过下标查是O(1)2. 通过数值查是O(n)，如果是有序数组则O(logn) O(n) 占用空间 1. 直接申请空间，当元素个数不确定时，容易浪费 1. 相对数组来说会存储前后指针2. 大小和元素个数相同 插入/删除 数组需要移动n/2个元素 链表只需要修改指针 知识扩展 什么是双向链表和环形链表 双向链表是指每个元素不仅指向下一个元素，还会指向上一个元素，如下图所示： 环形链表指链表的最后一个元素会指向链表的第一个元素；或者链表的最后一个元素会指向链表中间的某个元素，如下图所示： 相关算法 反转链表：https://leetcode.cn/problems/fan-zhuan-lian-biao-lcof/ 合并两个有序数组：https://leetcode.cn/problems/merge-sorted-array/ 判断环形链表：https://leetcode.cn/problems/linked-list-cycle/

典型回答 栈和队列从定义上来讲，只有一个不同，就是**栈是先进后出的，而队列是先进先出的。**网上有一个形象的例子，说栈是吃了吐，队列则是吃了拉，哈哈哈。两者不的不同如下所图所示： 栈： 队列： 栈和队列的实现 从实现上来说，栈和队列都可以用数组或者链表实现，不过从实现难度和时空复杂度的角度考虑，一般来说，栈会用数组实现，队列会用链表实现。如下所示： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 class StackByArray { private int top = -1; private int maxSize; private int[] stack; public ArrayStack(int maxSize){ this.maxSize = maxSize; stack = new int[maxSize]; } public boolean isFull(){ return top == maxSize - 1; } public boolean isEmpty(){ return top == -1; } public void push(int data){ if (isFull()){ return; } stack[++top] = data; } public int pop () { if (isEmpty()){ throw new RuntimeException("this stack is empty"); } int data = stack[top--]; return data; } } class StackByLink { private Node head; public void push(int data) { Node temp = new Node(data); if(head != null) { temp.next = head; } head = temp; } public int pop() { if(head == null) { return 0; } int ans = head.data; head = head.next; return ans; } private static class Node { public int data; public Node next; public Node(int data) { this.data = data; } } } 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 class QueueByLink { Node front; Node tail; int size; public void offer(int data){ Node temp = new Node(data); if(isEmpty()){ front = temp; tail = front; } else { tail.next = temp; tail = temp; } size++; } public int poll(){ if(isEmpty()){ return 0; } int data = front.data; front = front.next; size --; return data; } public boolean isEmpty(){ return size == 0; } private static class Node { public int data; public Node next; public Node(int data) { this.data = data; } } } 在Java中，常见的栈有Stack，Deque(implemented by LinkedList�)，常见的队列有Queue和Queue（implemented by LinkedList）所以我们一般刷题的时候，常常会用下面的写法： ...