八股文·数据结构

顺序存储和链式存储

顺序存储

• 代表：列表，数组等
• 优点：支持随机索引(索引快)
• 缺点：插入和删除操作慢

链式存储

• 代表：链表
• 有点：插入和删除操作快
• 缺点：不支持随机索引

栈

共享栈

特点：两个栈共享数组空间

• 原来的栈顶变成栈1的底部，栈底变成栈2的底部。
• 共享一个数组的空间。

队列

顺序队列

• 两个指针，分别指向队头和队尾。
  +q.front在出去元素时，往后走；q.end在进来元素时往后走。二者的方向一致。

实现：两个指针移动的方向一样！

特点：容易出现假上溢的问题

• 容易出现假溢出问题，两个指针都在最后，看似没有位置，实际上数组空余。
  

循环队列

特点：无法却分队满和对空！

• 解决了顺序队列出现的假上溢问题。

如何区分循环队列队满？牺牲一个单元法和标记法

• 解决方案1：牺牲一个存储单元用于区分。队空仍然是指针重合，队满时由于隔一个存储单元，就能判断是队空。
• 解决方案2：使用tag标记是出队列还是入队列，用于判断是队满和队空。
  

KMP算法

next数组的含义：切片的公共前后缀

next[i] 表示子串切片s[0:i] 的最长公共前后缀的长度，next 数组只和子串有
关，和主串无关

原理：主串不回退，子串回退到前缀位置

• 保留算法：每次匹配主串失败，子串要重新开始匹配，主串需要回退。
• KMP算法的改进：主串和子串匹配失败后，主串不需要回退，子串回退到公共前后缀的位置。

哈夫曼树

定义：带权路径之和最小

所有叶子节点的带权路径长度之和最小的树。注意一定要带权，不然会退化为最小生成树。

应用：哈夫曼编码

定义：变长 + 前缀

• 哈夫曼编码是一种前缀编码
• 对数据进行变长长度的编码

思想：频率低编码长+频率高编码短

• 出现频率越小的词语会被编码为较大长度，反之出现频率较长的词语会被编码为较短长度。

哈夫曼编码的构造：叶子节点

• 为边进行编码：左边节点编码为0，右边为1。注意是为边进行编码，不是为节点进行编码！！！
• 只有叶子节点才是最终的编码结果。
• 哈夫曼编码保证不出现重复的前缀，消除了二义性。

二叉树

完全二叉树

除了最后一层节点之外，每一层节点都达到最大数量的二叉树。

满二叉树

满二叉树是每一层节点都达到最大数量的二叉树。

堆

定义

• 符合完全二叉树的定义，使用数组来进行顺序的实现。
• 分为小堆/大堆：根节点必须大于/小于两个孩子。

实现

• 使用数组来实现
  

维护堆的性质：例如大根堆满足当前元素大于子节点的元素，如果不满足则交换最大子节点的元素；但这样还不够，需要递归的实现每一步操作！

插入新元素：直接在数组末尾添加一个元素(注意要满足完全二叉树的定义)，然后与父节点进行比较，如果不满足堆的性质则交换。

删除新元素：把末位元素替代待删除元素，然后遍历子节点，把不满足性质的节点进行交换。

二叉排序树

递归定义

• 满足根节点的值大于左子树，小于右子树的二叉树。

遍历性质：中序遍历得到单调序列

• 使用中序遍历可以得到单调递增的序列。

二叉排序树的删除操作

• 回答思路：分左右子树是否存在来讨论。
• 叶子节点 (都不存在)：直接删除
• 恰好存在一个：例如左子树存在，直接使用左子树的根节点连接即可。
• 都存在：使用左子树的最大值当作当前根节点。然后再删除左子树的最大值即可！同理，可以使用右子树的最小值。
  

平衡二叉树：二叉排序+平衡

递归定义

• 满足二叉排序树的性质：左子树的值<根节点<右子树的值
• 平衡定义：左子树的高度与右子树的高度差不超过1
• 平衡因子：定义为左子树-右子树的高度

为什么要引入平衡二叉树：搜索效率取决于树的高度

• 二叉排序树的搜索效率取决于树的高度，在最坏情况下会退化到On。
• 需要对二叉树的高度进行限制，进而保证稳定的搜索效率。

AVL的插入原理

• 插入按照二叉排序树的形式来插入
• 平衡修复：根据最小不平衡子树来进行修复。
• 最小不平衡子树：从插入点开始回溯的第一个不平衡的AVL树。高度一定发生变换。
• 思想：导致不平衡一定是某个子树的高度发生变换，我们找到一个最小的不平衡子树，将其高度修复过来，其他父亲不平衡子树一定也会被顺便修复。

