数据结构复习纲要

因为之前就复习完数据结构了，所以为了保持记忆，整理了一份复习纲要，复习的时候可以看着纲要想具体内容。

---

树

• 树的基本概念

  • 树是递归的定义
  • 有序树（如二叉树）
  • 树的高度（叶结点高度为1）
  • 树的性质（王道补充）
    • 高度为h的m叉树至多结点数: (m^h - 1)/(m-1)，等比数列求和公式
    • 具有n个结点的m叉树的最小高度：↑logm(n(m-1)+1) ↑（↑↑为向上取整）
    • 含有n个结点的m叉树的最小高度和最大高度，通过不等式，等比数列求和公式，同时取对数方法计算（重点）

• 二叉树

  • 定义，有序树，子树次序不能颠倒，完全二叉树，满二叉树
  • 性质
    • 第i层最多结点数
    • 深度为k的二叉树最少和最多结点数
    • N = N0 + N1 + N2 && E = 2N2 + N1 = N - 1 —> N0 = N2 + 1
      • 可适用于m叉树 N = N0 + N1 + N2 +….+ Nm && N = mNm + (m-1)Nm-1 + …. + 2N2 + N1
      • 注意n1奇偶不同的情况
    • n个结点的完全二叉树的深度

• 二叉树的存储表示

  • 数组存储
  • 链表存储
  • n个结点的二叉链表中有n+1个空链指针域，N空 = 2N0 + N1 = 2(N2+1) + N1 = N + 1，多叉链表同理
  • 静态链表结构，数组元素四个区域：data、parent、leftchild、rightchild
  • 广义表表示建立二叉树（P197），二叉树高度与广义表深度及括号嵌套数的关系

• 二叉树遍历及其应用

  • 遍历的递归算法（O(n)）

    • 前序
      • 创建二叉树
      • 判断两棵树是否相等
      • 以广义表输出二叉树
    • 中序
    • 后序（从『先计算左右子树，再比较两者大小』方面理解）
      • 树高度、深度
      • 结点个数（左子树的结点个数+右字数的结点个数+1）

  • 遍历的非递归算法

    • 前序、中序、后序（设置tag表示左右方向）、层次遍历（队列）

  • 二叉树的计数

    • 前序（后序）+ 中序
    • 层次 + 中序
    • 前序1，2，3.....n，可以确定多少棵二叉树，与进栈顺序一定，出栈方式的数量相同

• 线索二叉树

  • 中序线索二叉树
    • 建立、遍历
    • 中序序列的First()、Next()、Last()、Prior()函数
    • 实现前序、后序遍历
    • 插入与删除
  • 前序、后序线索化二叉树
    • 后序线索树遍历时仍然需要栈的支持

• 树与森林

  • 树的存储表示
    • 广义表、父指针、子女链表、子女-兄弟链表
  • 森林、二叉树的转换

• 树与森林的遍历及其应用

  • 树的深度优先遍历
    • 先跟、后跟
  • 森林的深度优先遍历
    • 先跟（前序）、后跟（中序）
  • 树和森林的广度优先遍历

• 堆

  • 最小堆、最大堆
  • 堆的建立、插入、删除
    • siftDown()、siftUp()

• Huffman树

  • 建立
  • 带权路径长度
  • 最优判定树
  • Huffman编码
    • 前缀编码（无前缀）

• 综合应用：（递归算法是重点，除非特殊说明否则都是二叉链表存储结构）

  • 递归
    • 返回二叉树中值为x的结点所在的层号
    • 从二叉树中查找值为x的结点，返回指向其父结点的指针
    • 交换左右子树，返回新的根结点
    • 原来根的基础上交换左右子树（前序后序都可）
    • 删除二叉树中值为x的结点（注意在递归状态下删除结点，无需手动改变指针链接）
      • 将此题与链表递归删除结点对比（王道P42），删除结点无需手动指定链接，L=L->next 在递归中相当于L->next = L->next->next，就完成了删除结点
    • 计算二叉树双分支结点个数（注意递归模型的统一性）
    • 计算二叉树叶节点的带权路径长度之和（前序或层次）
  • 非递归
    • 求树的高度
    • 非递归后序遍历
      • 打印值为x的结点的所有祖先
      • 找到p和q的最近公共祖先结点

