八股文·数据结构

文章目录顺序存储和链式存储顺序存储链式存储栈共享栈特点两个栈共享数组空间队列顺序队列实现两个指针移动的方向一样特点容易出现假上溢的问题循环队列特点无法却分队满和对空如何区分循环队列队满牺牲一个单元法和标记法KMP算法next数组的含义切片的公共前后缀原理主串不回退子串回退到前缀位置哈夫曼树定义带权路径之和最小应用哈夫曼编码定义变长 前缀思想频率低编码长频率高编码短哈夫曼编码的构造叶子节点二叉树完全二叉树满二叉树堆定义实现二叉排序树递归定义遍历性质中序遍历得到单调序列二叉排序树的删除操作平衡二叉树二叉排序平衡递归定义为什么要引入平衡二叉树搜索效率取决于树的高度AVL的插入原理AVL平衡修复八股文修复平衡二叉树的逻辑LL/RR-反面 LR/RL 正面红黑树动机平衡二叉树的调整比较频繁定义红黑失败节点路径长度一致B树多路平衡二叉树定义多路平衡搜索树B树定义非叶子作为指针叶子含数据链表应用MySQL使用这种底层排序算法稳定性的定义相对位置不变判定技巧交换跨度大一般是不稳定的冒泡排序特点稳定有序数组最快插入排序特点稳定有序数组有优化希尔排序分组插入排序为什么比插入排序好插入排序的效率依赖有序性特点不稳定时间复杂度为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)归并排序递归分治特点稳定空间复杂度O ( n ) O(n)O(n)不是原地排序顺序存储和链式存储顺序存储代表列表数组等优点支持随机索引(索引快)缺点插入和删除操作慢链式存储代表链表有点插入和删除操作快缺点不支持随机索引栈共享栈特点两个栈共享数组空间原来的栈顶变成栈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插入到失衡节点右孩子的左子树先对右孩子做右旋再对失衡节点做左旋修复平衡二叉树的逻辑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)不是原地排序稳定不出现交换需要额外数组不是原地排序。