AVL平衡修复八股文

• 命名：LL表示左子树的左子树插入节点导致不平衡

修复平衡二叉树的逻辑：LL/RR->反面 + LR/RL + 正面

往根节点的左子树的左子树插入节点导致不平衡：根节点的左孩子右旋替代根节点。

往根节点的右子树的右子树插入导致不平衡：根节点的右孩子左旋替代根节点。

往根节点的左子树的右子树插入节点导致不平衡：根节点的左孩子的右孩子先左旋取代左孩子，然后再右旋取代根节点。

往根节点的右子树的左子树插入节点导致不平衡：根节点的右孩子的左孩子先右旋取代右孩子，然后再左旋取代根节点。

红黑树

动机：平衡二叉树的调整比较频繁

• 红黑树也是二叉搜索树的变体。平衡二叉树在插入和删除时需要大量的旋转操作来调整树的结构，红黑树通过放宽平衡条件，减少了这些操作的开销。

定义：红黑+失败节点+路径长度一致

• 节点都有两种颜色，根节点为黑色。
• 叶子节点表示空节点和失败节点，叶子节点都是黑色。
• 红色节点不能相邻
• 任意到叶子节点的路径上，经过黑色节点的数量是相同的。
  

B树：多路平衡二叉树

定义：多路+平衡+搜索树

二叉搜索树+平衡+多叉树

• 多路平衡二叉搜索树：一个节点有多个值，有多条搜索路径
• m阶B树中，一个节点最多有m个分支，m-1个值(将搜索范围划为为m个区间)。
• 非根节点的分支数不少于m/2，确保高度有限
• 强制确保所有的左子树和右子树高度一致。
  

B+树

定义：非叶子作为指针+叶子含数据+链表

• 也是二叉搜索树的变体。
• 叶子节点包含指向真实数据所在地址的指针，非叶子节点不包含这一点，仅作为快速查早的索引。
• 叶子节点之间会有指针，构成链表，可以按照顺序索取。
• 一个节点有多少个值与节点有多少个分叉有关。
  

应用：MySQL使用这种底层

排序算法

稳定性的定义：相对位置不变

两个值相同的元素，在排序过后，相对位置仍然保持不变。

判定技巧：交换跨度大一般是不稳定的

冒泡排序

• 两两交换元素，将最大的元素放在末位。
• 稳定的算法：只交换相邻元素

特点：稳定，有序数组最快

• 使用flag来判断是否出现了交换，如果没有出现交换直接结束。
• 在数组本来就有序的情况下，最快时间复杂度为On

插入排序

• 贪心的思想：假设当前子序列有序，选择一个元素与子序列中的元素一一比对，找到其插入位置；插入该元素，最后子序列后面的元素往后移动一位。

特点：稳定：有序数组有优化

• 在数组本来就有序的情况下，时间复杂度为On
• 稳定的算法：只交换相邻元素

希尔排序：分组插入排序

• 选择一个间隔数，根据该间隔数对于组内元素进行插入元素
• 不断降低间隔数，数组逐渐变得越来越有序。

为什么比插入排序好：插入排序的效率依赖有序性

• 通过先优化间隔大的子序列，进而使得数组整体有序，后面进行间隔更小的插入排序时，速度更快。
• 插入排序的原理是数组越有序，排序越快。

特点：不稳定，时间复杂度为O ( n 1.3 ) O(n^{1.3})O(n1.3)

• 不稳定的算法：间隔数>1，会改变相对顺序。
• 时间复杂度为O ( n 1.3 ) O(n^{1.3})O(n1.3)

快速排序：递归+分治

• 选择一个基点，然后将数组分为小于该基点和大于该基点的两部分序列
• 然后递归的进行快速排序。

特点：不稳定，有序时最坏，空间复杂度O ( log ⁡ n ) − O ( n ) O(\log n)-O(n)O(logn)−O(n)

• 不稳定的算法：交换间隔较远的元素。
• 当数组本来有序时，最坏时间复杂度是：On2
• 空间复杂度为：Ologn，需要依赖栈空间

假设数组有序，选择最小值作为绩点，会将序列分为左边的空序列和右边的n-1个长度的序列
问题规模不会显著缩减，而是线性优化。

归并排序：递归+分治

• 将数组不断二分为子序列，子序列递归地进行再次二分
• 然后对于子序列进行合并

特点：稳定，空间复杂度O ( n ) O(n)O(n)，不是原地排序

• 稳定：不出现交换
• 需要额外数组，不是原地排序。