---

散列表

• 概念
  • 冲突
    • 散列函数可能会把两个或两个以上的不同关键字映射到同一地址的情况
    • 冲突只是一种情况，并不代表结果冲突，冲突是无法避免的，所以需要设计好的散列函数
  • 堆积、聚集、同义词、关键码、装载因子，ASL(succ)、ASL(unsucc)
• 散列函数
  • 除留余数法
    • hash(key) = key % p（p<=m），p是不大于m的最大质数，m是散列表允许的地址数
  • 数字分析法、平方取中法、折叠法
  • 其他方法，注意返回值要一对一确定，否则无法查找，所以不能random
• 处理冲突方法
  • 闭散列（开放定址）法（只能逻辑删除元素）
    • 线性探查法（线性探测再散列）
    • 二次探查法
      • 散列表大小必须是满足4k+3的质数
      • 至少能探测到一半单元，装载因子α <= 0.5时，新表项一定能够插入，且任意一个位置不会被探查两次
    • 双散列法
      • j = H0 = Hash(key)，p = ReHash(key)，j = (j+p) % m，其中p是小于且与m互质的正整数
  • 开散列（闭合定址/拉链）法
  • 计算ASL(succ)和ASL(unsucc)
    • 注意计算ASL(unsucc)时，分母是可能取的散列地址数，如除留余数法%后面的数，跟表长无关（若表长是质数则与散列地址数相同）
• 散列表分析
  • 开散列优于闭散列，除留余数法优于其他散列函数
  • 搜索性能直接依赖于装载因子，不直接依赖于n或m

搜索结构

• 静态搜索结构
  • 顺序搜索
    • 监视哨
  • 基于有序顺序表的顺序搜索和折半搜索
    • 顺序搜索
      • ASLsucc = (n+1)/2
      • ASLunsucc = (1+2+….+n+n)/(n+1) = n/2 + n/(n+1)
    • 折半搜索
      • 代码及拓展代码
      • n个关键码有序顺序表，最多比较次数
      • ASLsucc = O(log2n)
• 二叉搜索树（二叉排序树）
  • 常用来表示字典结构，主要用于内存中目录的编制，需要快速插入搜索删除
  • 搜索、插入、删除，O(log2n)
  • n个关键码的集合，有n！种不同排序，可构成的二叉搜索树有多少种
  • ASLsucc、ASLunsucc（等概率和不等概率）
• AVL树
  • 平衡因子
  • 平衡化旋转（代码）
  • 插入、删除
  • 性能分析，斐波那契数
• 伸展树
• 红黑树

---

图

• 概念
  • 图不可以是空图，至少有一个顶点
  • 完全图
    • 无向图，n(n+1)/2边
    • 有向图，n(n+1)边
  • 路径
    • 一系列顶点序列来定义
  • 简单路径
    • 路径上各顶点不互相重复
  • 连通图与连通分量
    • 无向图中，v1到v2有路径，则v1与v2连通，图中任意一对顶点连通，此图为连通图
    • 非连通图的极大连通子图叫连通分量
  • 强连通图与强连通分量
    • 有向图中，每一对顶点vi到vj有路径，vj到vi也有路径，此图是强连通图
    • 非强连通图的极大强连通子图叫强连通分量
  • 设图G的邻接矩阵为A，A^n的元素An[i][j]等于由顶点i到顶点j长度为n的路径的数目
• 存储结构
  • 邻接矩阵
  • 邻接表
    • 有向图、无向图的度和边链表中边结点数目的关系
• 遍历
  • DFS
    • 深度优先生成树
    • 判断有无回路
  • BFS
    • 广度优先生成树
    • 先访问，再如队列，否则会出现重复入队现象
  • 主调用函数中对BFS/DFS的调用次数是该图的连通分量的数目
  • 基于邻接矩阵遍历的DFS/BFS序列唯一，邻接表则不唯一
  • 时间复杂度
    • 邻接表 O(n+e)
    • 邻接矩阵 O(n^2)
  • 应用
    • 找极大连通子图
    • 消除图中回路
    • 找出关节点等应用
• 最小生成树MST
  • MST不一定唯一，MST权值一定唯一
  • prime
    • 时间复杂度
      • 王道：O(n^2)
      • 教材：O(elog2e)，使用了最小堆
    • 适用于边稠密图
  • kruscal
    • 最小堆
    • 并查集
    • 时间复杂度：
      • O(n)+O(建堆e)
      • 建堆时间复杂度是O(n)还是O(nlog2n)?王道和教材不一致
    • 适用于边稀疏，顶点较多的图
• 最短路径
  • Dijkstra
    • 非负权值单源最短路径，求某一点到其他点的最短路径
    • O(n^{2)，若求所有源最短路径，则O(n}3)
  • Floyd
    • 所有顶点之间的最短路径
    • 允许有带负权值的边，但不许有包含负权值边组成的回路
    • O(n^3)
  • Bellman-Ford
    • 任意权值的单源最短路径
    • Bellman-Ford方程为距离向量路由选择算法给出了基本思想
  • BFS广度优先搜索算法
    • 非带权图单源最短路径
• AOV网（activities on verticles）
  • 拓扑排序
    • 检测有向环
    • 拓扑排序算法，O(n+e)
    • 用DFS实现拓扑排序，退出递归时访问结点，得到逆拓扑有序序列。要求没有有向回路
• AOE网（activities on edges）
  • 关键路径
    • 检测是否有从开始顶点无法到达的顶点
• 综合应用
  • 将无环有向图的顶点号重新安排使得该图的邻接矩阵中所有的1集中在对角线以上
    • 拓扑排序
    • 出度最大的编号为1
  • Dijkstra和prime算法比较
  • 判断有向图中是否存在回路
    • 拓扑排序
    • DFS
      • 无向图：遇到回边
      • 有向图：DFS(v)结束之前出现一条u道v的回边，且u在生成树上是v的子孙
  • 『破圈法』求解最小生成树
  • 判断无向图是否为一棵树
  • DFS非递归算法
  • 分别采用DFS、BFS判断有向图邻接表中是否存在vi到vj的路径
  • 邻接表，输出vi到vj的所有简单路径
  • 计算图中各顶点的度
  • 计算某顶点的入度、出度
  • 删除有向图中以某顶点为弧头（尾）的有向边
  • 根据邻接矩阵转换邻接表、根据邻接表转换为邻接矩阵
  • 根据邻接表建立逆邻接表（边链表中是弧指向该顶点的顶点）

---

内部排序

• 排序码、算法稳定性、内部排序外部排序
• 对任意n个关键字排序的比较次数至少为↑log2(n!)↑
• 插入排序（左边是排好序的序列，右边是未排序序列，右边第一个拿出来插入到左边）
  • 初始排列基本有序的序列，效率很高
  • 直接插入排序（从后向前比较再插入）
  • 折半插入排序（注意是从high+1的位置（包括）往后移空出插入位置）
    • 比较次数为O(nlog2n)，但交换次数仍然是O(n^{2)，所以时间复杂度仍然是O(n}2)
  • 希尔排序
    • 增量gap = ↑n/3↑ + 1 （教材）
• 冒泡排序（从后往前冒泡）
• 快速排序（先移动high）
  • 最通用，平均最快
  • 分治思想
  • 每一次选出一个基准值，小于基准的在左边，大于基准的在右边，基准在中间
  • 每次的枢轴都把表分为长度相近的两个子表时，速度最快
  • 改进算法
    1. 序列长度M取值为5-25时，直接插入比快排快10%，因此小于M时直接用插入排序
    2. 划分过程中对小规模子序列不排序，最后进行一遍直接插入排序
    3. 采用左端点，右端点，中间端点，三者取中间值作为基准，并交换到右端点
    • 将2.3结合，可将递归实现的快排效率提高20%-25%
• 选择排序
  • 直接选择排序
    • 每趟从未排序序列中选择一个最小的与未排序序列第一个位置进行交换
    • 移动次数O(n)，比较次数O(n^{2)，时间复杂度O(n}2)
  • 锦标赛排序（胜者树）
• 堆排序
  • 每趟从小到大排序，建立最大堆，将最大的取出来交换到排序数组最后
  • 计算插入、删除元素的比较次数时，注意左右子树可能会先比较
• 归并排序
  • 分治法
  • 改进算法
  • 归并趟数 m = logkN 其中k为路数 k路归并
• 分配排序
  • 桶式排序
  • 基数排序
    • LSD 最低位优先
    • MSD 最高位优先
    • 空间O(n)，时间O(d(n+r)) ，d为分配和收集的趟数，r为队列数
• 算法分析
  • 按时间复杂度：
    • O(n^2)：直接插入、冒泡、直接选择、折半插入
    • O(nlog2n)：快排、堆排、归并
    • O(n^1.25)：希尔
  • 按内存（空间）复杂度：
    • O(1)：直接插入、冒泡、直接选择、堆排、希尔
    • O(log2n)：快排
    • O(n)：归并
  • 按规模：
    • 规模很小（n<=25）：直接插入、简单选择排序（记录本身信息量较大，移动要少）
    • 中等规模（n<=1000）: 希尔
    • 规模不是很大（n<10k）：直接插入、冒泡、直接选择比较主要
    • 规模很大：快排、堆排、归并
    • 规模很大，记录关键字位数较少且可分解：基数排序
    • 基本有序：插入、冒泡
    • 记录本身信息量较大时：用链表做存储结构，避免耗费大量时间移动记录
  • 按稳定性：
    • 稳定：直接插入、冒泡、归并、折半插入、基数排序
    • 不稳定：快排、堆排、希尔、简单（直接）选择
  • 按最好最坏情况：
    • 冒泡：改进算法最好只需要一趟起泡过程，n-1次比较操作
    • 直接插入：最好只要n-1次比较操作O(n)，平均和最差情况下，比较和交换都是O(n^2)
    • 直接选择：比较次数总是O(n^2)，但移动次数最好情况一次也不移动
    • 快排：
      • 时间复杂度：元素有序时会退化，时间O(n^2)，空间O(n)，但改进算法可避免最坏情况发生
      • 空间复杂度：最好为log2(n+1)，最坏为O(n)，平均O(log2n)
    • 希尔：最坏O(n^2)
    • 归并：平均和最坏的空间O(n)
  • 比较：
    • 堆排不太可能提供比快排更好的平均性能
    • 归并排序跟堆排和快排相比，稳定
    • 基数排序的线性时间开销实际并不比快排小多少，应用不广泛，主要适用于硬件环境，编程环境和输入与元素序列满足一定条件时，且不能处理float，double类实数
    • 只需得到前k小个元素的顺序排列可采用的排序算法有冒泡、堆排、简单选择，当k>=5时，堆排最优，4n+klog2n
• 算法代码应用
  • 快排划分的两种算法
    • 从第二个元素开始寻找小于基准的元素，找到后交换到前面 swap( A[++i] , A[j] )，重复
    • 从后面开始找到<基准的元素j，覆盖从前面找到>基准的元素i，i++，覆盖j，j++，覆盖i，重复
  • 使用快排分治思想，在数组中找到第k小的元素
    • 用k跟基准比，小的在左边，大的在右边，递归划分继续查找
  • 荷兰国旗问题，将仅有红白蓝三种颜色的序列，按红白蓝顺序排好（将负数排在非负数前面同理，快排划分思想）
    • j为工作指针，i以前的元素为红色，k以后的元素为蓝色，i++，k—
  • 链表的选择排序算法，每次从first链上摘下最大的结点current链入head之后，算法结束前将head删除

---

外部排序

• 基本过程
  1. 建立为外排序所用的内存缓冲区，根据大小将输入文件划分为若干段，对各段进行内排序（如堆排），经过排序的段叫初始归并段，将他们写入外存
  2. 把第一阶段生成的初始归并段加以归并，一趟趟扩大归并段和减少归并段个数，直至最后归并成一个大有序文件
  • 输入缓冲区、输出缓冲区
  • 总归并趟数 == 归并树的高度减一 == ↑log2m↑ ，其中m为初始归并段个数
  • S=↑logkm↑ 增大归并路数k，或减少初始归并段个数m，都能减少归并趟数s，以减少磁盘I/O数，提高排序速度
    • 但是k增大时，相应需要增加输入缓冲区个数，k值过大时，外存I/O仍会增加，需要综合考虑
• k路平衡归并
  • k路平衡归并时，m个初始归并段，则归并树有 ↑logkm↑+1 层，需要归并 ↑logkm↑ 趟
  • 增大归并路树k，会是内部归并的时间增大
• 败者树
  • 『败者树』从k个归并段中选最小者，排序码比较次数与k无关，总的内部归并时间不会随k的增大而增大
  • 完全二叉树，叶节点存放各归并段在归并过程中当前参加比较的记录，非叶结点记忆其子女中记录排序码小的结点（败者），根结点记忆树中当前的最小记录
  • 冠军送入结果归并段，冠军所在归并段的下一个记录替补上来，与其父节点记忆的败者进行比较，败者进行记忆，胜者与更上次父节点的败者继续比较，直到比出冠军
  • 败者树高度↑log2k↑+1，包括冠军结点
  • 每次调整找下一个最小记录时，最多做↑log2k↑次排序码比较
• 初始归并段的生成（选择-置换）
  • 使用败者树生成初始归并段，同样内存下，生成平均比原来等长情况下大一倍的初始归并段，从而减少m，降低s
  • 从败者树中选一个最小的，然后补上记录，再输出最小的，注意只有比当前归并段最大值大的才能输出到归并段，否则放到下一个归并段中
  • n个记录，生成初始归并段的时间开销O(nlog2k)，每输出一个记录，对败者树进行调整需要O(log2k)
• 最佳归并树
  • 只有度为0和度为k的结点的正则k叉树
  • 叶节点代表参加归并的各初始归并段，叶节点权值为该初始归并段的记录个数，叶节点到根结点的路径长度表示在归并过程中的归并趟数，归并树的带权路径长度WPL（叶节点）即为归并过程中总的读记录树，总读写记录次数为2*WPL
  • Huffman树思想
    • 补空归并段，计算补的度为0的结点个数，正则k叉树 n0 = (k-1)nk + 1，其中n0就是记录数n（Huffman树的key都是叶节点）
    • 若(n0-1)%(k-1) = 0，则说明这n0个叶节点（即初始归并段）正好可构造k叉归并树，不需要空归并段
    • 若(n0-1)%(k-1) = m ≠ 0，则说明剩m个记录加不到树中。此时在记录中增加k-m-1个空记录（0）即可
• 计算应用
  • 假设文件4500个记录，磁盘上每个页块可放75个记录，计算机中用于排序的内存区可容纳450个记录，（1）可建立多少归并段？每个归并段有多少记录？存放于多少页块中？（2）应采用几路归并？写出归并过程及每趟需要读写磁盘的页块数
    • （1）可建立初始归并段有4500/450=10个。每个初始归并段中有450个记录，存于450/75=6个页块中
    • （2）内存区可容纳6个页块，可建立6个缓冲区，其中5个用于输入，1个用于输出，采用5路归并。做了两趟归并，每趟需要读60个磁盘页块，写60个磁盘页块

---

多级索引结构

• 动态的m路搜索树
  • 每个结点最多m棵子树，最多有m-1个关键码
  • 最少有0棵子树，1个关键码
  • AVL树是2路搜索树
  • m路搜索树，高度h，最大结点数（m^h-1)/(m-1) ，注意是结点数，一个结点里有m-1个关键码，所以相乘，最大关键码数为（m^h-1）
    • 最大结点数时的结点结构与满m叉树结构一样，所以结点数都是上面的公式，相同
  • m路搜索树，高度h，最小结点数为h
  • h <= 关键码个数 <= (m^h-1) —> n个关键码的m路搜索树高度h： logm(n+1) <= h <= n
  • 提高搜索树的路数m，可以改善树的搜索性能。对于给定的关键码数n，如果搜索树是平衡的，可以使m路搜索树的性能接近最佳（B树）
• B树（继承自m路搜索树）
  • B树常存储在磁盘上，在B树种寻找结点是在磁盘上进行的，在结点内找关键字是在内存中进行的。找到目标结点后，先将结点中的信息读入内存，再用顺序或折半查找关键字
  • B树结构
    n
    P0
    K1
    P1
    K2
    P2
    ……
    Kn
    Pn
    K为关键字n个，P为指向子树根结点（也即磁盘地址）的指针n+1个（可出计算题）
  • m阶B树的性质（调整B树时看的就是这三点性质！）
    • 根结点至少2个子女
    • 除根结点以外的所有结点（不包括失败结点）至少有↑m/2↑个子女，即该结点至少有↑m/2↑-1个关键字
    • 所有的失败结点都位于同一层
  • B树的搜索过程是一个在结点内搜索和循某一条路径向下一层搜索交替进行的过程，因此B树的搜索时间与B树的阶数m和高度h直接相关，需加以权衡
  • 搜索成功所需时间取决于关键码所在层次，搜索不成功所需时间取决于树的高度
    • B树高度时不包括失败结点
    • 第二层至少两个结点，每个结点至少有↑m/2↑个子女，因此第三层至少2↑m/2↑个子女
    • 第h层至少有2↑m/2↑^(h-2)
    • 位于第h+1层的失败结点至少有2↑m/2↑^(h-1)个结点 == 树中所有关键码的数量+1
    • 树中关键码有N个，则失败结点个数为N+1 >= 2↑m/2↑^(h-1) —> h <=↓ log↑m/2↑((N+1)/2) ↓+ 1，（h不包括失败结点）
    • B树最高h =↓ log↑m/2↑((N+1)/2) ↓+ 1，最低h = ↑ logm(n+1)↑
    • 由公式看到，增大m可以降低树的高度，从而减少结点读入结点的次数，减少磁盘I/O次数，但是当m超过可分配内存时，结点不能一次读入内存，反而增加了读盘次数
• B树的插入
  • 每个非失败结点的关键码个数在 ↑m/2↑-1 和 m-1 之间（这样其子女就有↑m/2↑到m个，满足B树性质）
  • 插入是在某个叶结点（第h层）开始，插入后关键码个数超过m-1，则需要分裂，将中间结点K↑m/2↑插入父结点，继续向上处理
  • 高度为h的B树，自顶向下搜索叶结点的过程需要h次读盘，最坏结果需要自底向上分裂结点，分裂非根结点向磁盘写出2个结点，分裂根结点写出三个结点，完成一次插入需要读写磁盘次数为 h+2(h-1)+3 = 3h+1
    • 当m较大时，访问磁盘平均次数为h+1
• B树的删除
  • 所删除关键字k不在终端结点中时
    • k的左子树满足条件，前驱值k’取代k，再递归删除k’；若左子树不满足，右子树满足，则用右子树后继来取代
    • 前后子树均不满足条件，合并两个子结点，直接删除k
  • 所删除关键字k在终端结点中时
    • 直接删
    • 不能直接删，兄弟够借，父亲下来，兄弟上位
    • 兄弟不够借，删除k后，父亲下来跟兄弟合并，再看父亲
  • 最坏情况，读写磁盘 3h-2次，释放h个结点
• B+树
  • 实现文件索引结构方面比B树使用更普遍
  • 所有关键码都在叶结点中，上层非叶结点的关键码是其字数中最小（大）关键码的复写
  • 叶结点包含了全部关键码及指向相应记录地址的指针，且叶结点本身按关键码从小到大顺序连接
  • 『最大关键码复写』原则定义B+树
    • 每个结点最多有m棵子树
    • 根结点至少有一个子树，其他结点至少↑m/2↑个子树
    • 所有叶结点再同一层，按从小大顺序存放全部关键码，各个叶结点顺序链接
    • 有n个子树的结点有n个关键码
    • 非叶结点可以看成叶结点的索引
  • 叶结点中存放的是对实际数据记录的索引，每个索引项给出数据记录的关键码及实际存储地址
  • B+树有两个头指针，一个纸箱B+树的根结点，一个指向关键码最小的叶结点，因此可对B+树进行两种搜索：
    • 循叶结点拉起的链表顺序搜索
    • 从根结点开始，自顶向下随机搜索，每次搜索都是一条根到叶结点的路径
• B+树的插入
  • 仅在叶结点上进行
    • 插入后叶结点中的关键码个数n>m时，将叶结点分为两个分别包含↑(m+1)/2↑ 和 ↓(m+1)/2↓个关键码的结点
    • 他们的父结点应同时包含这两个结点的最大关键码和地址
  • 非叶结点中关键码的插入
    • 叶结点分裂后，其父节点（非叶结点）被动插入，最终可能树会增加一层
  • 插入高度h的B+树需要3h+1此磁盘访问，平均大约h+1次磁盘访问，与B树类似
• B+树的删除
  • 仅在叶结点上进行
  • 删除后该结点关键码个数不小于↑m/2↑-1（或者说子树棵树小于↑m/2↑时）时，无需调整上层索引（即使删了某结点的最大关键码，其在父结点的复写也不用动，因为索引只起引导搜索的分界作用）
  • 小于↑m/2↑时，需要调整合并
    • 可从右兄弟结点拉一个，然后修改父结点索引
    • 右兄弟子树棵树也达到下限时，将右兄弟合并至被删关键码所在结点，父结点再根据情况与其兄父调整合并，最终可能树会减少一层
• 计算应用
  • 利用B树做文件索引时，若假设磁盘页块的大小是4000字节，指示磁盘地址的指针需要5个字节，现有20 000 000个记录构成的文件，每个记录200字节，其中包含关键字5个字节。（1）在此采用B树做索引的文件中，B树的阶树应为多少？（2）嘉定文件数据部分未按关键字有序排列，则索引部分需要占用多少磁盘页块？
    • （1）：根据B树概念，一个索引结点应适应操作系统过一次读写的物理记录大小，其大小应取不超过但最接近一个磁盘页块的大小。假设B树为m阶，一个B数结点最多存放m-1个关键字（5字节）和对应的记录地址（5个字节）、m个子树指针（5个字节）、1个指示结点关键字个数的整数（2字节），则有（2(m-1)+m）5+2<=4000，m<=267
    • （2）：一个索引结点最多存放266个索引项，最少133个，全部有20 000 000个记录，每个记录200字节，每个页块则20个记录，全部记录分布在1 000 000个页块中，则最多占用1 000 000/133 = 7519个磁盘页块（也就是7519个索引结点）作为B树索引，最少3760个。