数据结构与算法

由于本人对算法编写比较熟悉，略过了许多算法的具体过程（比如快速排序、归并等）侧重于在 OI 中不常见的理论部分知识点。 内容包含：数据结构，算法设计与分析

概述

• 数据结构三要素：逻辑结构、存储（物理）结构、数据的运算
  • 逻辑结构：线性、非线性（树、图）
  • 存储结构：顺序存储、链式存储、索引存储（<关键字，地址>）、散列存储

渐进复杂度分析

• \(O\) 的定义 \(\lim_{ n \to \infty }\frac{f(n)}{g(n)}=c<\infty\to f\in O(g)\)
  • 若 \(c=0\) 则为 \(o\)，\(c=w\) 则为 \(\infty\)
  • 等于为 \(\Theta\)（\(0<c<\infty\)），大于等于为 \(\Omega\) (\(c>0\))

• 常见复杂度的比较

  • \(lglgn<lnn,lgn<lgn^2<\sqrt{ n }<n<nlgn<n^{1.1}<\)
  • \(n^2,n^2+lgn<n^3<2^{n-1},2^{n}<e^n<n!\)
  • Tip \(n! = \sqrt{ 2\pi n }{\left( \frac{n}{e} \right)^n}\)

• smooth 定理：

  • 对于⼀个非负 ,最终单增的函数若满⾜ \(f(2n)\in \Theta(f(n))\) 则称为 smooth 函数
  • 可以用部分特殊位置的渐进复杂度作为算法的复杂度 (如 \(2^k\))

递归问题的时间复杂度求解 - 对分治递归式的理解 \(T(n)=aT\left( \frac{n}{b} \right)+f(n)\) - 划分为 a 个问题规模为 1/b 的子问题 - f (n) 表示子问题划分与合并的代价 - 猜测-证明法： - 先根据递归树推导猜测，再用变量替换进行证明 - - 递归树 - - 主定理法： - 如果公比大于 1，最后一行代价作为总代价；如果小于 1，根节点代价作为总代价；如果公比等于 1，每一行代价和作为总代价 - 取 \(E=\log_{b}^a\) - 若 \(f(n)\in O(n^{E-\epsilon})\) 则 \(T(n)\in\Theta(n^E)\) - 若 \(f(n)\in \Theta(n^E)\) 则 \(T(n)\in \Theta(f(n)\lg n)\) - 若 \(f(n)\in \Omega(n^{E+\epsilon})\) 则 \(T(n)\in\Theta(f(n))\) - *若 \(f(n)\in \Theta(n^E\lg ^kn)\) 则 \(T(n)\in \Theta (n^E\lg ^{k+1}n)\)

算法分析的数学基础

• 级数求和

  • \(\sum^n_{i=1}i=\frac{n(n+1)}{2}\)
  • \(\sum^n_{i=1}i^2=\frac{1}{3}n\left( n+\frac{1}{2} \right)(n+1)\)
  • 即求和 \(\sum^n_{i=1}i^k\in \Theta\left( \frac{1}{k+1}n^{k+1} \right)\)
  • 等比数列 \(\sum ar^i=\Theta(r^k)\) 就等于最大那一项
  • \(\\sum^k_{i=1}\frac{1}i=\ln k\)

• 算法问题规约：

  • 输入规约：明确规定算法接受的所有合法输入
  • 输出规约：规定对于每一组合法的输入，相应的输出是什么
• 弱数学归纳法
  • P (1) 为 TRUE
  • p (k) -> p (k+1)
• 强数学归纳法
  • P (1) 为 TRUE
  • p (1)&&... p (k)->p (k+1)

    比如 gcd 算法就可以由强数学归纳法证明

顺序结构

线性表

• 线性表：一种抽象数据结构，线性表中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的（有唯一的前后继）。

顺序表

• 用地址连续的存储单元一次存储线性表中的数据元素，逻辑上相邻的元素在物理位置上也相邻
• 顺序表与数组的区别
  • 数组是一种存储方式（顺序存储），数组并不一定是顺序表（比如数组形式存储的堆）
  • 顺序表（线性表）强调的是一对一的前后继关系

链表

• 逻辑上相邻的元素，物理上不再相邻
• 头插法得到反序链表，尾插法得到正序

栈与队列

• 栈和队列都是限制存取位置的线性结构，即具有相同的逻辑结构（线性结构）

栈

• n 个元素入栈，可能的出栈顺序数目：
• 枚举第一个元素的出栈时间，分治 \(f(n) = \sum_{i=1}^{i=n}{f(i-1)*f(n-i)}\)（卡特兰数），通项为 \(f(n) = \frac{C_{2n}^{n}}{n+1}\)
• 在第一个元素入栈之后出栈之前有 i-1 个元素入栈又出栈，这可以作为一个类似的子问题
• 双栈共享空间
  • 
• 链式栈
  • 栈顶在链头，插入与删除仅在栈顶处执行
  • 

表达式求值 - 转化为后缀表达式 - 手动转化方式：先对中缀表达式按运算优先次序加上括号，再把操作符后移到右括号的后面并以就近移动为原则，最后将所有括号消去。 - - - 数字直接输出 - ; 用作标识，开始之前先将 ; 入栈，并且中缀表达式末尾也有一个 ;（用作结束时清空栈） - - - 后缀表达式求值 - 遍历后缀表达式，遇到数就压栈，遇到操作复就从栈中取数进行计算，再放回栈中 - 栈中剩下的最后一个元素就是计算结果 - 对于尾递归和前向递归可以不使用栈修改为迭代

队列

• 顺序队列
  • 
  • 进队：rear++；出队：front++
  • 队空时：rear=front；队满时：rear=maxSize
  • 随着元素进入与弹出，逐渐无法使用，出现假溢出
• 循环队列
  • 
  • 队头指针进 1: front = (front+1) % maxSize;
  • 队尾指针进 1: rear = (rear+1) % maxSize;
  • 队列初始化：front = rear = 0;
  • 队空条件：front == rear;
  • 队满条件：(rear+1) % maxSize == front
• 链式队列
  • 
  • 队头在链头，队尾在链尾。

数组与矩阵

• 对称矩阵（方阵）
  • 可以只存储为上三角矩阵或下三角矩阵
  • 下三角矩阵：只存储 \(i\geq j\) 的数组元素，数组元素 \(A[i][j]\) 在数组中存放位置为 \(1+2+\cdots+i+j=(i+1)*i/2+j\)
  • 上三角矩阵：只存储 \(i\leq j\) \(A[i][j]\) (i<=j)位于 \(n+(n-1)+\dots+(n-i+1)+j-i=(2*n-i-1)*i/2+j\)
• 三对角矩阵
  • 有 \(3n-2\) 个非 0 元素, \(0<=i<=n-1 \ i-1<=j<=i+1\)
  • \(A[i][j]\) 位于 \(k=2*i+j\)

• 计算时一定要小心下标是否从 0 开始

• 稀疏矩阵

  • 稀疏因子 \(e=s/(m*n)\) 通常认为 \(e<=0.05\) 为稀疏矩阵
  • 存储稀疏矩阵时一般只存储非零元素，使用三元组 \((i,j,a_{ij})\) 表示矩阵的元素在稀疏矩阵的三元组表中 (按照字典序进行存储)
  • 非空元素三元组加上矩阵的长宽就可以确定唯一的稀疏矩阵
• 稀疏矩阵转置
  • 设矩阵列数为 Cols，对矩阵三元组表扫描 Cols 次。第 k 次扫描找寻所有列号为 k 的项，将其行号变列号、列号变行号，顺次存于转置矩阵三元组表。
  • （因为要维护字典序所以这么麻烦）
• 快速转置算法
  • 

字符串

KMP 算法

• 朴素的模式匹配 \(O(n\cdot m)\)，kmp 的复杂度 \(O(m+n)\)
• \(next[i]\) 表示 \(pat[0,i-1]\) 的最长共同前后缀的长度
• 

  vector<int> build_next(string s)//构建next数组
  {
      vector<int>next{-1};//第一位一定为零（因为规定前后缀不能为自身）
      int i=1,len=0;//len记录当前位置最大重合长度
      while(i<s.size())
      {
          if(s[len]==s[i-1]&&len!=i-1)
          {
              len++;
              next.push_back(len);
              i++;
          }
          else
          {
              if(len==0)
              {
                  next.push_back(0);
                  i++;
              }
              else
                  len=next[len];//找到对应的前缀的末尾位置（一种递归思想，长的匹配不上则逐渐缩短去找）
          }
      }
      return next;
  }
      int kmp(string fs,string ss)//ss为待匹配的子串
      {
          vector<int>next=build_next(ss);
          int i=0,j=0;
          while(i<fs.size())
          {
              if(fs[i]==ss[j])
              {
                  i++;
                  j++;
              }
              else if(j>0)
                  j=next[j];//前next[j-1]位仍相同，在这之后继续匹配
              else
                  i++;
              if(j==ss.size())
                  return i-j;
          }
          return -1;
      }
  

广义表

• 广义表中的元素可以为数据元素或子表
• n > 0 时表的第一个元素为广义表的表头，其他元素为表尾 \(G=('a',(5,3,'x'),\dots)\) 其中表头为 \('a'\)，表尾为 \(((5,3,'x'),\dots)\)
• 通过 head、tail 操作获得表头和表尾，进而得到任何一个元素（要走注意的是返回表尾时会在外面额外加上一组括号）
  • 
  • 

• 长度为元素数目，深度为括号嵌套的层级

  • 

• 广义表节点的定义：utype|info|tlink

  • utype 节点类型：0 表示广义表附加头结点（表标识符 ABCD）；1 表示元素数据项；2 表示子表
  • info 存储信息：0 时存储引用计数；1 时存储具体数据值；2 时存储子表表头指针
  • tlink 尾指针：0 时指向第一个节点；否则指向同层下一个节点
  • 

排序

• 内排序与外排序: 内排序是指在排序期间数据元素全部存放在内存的排序；外排序是指在排序期间全部元素个数太多，不能同时存放在内存，必须根据排序过程的要求，不断在内、外存之间移动的排序。
• 常见的不稳定排序：希尔排序，快速排序，直接选择排序，堆排序
• 
• 需要随机访问的排序只能使用顺序存储：如折半插入排序，希尔排序，快速排序，堆排序
• n 较小：选择直接插入排序、简单选择排序
• n 较大：使用 nlogn 算法
• 基本有序：直接插入，冒泡
• 如果 n 很大，但是关键位较少可以考虑基数排序

常见的排序算法

• 插入排序
  • 直接插入排序：每次选一个还没有排序的元素向已经排好序的数组中插入元素（从后向前），不能放久交换位置
  • 折半插入排序：在查找插入位置时折半查找而不是逐一比较（不过由于要逐一交换，还是很慢，只是比较次数减少了）
• 希尔排序
  • 取一个整数 gap 作为间隔，将距离为 gap 的元素放在同一个子序列（即得到 gap 个序列），对每一个子序列进行直接插入排序，然后减小 gap 重新进行插入排序，直至 gap=1
  • 复杂度约为 \(n^{1.25}\)

• 选择排序

  • 直接选择排序：每一趟选出待排序元素中的最小元素，放在已排序区间的末尾（与第一个元素对调）
  • 锦标赛排序：将两两比较中较小者作为优胜者上升到双亲节点（胜者树）
  • 
  • 建树 \(O (n)\)
  • 之后对树进行维护，将获胜者修改为 \(-\infty\) 之后对整个路径进行更新，耗时 \(O(\log n)\)

• 快速排序

  • \(A(n)=(n-1)+A(i)+A(n-1-i)\)
  • partition 的两种方式：左右交替移动（partition 作为中介）交换；ij 双指针，从左到右移动，维护两个区间
  • 注意由于递归的原因，快速排序并不是 O (1) 的，平均为 O (nlogn)最差 O (n^2)
• 归并排序
  • \(A(n)=2A\left( \frac{n}{2} \right)+O(n)\)
• 堆排序
  • 建堆 \(W(n)=2W\left( \frac{n}{2} \right)+2\log n=O(n)\)
  • 维护堆 \(O(\log n)\)
  • 两种维护操作：从上向下（如删除根节点），从下向上（如插入新元素）
• 基数排序
  • 以 LSD 为例，先从左到右遍历元素，将第 i 为 k 的 push 到第 k 组（一共 0-9 即 10 组），之后从左到右取出元素得到新排列；再根据第二位（十位）重做，直至所有位完成
• 复习到这看到了这个图片~

基于比较的排序的下界

• 引入决策树，每个节点表示两个元素之间的比较，其左右节点分别表示比较不同结果，最终叶节点表示根据前面的比较信息得到的排序

• 由于排序结果有 n! 种，因此决策树的叶节点至少有 n! 个，那么 \(h\geq\log (n!)=\Omega(n\log n)\) 即为基于比较的排序的最坏情况的下界

• 平均情况的时间复杂度对应于根节点到所有叶节点的路径长度的加权值

  • 为了计算决策树根节点到所有叶节点路径长度的加权和，引入外部路径长度 EPL
  • \(ELP(T)=ELP(T_{L})+N_{L}+ELP(T_{R})+N_{R}\)
  • 平均复杂度就是 \(\frac{ELP}{L}\)，L 为叶节点数目，即可能得排序结果数目
  • 对于尽可能平衡的树 \(ELP=L\log L\) 得到最终的复杂度同为 nlogn

查找&选择

线性时间选择

期望线性时间选择-partition - 做一次 partition 之后，如果左边元素数等于 k-1，那么直接返回该元素 - 如果左边数目大于 k-1，那么在左边递归的找第 k 元素 - 如果左边数目小于 k-1，那么对右边递归选择（选 \(k-n_{l}-1\)） - 平均复杂度 \(O(n)\) 最坏时间复杂度 \(O(n^2)\)

最坏线性时间选择 - 核心思想：最坏情况下的划分也不能太不平衡 - 将所有元素 5 个一组进行划分（\(\left\lceil \frac{n}{5} \right\rceil\) 组），并找到每一组中的中位数，并对数组进行划分 - 再对所有组，依据中位数的大小求中位数的中位数，并进行划分 - - 可以明确的是 - A 区全部小于 \(m^*\)；B 区全部大于 \(m^*\)（这就保证了相对均衡的划分） - 对于 CD 区要进行比较判断 - 这就相当于进行了一次有划分均匀性保障的 partition，之后的过程一致 - 时间复杂度 \(W(n)\leq W\left( \left\lceil \frac{n}{5} \right\rceil \right)+W\left( \frac{7}{10}n+6 \right)+O(n)=O(n)\)

为什么是 5 个一组

5 个一组：\(W(n)\leq W\left( \left\lceil \frac{n}{5} \right\rceil \right)+W\left( \frac{7}{10}n+6 \right)+O(n)=O(n)\) - 3 个一组 - \(W(n)\geq W\left( \left\lceil \frac{n}{3} \right\rceil \right)+W\left( \frac{2}{3}n+3 \right)+O(n)=O(n\log n)\) - 渐进复杂度都不对了 - 7 个一组 - \(W (n)\leq W\left ( \left\lceil \frac{n}{7} \right\rceil \right)+W\left ( \frac{5}{7}n+8 \right)+O (n)\) - 只是常数大一点（因为没必要分这么细，并没有比 5 使得划分更加均匀） - 问题在这：对于 \(W(n)=W(an)+W(bn)+O(n)\) - 当 \(a+b<1\) 时时间复杂度为 \(O(n)\)；每一层任务量递减，因此主要是由顶层贡献的 - 当 \(a+b=1\) 时时间复杂度为 \(O(n\log n)\)；每一层任务量不变，即每一层的贡献量一致，都要纳入计算

二分查找

• 从一组键值中找到指定的键值
• 上界 \(O(n)\)；下界 \(O(1)\)
• 折半查找的判定树高度：\(\lceil \log (n+1) \rceil\) (即查找失败时的最大查找次数)

树与森林

• 树的深度：到根路径长（根的深度为 0）
• 数的高度：到叶节点最大路径长（叶节点的高度为 0）
• 子孙：某结点的所有下属结点，都是该结点的子孙。
  • 直接下属：子女
• 祖先：根结点到该结点的路径上的各个结点都是该结点的祖先。
  • 直接上属：双亲
• 度：节点的子树数目就是节点的度，树中度的最大值是树的度（说节点的度，不包括来父节点的边）
• 有序树：子树从左到右有顺序，不能调换，无序树反之

二叉树

• 深度为 k 的二叉树最少 \(k\) 个结点，最多 \(2^k-1\) 个（满二叉树）；n 个节点的完全二叉树深度 \(\lceil\log_2(n+1)\rceil\)
• 满二叉树：有 \(2^k-1\) 个结点的二叉树
• 完全二叉树：除第 k 层外全满（堆的要求）
  • 有 \(\left\lfloor \frac{n}{2} \right\rfloor\) 个分支节点，\(n-\left\lfloor \frac{n}{2} \right\rfloor\) 个叶节点
  • 只可能有一个度为 1 的点，如果有一定是 \(\left\lfloor \frac{n}{2} \right\rfloor\) (当 \(n\%2=0\) 时存在)
• \(n_{0}=n_{2}+1\)（注意这里的非叶节点是指度为 2 的）

遍历

• 可以唯一确定二叉树的组合
  • 先序遍历+中序遍历
  • 后序遍历+中序遍历
  • 层次遍历+中序遍历
  • 其他的组合都没法很好的确定节点来自左子树还是右子树（如全左、右倾斜树）
• 其他组合可能只能在一些特殊情况求出（如满二叉树）
• 前序遍历+后序遍历：如果有 A... B 在前序 B... A 在后序，则 A 是 B 的祖先
• 前序遍历（非递归）
  • 先遍历左边再右边，因此将右边先存储起来，等到无路可走时前往
  • 
• 中序遍历（非递归）
  • 与前序类似，不过不止右子树需要回来再访问，根节点也要和右子树一起访问，因此压栈的为根节点，回来时先访问根节点，之后继续访问右子树
  • 
• 后序遍历（非递归）
  • 更为复杂，需要标记一个节点处于什么状态，（回来时左子树一定完成了，因为先访问左子树）等待访问右子树和等待访问根节点，一个元素的不同状态会被依次压栈
  • 
  • 
• 层次遍历：使用 BFS（队列）实现
  • 

（中序）线索化二叉树

• 可以直接找到书中每个节点在中序遍历中的前继和后继
• 复用 left 和 right 指针，减少空间的使用
  • 标志位=0 表示存储的是子女结点，1 表示存储线索
  • 

rightChild\rtag	==0	==1
==NULL	无此情况	无后继
!=NULL	后继为当前结点右子树的中序下的第一个结点	后继为右子结点

leftChild\ltag	==0	==1
==NULL	无此情况	无前驱
!=NULL	前驱为当前结点左子树中序下的最后一个结点	前驱为左子结点

• 通过对树进行一次遍历，在遍历的同时建立线索的连接
• 线索数建立完成之后，可以不使用栈就进行迭代遍历（后序线索树除外）也就是说无法解决求解后序后继的问题
  • 因为后序线索树存在从有节点回到父节点（而这个有节点的度可能为 2，即没有多余位置存储指向父节点的指针）
  • 

森林

• 森林：森林是 m（m≥0）棵树的集合

树的表示与遍历

方式	示意
广义表
双亲表
链表表示
指针节点表示
子女兄弟表示（树的二叉树表示）

• 树的遍历（使用子女兄弟表示法）
  • 先跟次遍历：先访问根节点再依次遍历子树；树的先根遍历结果与其对应二叉树表示的前序遍历结果相同
  • 后跟次遍历：先遍历子树在访问根节点；树的后根遍历结果与其对应二叉树表示的中序遍历结果相同
• （子女兄弟表示下）
  • 没有左节点的是叶子节点
  • 每一个非叶节点对应一个无右节点的节点（这个非叶结点的子节点）
    • 如果是森林还要+1（最后一颗树对应）

森林与二叉树

• 

• 森林的先根次序遍历：先根遍历森林的第一棵子树森林，然后再遍历森林中除第一棵树外其他树组成的森林

  • 对应二叉树的前序遍历
• 森林的后根次序遍历：先访问第一棵子树的根结点的子树森林，然后访问森林的根结点\(r_1\), 然后再遍历森林中除第一棵树外其他树组成的森林
  • 对应二叉树的中序遍历
• 森林的广度优先遍历
  • 先遍历各棵树的根节点
  • 遍历各棵树根结点的所有子女
  • 逐层向下进行遍历

Huffman 树

• 带权路径长度最小的扩充二叉树
• 扩充二叉树
  • 只有度为 2 的内节点和度为 0 的外节点
  • 每个叶节点被赋予一个权值

路径长度

• 内部路径长度 \(IPL\)：各非叶节点到根节点的路径长度之和
• 外部路径长度 \(EPL\)：各叶节点到根节点的路径长度之和
• 路径长度 \(PL=EPL+IPL\)
• 

• 完全二叉树路径长度最小，有 \(PL=\sum^n_{i=1}\lfloor\log_2i\rfloor\)

• \(WPL=\sum_{i=1}^1w_i*l_i\) (权值乘以路径长度(深度))

  • 
• 此外在 Huffman 树中还有 \(WSL\) 等于所有非叶结点（分支节点）权值之和

Huffman 构造算法

• 初始状态：给定 n 个权值 \({w_0,w_1,\cdots,w_{n-1}}\) 构造有 n 棵扩充二叉树的森林 \(F={T_0,\cdots,T_{n-1}}\)，每颗子树都只有一个带特定权值的根节点，左右子树为空（就是有 n 个节点）
• 重复以下，直至剩下一棵树：
• 选择两颗根节点权值最小的扩充二叉树，作为左右子树构造新二叉树，新二叉树根节点的权值为左右子树上根节点的权值之和
• 在 F 中删去两颗二叉树并把新的加入 F

• 

• Huffman 编码

  • 根据字符出现频率决定对字符的编码，使用变长二进制编码（使得编码长度的均值最小）
  • 总编码长度就是表示报文中全部字母需要的二进制位的数目，就是 Huffman 树的带权路径长度 WPL（深度乘以出现频率）
  • CAST CAST SAT AT A TASA
  • 加权频率使用 \(WPL\) 除以频率之和（图中 \(7+5+2+4\)）

图论

• 简单图：无重复边，无自环
• 简单路径：不含重复的边（顶点也不能，因此回路不是）
• 有 n 个节点时：对于无向图，图中一点的最大度为 \(n-1\)；对于有向图为 \(2n-2\)
• 联通分量：极大连通子图

图的存储

• 邻接矩阵

  • 

• 邻接表

  • 

• 邻接多重表

  • 无向图的邻接表表示中，每条边被存储了两遍，浪费空间并且处理较为不便
  • 在邻接表多重表中一条边只有一个节点（只存储一次）
• 无向图
  • 边存储：v1|v2|p1|p2 ：p1, p2 分别指向下一条依附 v1, v2 的边
  • 点结构： data|firstout：firstout 指向依附于该顶点的第一条边的指针
  • 
• 有向图（有的将针对有向图的邻接多重表存储称为十字链表）
  • 点存储：data|firstin|firstout
  • 

图的遍历

活动区间

• 活动区间表示了深度优先搜索的过程，记录每一个从被发现到结束遍历的时间；

• 白路径定理

  • 在深度优先遍历中，v 是 w 的祖先，当今当在遍历过程中法线点 v 时存在一条由 v 到 w 的全部由白色节点组成的路径
  • \(\Rightarrow\) v 是 w 祖先，则存在从 v 到 w 由 TE 边构成的路径，显然当 v 刚被发现时为一条白路径
  • \(\Leftarrow\) 假设路径的长度为 k，假设白路径上第一个不是 v 的后代的带你 x，当遍历到 x 的前驱时 x 为白色（否则就是后代了），而 x 一定是前驱的后代（由归纳假设得到），因而矛盾，x 是 v 的后代

边的类型

边的类型	活动区间要求（边 vw）
TE	active (w) \(\subset\) active (v)
BE	active (v) \(\subset\) active (w)
DE	active (w) \(\subset\) active (x) \(\subset\) active (v)
CE	active (w) < active (v)
- TE 构成了搜索的生成树

• 有向图 dfs
  • 四种边都会出现
• 有向图 bfs
  • TE, BE（黑色邻居，并且是祖先节点）
  • 没有 DE：（只能是 TE）
  • CE：灰色、黑色（不是祖先），跨越两棵树的情况（uv, \(v.dis\leq u.dis+1\)）
• 无向图 dfs
  • TE、BE（只包含子节点指向非直接父节点的祖先节点，因为子节点指向父节点是一种重复遍历）
  • 不含 DE：一定是重复变量（在子节点处已经以 BE 的形式遍历过了），可以通过对 v 的颜色枚举再一一否定
  • 不含 CE：无向图中不可能有两点之间有边但是没有父子关系（对方白显然有关系；对方黑不可能，一定是重复遍历）
• 无向图 bfs
  • TE，CE（灰）(\(v.dis=u.dis\mid\mid v.dis=u.dis+1\) 因为只能是灰点，由于队列中灰点最大差 1 造成范围比有向图更加具体)
  • 无 BE，DE

BFS 就是最短距离

• 想要证明 \(d(s,v)=v.dis\)，d 表示真实的最短距离，dis 为 bfs 过程中求出的最短距离
• 对于任意边 \(uv\) 有 \(d(s,v)\leq s(s,u)+1\)
• 从节点 \(s\) 开始广度优先遍历，在遍历结束时有 \(v.dis\geq d(s,v)\)
  • 使用数学归纳法说明：初始情况是队列执行第一个操作，将源点 s 放入到队列 \(s.dis=d(s,s)=0\) 初始情况下成立；
  • 当一个新节点加入时有 \(v.dis=u.dis+1\geq d(s,u)+1\geq d(s,v)\) 得证
• 队列中的元素 \(<v_{1}\dots v_{r}>\) 有 \(v_{i}.dis\leq v_{i+1}.dis(1\leq i\leq r-1)\)，\(v_{r}.dis\leq v_{1}.dis+1\)
  • 使用数学归纳法：初始时只有源点 s 显然成立
  • 假设队头元素 \(v_{1}\) 出队，\(v_{2}\) 成为新的队头元素，有归纳假设得到 \(v_{r}\leq v_{1}.dis+1\leq v_{2.dis+1}\) 即保持成立
  • 当 \(V_{r+1}\) 入队，一定有 \(v_{r+1}.dis=u.dis+1\)，\(u\) 为刚刚取出正在处理的队首元素 \(u.dis\leq v_{1}.dis\)，所以 \(v_{r+1}.dis\leq v_{1}.dis+1\)，同样对与上一个队尾 \(v_{r}\leq u.dis+1=v_{r+1}dis\)
• 最后证明有 \(v.dis=d(s.v)\)，且从 s 到 v 的 TE 组成的路径就是最短路径
  • 假设存在点的 dis 不等于 d，取其中与 s 最近的点 v
  • 考察 s 到 v 的路径，记 u 为路径上 v 前面的点，即 \(d(s,v)=1+d(s+u)\) 且 \(u.dis=d(s.u)\)，那么就是说 \(v.dis>d(s,v)=u.dis+1\)
  • 考察 u 刚刚出队的情况，如果 v 为白色，则 \(v.dis=u.dis+1\) 矛盾；v 为灰色，假设是作为 w 的邻居放入，那么 \(v.dis=w.dis+1\)，但是由于 w 比 u 先离开队列，因此也有 \(v.dis\leq u.dis+1\) 矛盾；如果 v 为黑色，显然矛盾；

有向图算法

拓扑排序

• 排序之后的符号假设为 \(t_{1}\dots t_{n}\)
• 如果存在有向边 \(i\to j\) 则有 \(t_{i}<t_{j}\) (反之是逆拓扑排序)
• 如果有环则不存在拓扑排序，如果为 DAG 则必然存在拓扑排序

SCC 强联通分量

• 强联通：对于一对顶点 v, w 从 v 到 w 和从 w 到 v 之间都有路径；如果图中任意两点都是强联通的，那么为强连通图（n 个点的强连通图至少 n 个边，即一个环）
• 收缩图：将图中的强连通分量缩为一个点，得到一个 DAG
• 难点：如何限制搜索在一个强联通分量内部（这样就能正好获得一个强连通分量的内容）？像拓扑排序那样，从出度为 0 的 DAG 开始，这样保证被限制在自己的强连通分量内部
• 基本过程
  • 先进行第一轮遍历，在每个节点遍历结束时入栈
  • 计算得到转置图，从栈中取出节点进行二轮遍历，并标记强连通分量
  • 

下面进行正确性证明 - 第一轮遍历中每个强连通分量第一个被发现的点为该强连通分量的首节点；并且具有一下性质：是一个强连通分量中第一个被发现的，同时也是最后一个结束遍历的（即包含了同一个强联通片中其他所有节点的活动区间） - 遍历到首节点时不可能有从首节点通往某个灰色点的路径：否则有一个环，即在同一个强连通分量，矛盾 - 设 l 为一个强连通分量的首节点，x 为另一个强连通分量中的节点，并且存在 l 通向 x 的路径，则 x 会比 l 先结束遍历（入栈）。由上一条已经知道了只能为黑色或者白色，黑色时显然成立；白色时则应该存在一条白路径（不会有黑，因为不可能有黑点指向白点），即为后代，同样得证 - 在第二轮遍历中，一个白色节点被 pop 出来时，一定是所在强连通分量的首节点（因为在第一轮遍历时最后结束，即最后入栈） - 每次出栈一个首节点，对强连通分量所有点进行遍历，可以标记整个强连通分量；并且不会错误的多遍历其他强联通分量中的节点，假设第二轮遍历中到达一个节点 l，对于另一个强连通分量的首节点 x，\(G^T\) 中有 l 到 x 的路径，由上面的引理知道 l 比 x 先完成遍历，因此 l 不会错误的将其他强连通分量加入到该强联通分量

无向图算法

Tarjan 算法

• 容错连通：
  • k-点连通：去除任意 k-1 个点后仍然连通
  • k-边联通：去掉任意 k-1 个点后仍然连通
• 对于联通的无向图 G（下面两种都不是 2-连通）
  • 割点 v：去掉点 u 之后，图 G 不再连通
  • 桥 uv：去掉 uv 之后，图 G 不再连通

求解割点 - 另一种定义：点 v 为割点，当且仅当存在 wx，点 v 出现在 w 和 x 之间的所有路径上 - 进一步，对于点 v（跟除外）为割点当仅 v 的某个子树没有 BE 指向 v 的祖先 - \(\Leftarrow\) 显然 - \(\Rightarrow\) 假设 v 为割点，对于两个点 xy 满足 xy 所有路径都经过 v，那么这两个点至少有一个点是 v 的后继节点（否则删除 v 这两个点一定还联通）；对于没有 BE 向上，同样使用反证（那样删除了 v 也还是有路径） - 基本过程 - v 被首次发现时 \(v.back=v.discovertime\) - 遍历过程中发现从 v 指向 w 的 BE \(v.back=min\{v.back,w.discovertime\}\) - 为什么不用w.back，因为是依靠 w 继续向上（如果 w 是割点呢？不应该这么做） - 发现从 v 指向 w 的 TE \(v.back=min\{v.back,w.back\}\) - 如果 \(w.back\geq v.discovertime\) 则说明 v 是一个割点

求解桥 - 对求解割点的算法稍加修改 - 只需要修改条件为 \(v.back>u.discovertime\) - 因为删除边 uv，\(=\) 时可以跳回到 \(u\)，这不是桥

二分图判断

• 二分图：存在顶点的划分 \(V_{1}\bigcap V_{2}=\phi,V_{1}\bigcup V_{2}=V\) 并且对于任意一条边有一个点在 \(V_{1}\) 另一个点在 \(V_{2}\)
• 二分图是可以二着色的（用两种颜色染色，并且是的边两个顶点的颜色不同）
• 从任一点出发，将所有相邻点染为不同的颜色，如果相邻点不是白点，并且两边颜色相同则说明不是二分图

k 度子图

• G 的子图 H 的每一个顶点的度都不低于 k
• 先扫买图中所有的点，检查是否有度小于 k 的点，将这些点和对应的边删除，如果删除导致了新的 yipi 节点度小于 k，就需要继续进行删除（这个过程与使用 bfs 实现拓扑排序是类似的）

最小生成树

• 生成树：T 是 G 的生成树，当今当 T 包含 G 中所有顶点并且 T 是连通无环图（树）

• 最小生成树（直接定义）：T 是 G 的生成树，并且图中不存在任何其他比 T 权更小的生成树

  • 间接定义（最小生成树性质）：对任意不在 T 中的边 e，\(T\bigcup\{e\}\) 含有一个环，并且 e 是环中权值最大的边。下面对定义的等价性进行说明：
  • 所有满足最小生成树性质的生成树都具有相同的权值：假设 \(T_{1},T_{2}\) 都满足最小生生成树性质，对其之间边的差异数目 k 做归纳。\(k=0\) 显然权值相同，归纳假设对于 \(0\leq j<k\) 都有相同权值，假设不同时在 \(T_{1},T_{2}\) 中的边最小的为 \(uv\) （假设在 \(T_2\) ），\(T_{1}\) 中也一定有一条连接 uv 的路径（长度>1）并且这条路径上存在不在 \(T_{2}\) 中的边 \(w_{i}w_{i+1}\)，\(uv.weight\leq w_i w_{i+1}.weight\) 这是因为前面已经说了 \(uv\) 是最短边；\(uv.weight\geq w_i w_{i+1}.weight\) 将 \(uv\) 加入到 \(T_{1}\) 生成了环，有最小生成树性质成立，由此可以通过递归进行边替换（也就是说可以通过删除、加上边从一个生成树转化为另一个，也就是具有相同的权值）
  • T 是最小生成树，当仅当 T 具有最小生成树性质：假设最小生成树不满组最小生成树性质，那么显然存在 \(e\)，将 e 加入到最小生成树并删除环上的另一条边就可以使得权值更小，矛盾；前面已经说明了最小生成树一定具有最小生成树性质，那么所有具有最小生成树性质的权值相同，就是说都是最小生成树

• 对于不连通图，每个连通片的最小生成树组成最小生成森林

Prim

• 将最小生成树问题分解：
  • 构建生成树，从任意节点出发，不断发现新节点，添加到生成树，直至包含所有节点
  • 保证生成树的权值最小，总是贪心的选择权值最小的边加入
• 过程
  • 从任一节点开始，比如先选中 a（a 就构成了目前的最小生成树），现在候选点就是 a 的邻居
  • 从所有邻居中选出最短的边，并将对应的点加入集合，重复直到所有点加入
• 复杂度分析
  • \(T(n,m)=O(nC_{min}+nC_{insert}+mC_{decrease})\)
  • 数组实现 \(O(n^2+m)\)
  • 堆实现 \(O((n+m)\log n)\)

正确性证明 - 根据生成树的规模对 prim 的阶段进行划分（有 i 个点就对应阶段 \(T^{(i)}\)）\(T^{(1)}\dots T^{(n)}\)，可以依此做归纳证明（说明 Prim 算法总是能得到最小生成树） - 初始情况 \(T^{(1)}\) 显然是最小生成树，现在证明 \(T^{(k)}\) 的情况，这是由 \(T^{(k-1)}\) 添加一条边和一个点转移来的（记为 \(v\) 和 \(u_{1}v\)） - 考虑像 \(T^{(k)}\) 中加入一条边，如果边的两个端点都在 \(T^{(k-1)}\) 显然是满足最小生成树性质的，因此只看一个顶点是新加入的 \(v\) 的边。（证明是不是仍然满足最小生成树性质） - - 根据贪心选择，一定有 \(u_{1}v\leq vu_{1},\dots,vu_{i}\)，现在尝试加入一条边 \(vu_{i}\) 形成环，需要证明这条边就是环上权值最大的边 - 假设从 v 出发，顺时针遇到第一条权值更大的边 \(w_{a}w_{a+1}\) 逆时针遇到 \(w_{b-1}w_{b}\) (不排除这两条边是同一个)假设 \(w_{a}\) 更先加入生成树，由于 prim 每次优先选择更小的边，因此 \(v\) 会比 \(w_b\) 更先加入，这就与 \(w_{b}\) 位于 \(T^{(k-1)}\) 而 \(v\) 是新加入的点矛盾，由此证明一定满足最小生成树性质

Kruskal

• 将边按照权值从小到大排列，依次选择边加入，使用并查集保证边两端不在同一个连通分量（防止成环），为了使用数学归纳法证明，可以使用类似的阶段划分思路 \(T^{(1)}\dots T^{(n)}\)
• 时间复杂度分析
  • 需要对边进行排序，时间复杂度为 \(O(m\log m)\)

正确性说明： - 要证明的不变式是 kruskal 算法得到的局部生成森林 \(T^{(k)}\) 总是最小生成森林（被包含在某个最小生成树中 \(T\)），进行说明 - 假设 \(T^{(k)}=T^{(k-1)}\bigcup\{e\}\) ，若 \(e\in T\) 则 \(F^{(k)}\subseteq T\)，先假设 \(e\notin T\)，那么 \(T\bigcup \{e\}\) 有环，下面证明一定有 \(e'\) 与 \(e\) 的权值相同 - 由于 T 是最小生成树，一定有 \(e'.weight\leq e.weight\) ；又由于 kruskal 贪心原则 \(T-T^{(k-1)}\) 每一条边的权值均不小于 \(e\)，所以环上必然有一个 \(e'.weight\geq e.weight\)；即 \(e'.weight=e.weight\) - 因此可以通过调换边转化，即说明 \(F^{(k)}\) 一定包含在某个最小生成树中，得证

最短路径算法

Dijkstra

• Dijstra 只能处理没有负边的情况（不要求 DAG，DAG 有更简单的线性算法（拓扑排序计算））

• 复杂度说明

  • \(T(n,m)=O(nC_{min}+nC_{insert}+mC_{decrease})\)
  • 使用数组实现：\(O(n^2+m)\)
  • 使用堆是实现：\(O((m+n)\log n)\)

正确性证明 - 同样划分为 n 个阶段：\(T^{(1)}\dots T^{(n)}\) - - 阴影部分已经完成计算（归纳假设），现在要证明 \(s\to y\to z\) 就是 s 到 z 的最短路径。假设存在更短路 \(p_{2}.weight<p_{1}.weight\) 假设 p2 在 \(z_{a-1}\) 离开阴影区域，阴影外第一个点为 \(z_{a}\) - 由于 dijkstra 总是选最小，因此有 \((s\to z_{a-1}\to z_{a}).weight\geq(s\to y\to z).weight\), 并且有 \((z_{a}\to z).weight\geq 0\) （这就是为什么要求所有边非负）所以 \(p_{2}.weight\geq p_{1}.weight\) 矛盾

Floyd

• 二元关系 E 的的传递闭包 R 定义为定义为：\(v_iRv_{j}\) 当今当存在从 \(v_{i}\) 到 \(v_{j}\) 的路径，初始时为邻居关系，经过传递闭包得到可达关系
  • 即如果有 \(a\to b 和 b\to c\) 那么就添加边 \(a\to c\)
  • 不断添加边知道没有可以新加入的边
• 最初的 \(O(n^4)\) 的算法思想，四层循环
  • 边的长度；u；v；k
  • 为什么要有边的长度：因为计算一条特定长度的边是否存在时，需要知道依赖的更短的边是否存在，因此按照从小到大的顺序进行计算。
  • 为什么不直接存最小值？上面的顺序无法通过这样得到正确结果（保证不了遍历的顺序）
• 优化的 \(O(n^3)\)
  • k, i, j
  • 每次添加一个新的中继节点
  • \(d(i,j,k)=min(d(i,j,k-1),d(i,k,k-1),d(k,j,k-1))\)
  • 总的来说使用特殊的调度：\(T^{(k)}\) 表示使用前 \(k\) 个点作为中继得到的最短路径，逐渐加入全部点可作为中继，得到结果

最小生成树贪心框架 MCE

• 切：顶点集合的一个划分构成图的一个切（类似于二分图那样）

• MCE 跨越切的最小权值边：针对 G 的某个切，将边分为跨越切的边和切内部的边

• 对于边 \(e\) 如果有一个切使得 \(e\) 成为切的 MCE，那么 e 一定属于某一棵最小生成树

  • 假设 e 是一条 MCE 对应切 \(V_{1},V_{2}\)，但是不属于任何最小生成树，对于最小生成树 T，假设 \(e'\) 是 T 中跨越切的边
  • 现在将 e 加入最小生成树，得到环，一定有 \(e.weight\geq e'.weight\)
  • 又由于 e 和 e‘都是跨越切的边，并且 e 是 MCE，所以又有 \(e.weight\leq e'.weight\)，因此可以替换，\(e\) 一定属于某些最小生成树

• 解释 prim 算法

  • 在 \(T^{(k-1)}\) 时记节点为 \(V_{1}\)，与剩余节点 \(V_{2}=V-V_{1}\) 就构成了一个切。
  • 由于 prim 总是选择切之间的边，因此不会形成环，并且总是选择 MCE，因此总是能得到最小生成树

• 解释 kruskal 算法

  • 假设已经完成了 \(T^{(k-1)}\) 阶段，算法要选出剩下的边种权值最小且不成环的边 \(uv\)，一定可以构造一个切使得其为 MCE
  • 将 u 分给 \(V_{1}\)，v 分给 \(V_{2}\)，将所有和 u 联通的点分到 \(V_{1}\) 剩下随便（但是联通点分配到同一个）如果存在 u-v 的路径，这个分配是无法实现的，保证无环

贪心搜索框架 BestFS

• 在途中贪心的搜搜哦某种最优结构，将点分为三类
  • Fresh：贪心搜索还没有涉及的点
  • Fringe：进行贪心选择的所有候选节点
  • Finished：已完成贪心搜索，后序无需继续处理
  • 
• BestFS 总是从某个节点出发，处理完自己之后，通过相邻的边搜索相邻点，搜集信息，将点添加到 Fringe，随着贪心进行，不断从 Fringe 中选出最优点加入到 Finished（还需要更新这个点相邻点的信息）
• 类似于一个广度优先遍历，使用优先队列最为调度器

活动网络

• 首先要先判断是否存在有向环，如果出现了，则意味着无解

AOV 网络

• 给出可行的执行顺序，直接使用拓扑排序即可
• 

AOE 网络

• 有向边表示一个工程中的活动，边上的权值表示持续时间，顶点表示事件，求解完成全部任务需要的最少时间

• 只有一个开始点和一个完成点，开始点为源点，结束点为汇点；完成整个任务的时间就取决于从源点到汇点的最长路径（关键路径），路径上的活动都是关键活动

• \(Ve(i)\) 表示事件的最早开始时间（就是最长路径的长度）

• \(Vl(i)\) 保证最终任务按时完成的前提下事件的最迟开始时间
• \(Ae(k)\) 表示活动最早可能开始的时间
  • \(<V_i,V_j>\) 边有 \(Ae[k]=Ve[i]\)
• \(Al(k)\) 活动最迟开始时间
  • \(Al[k]=Vl[j]-dur<i,j>\)
• 对于 \(Al[k]=Ae[k]\) 的就是关键活动
• 先在正图和反图分别求解 \(Ve \ Vl\)
  • \(Ve[j]=max(Ve[i]+dur<V_i,V_j>)\)
  • 对于汇点有 \(Vl=Ve\)
  • \(Vl[j]=min(Vl[k]-dur<V_i,V_j>)\)
• 由此得到 \(Ae \ Al\) 进一步得到关键路径
• 

查找数据结构

• 静态搜索结构：插入删除前后搜索结构不发生变化
• 动态环境：插入删除操作后搜索结构自动进行调整（以保持较高的搜索效率）

集合

• 集合是成员的一个集群，集合中的成员可以是原子，也可以是集合，不过需要有相同的数据类型
• 集合中的元素一般是无序的，但是通常便于插入和查找
• 可以使用位向量（01）表示，针对有限种类
• 也可以直接使用数组、链表来表示

字典

字典的顺序表示

• 字典保存在线性序列中，关键码从左到右依次增大，可以使用有序顺序表或有序链表，通过顺序查找/二分查找
• 判定树描述查找
  • 搜索成功时停在内结点，搜索失败时停在外结点
  • 
  • 

哈希表（散列表）

• 不经过比较，一次直接从字典中得到搜索元素

• 在元素存储位置与其关键码之间建立一个确定的对应函数关系 Hash ()，使得每个关键码与唯一的存储位置相对应 Address ＝ Hash(key)

  • 存放、搜索时均使用相同的哈希函数进行位置的计算

• 同义词：具有不同键但是经过哈希函数之后得到相同哈希值的元素（被映射到相同位置），这些元素造成了哈希冲突

• 堆积现象：堆积是指在哈希表中连续的槽位被占用的现象，这种情况在使用开放地址法处理哈希冲突时尤为明显。当多个元素通过哈希函数映射到相邻的位置时，会形成一种称为“堆积”的效应，这会影响哈希表的查找效率，因为它增加了查找时可能需要探测的槽位数量。
  • 主要原因：冲突解决不当

哈希函数

• 要求

  • 简单，快速计算结果
  • 定义域存储全部关键码
  • 计算出来的地址应该能均匀分布在整个地址空间

• 直接定地址

  • 取关键码的线性函数值为散列地址 \(Hash(key)=a*key+b\)
  • 本质上就是一个数组了
• 数字分析
  • 设有 n 个 d 位数, 每一位可能有 r 种不同的符号。这 r 种不同符号在各位上出现的频率不一定相同。根据散列表的大小, 选取其中各种符号分布均匀的若干位作为散列地址。
• 除留余数
  • 设散列表中允许地址数为 m，取一个不大于 m，但最接近于或等于 m 的质数 p 作为除数 \(hash(key)=key\%p \ p<=m\)
• 平方取中法
  • 首先计算构成关键码的标识符的内码的平方, 然后按照散列表的大小取中间的若干位作为散列地址
• 折叠法
  • 把关键码自左到右分成位数相等的几部分, 每一部分的位数应与散列表地址位数相同, 只有最后一部分的位数可以短一些。把这些部分的数据叠加起来, 就可以得到具有该关键码的记录的散列地址。（蛇形叠加）

哈希表的冲突处理

• 复杂因子 \(\alpha=\frac{n}{m}\)

开放寻址方式：线性探查 - 发生冲突时顺次查找（注意线性探测需要在到达数组末尾时回到数组开头） - - 搜索成功时的平均搜索长度：实际位置-散列位置+1 - - 搜索不成功时的平均搜索长度：从什么位置开始搜索直到末尾空白（要小心的是如果货容量大于%可以到达的范围，不要把后面加上来！因为不能直接通过哈希到达） - - 不成功查找的时间复杂度 \(O\left( \frac{1}{1-\alpha} \right)\) - 连续探测不少于（下面只乘了前面成立的，没有说后面就不连续了） i 次的概率为 \(\frac{n}{m}\cdot{\frac {{n-1}} {m-1}}\cdots{\frac{{n-i+2}}{m-i+2}}\leq\left( \frac{n}{m} \right)^{i-1}=\alpha^{i-1}\) - \(E[x]=\sum^\infty_{i=0}i \ Pr\{x=i\}=\sum^\infty_{i=0}i(Pr\{X\geq i\}-Pr\{X\geq i+1\})\) - \(=\sum^\infty_{i=1}\alpha^i=\frac{1}{{\alpha}}\) - 成功查找的时间复杂度 \(O(\frac{1}{\alpha}\ln {\frac{1}{1-\alpha}})\) - 查找 \(x_{i+1}\) 成功就是在插入 \(x_{i-1}\) 后查找失败（此时 \(x_{i}\) 刚好还没有被插入） - \(T_{s}(m,n)=\frac{1}{n}\sum^{n-1}_{i=0}{\frac{m}{m-i}}=\frac{1}{\alpha}\sum^m_{i=m-n+1}{\frac{1}{i}}\) - \(\leq \frac{1}{\alpha}\int \frac{1}{x} \, dx=\frac{1}{\alpha}\ln{\frac{1}{1-\alpha}}\) - 其他探测方式 - 平方探测法：\(d_{i}=1^2,-1^2,2^2,-2^2\dots\) 不能探测到所有的位置，但是至少一半 - 双散列法：\(d_{i}=i*Hash_{2}(key)\) - 伪随机序列法 \(d_i\) 是一个为随机数序列 - 注意：删除时只是把这个位置打上一个删除标志，探测时跳过（但是还要继续），添加时可以添加到这个格子

闭地址法：（链地址法） - 具有相同地址的关键码归于同一子集，通过一个单链表链接起来，称为一个桶 - - 一次不成功的查找（含插入）的时间复杂度为 \(O(1+\alpha)\) - 完整遍历一个链表，长度期望为 \(\alpha\) 复杂度显然 - 一次成功的查找（含删除）同样为 \(O(1+\alpha)\) - 每个元素被查找的概率为 \(\frac{1}{n}\)，考虑哈希表建立的过程，所有在 \(x_{i}\) 后面插入的元素都可能在链表中排在前面 - \(T_{s}(m,n)=\frac{1}{n}\sum^n_{i=1}\left( 1+\sum^n_{j=i+1}{\frac{1}{m}} \right)\) - \(=1+\frac{1}{nm}\sum^n_{i=1}(m-i)=1+\frac{n-1}{2m}=O(1+\alpha)\)

并查集

• 并查集的操作：并（合并等价类），查（查询所在等价类）
• 无优化的"并查集"：最差时退化为链，查询的时间复杂度为 \(O(n)\)
• 按秩合并
  • 包含 k 个节点的数，高度不会超过 \(\log \lfloor k \rfloor\)
    • 数学归纳法，设待合并的两颗子树分别有 \(k_{1},k_{2}\) 个节点，高度为 \(h_{1},h_{2}\) ，不放设 \(k_{1}\geq k_{2}\) 那么 \(h=max(h_{1},h_{2}+1)\)，有 \(h_{1}\leq \lfloor \log k_{1} \rfloor\leq \lfloor \log k \rfloor\) 并且 \(h_{2}+1\leq \lfloor \log k_{2} \rfloor+1\leq \left\lfloor \log \frac{k}{2} \right\rfloor+1\leq \lfloor \log k \rfloor\)
  • 采用这种方案，对于 n 个元素进行 l 次操作，时间复杂度为 \(O(n+l\log n)\)
• 按秩合并+路径压缩->并查集
  • 最坏时间复杂度 \(O((n+l)\log^*n)\to O(n+l)\)
  • 超指数函数 \(H(n)=2^{H(n-1)} 对于n>0\)，如 \(H(5)=2^{2^{2^{2^2}}}\)
  • \(log*(j)=min(i|H(i)\geq j)\)

搜索树

二叉搜索树

• 定义：二叉搜索树或者是一棵空树，或者是具有下列性质的二叉树
• 每个结点都有一个作为搜索依据的关键码 (key)，所有结点的关键码互不相同。
• 左子树（如果非空）上所有结点的关键码都小于根结点的关键码。

• 右子树（如果非空）上所有结点的关键码都大于根结点的关键码。

• 二叉搜索树的数目：

  • 给定元素，二叉搜索树的中序遍历固定，二叉树的种类数目就是可能的前序遍历的数目
  • 这是一个卡特兰数 \(\frac{C_{2n}^n}{n+1}\)
  • 假设根节点在中序遍历中的 \(i\) 位置，那么就有 \(f(n)=\sum_{i=1}^nf(i-1)f(n-i)\) 即根节点确定，递归求解左右子树的数目，符合卡特兰数

• 插入元素

  • 先进行搜索，都多不成功到达的位置就是要插入的位置
  • 

• 删除元素

  • 叶节点直接删除
  • 被删结点右子树为空，可以拿它的左子女结点顶替它的位置，再释放它。
  • 被删结点左子树为空，可以拿它的右子女结点顶替它的位置，再释放它。
  • 被删结点左、右子树都不为空，可以在它的右子树中寻找中序下的第一个结点 (关键码最小), (左子树最后一个即)用它的值填补到被删结点中，再来处理这个结点的删除问题。(因为这个节点一定有一个子节点为空，因此对他的修复很快)
  • 

• 搜索的效率与是否平衡相关

红黑树

• 红黑树 RBT 定义：根节点为黑色节点，并且深度为 0。非根节点的黑色深度为从根节点到这个节点路径上黑色节点的数目。所有叶节点（叶节点都是黑色）的黑色深度相同，此外红色节点不能连续出现
• 对于根节点为红色但是满足其他条件的为准红黑树 ARB
• 红色节点就是用于平衡在维护树更平衡和维护的开销，即将不平衡限制在一定程度内

• 红黑树的递归定义

  • 一个黑色节点构成 \(RB_0\)
  • 对于 \(ARB_{h}\)，根节点为红色，左右子树为 \(RB_{h-1}\)
  • \(RB_{h}\) 根节点为黑色，左右子树为 \(RB_{h-1}\) 或 \(ARB_{h}\)

• 红黑树的性质

  • 对于 \(RB_{h}\) 有不少于 \(2^h-1\) 个内部黑色节点；不超过 \(4^h-1\) 个内部节点
  • 对于 \(ARB_{h}\) 有不少于 \(2^h-2\) 个内部黑色节点不超过 \(\frac{1}{2}4^h-1\) 个内部节点

• 红黑树的普通高度不会超过 \(2\log(n+1)\) 即任何黑色节点的普通高度至多是其黑色高度的二倍;增删改查的代价为 \(O(\log n)\)

• 插入

  • 四点模式：为了不概念黑色深度，插入的的点为红色节点，四点即三红一黑有两个红色节点相邻，通过将红黑节点调换（红节点上升至上一层），可能无法在局部解决
  • 三点模式：通过旋转，可以在局部解决

• 删除

  • 与右子树最左点（中序遍历下后继元素）进行调换，转化为此节点的删除
  • 黑->红：砍掉另一半，无法局部完成，灰点上升
  • 红->黑：修复灰点，局部完成

AVL 树 (平衡二叉树)

• 与红黑树相比，AVL 对平衡的要求更高，保证了树的高度以及搜索效率，但是调整更为频繁复杂，维护开销较大

  • 因此 AVL 树更适用于查找操作较多的系统，红黑树更适应插入和删除操作

• AVL 树：或者是空树，或者满足左右子树都是 AVL 树，并且高度差绝对值不超过 1

• 平衡因子：右子树的高度减去左子树的高度所得的高度差（-1,0,1）

• 关键字个数为 \(n=2^k-1\) 时平衡二叉树一定为满二叉树

• AVL 数目的高度与节点数目

  • \(n_{i}\) 表示高度为 \(i\) 的 AVL 树的最少节点数目 \(n_{0}=0,n_{1}=1,n_{2}=2\dots n_{h}=1+n_{h-1}+n_{h-2}\)
  • 对于求解平衡树可能的种类数目也可以用类似的的递推思想

• 旋转操作：插入或者删除后可能造成不平衡，需要通过旋转进行调整

  • 左单旋转
  • 右单旋转
  • 先左后右：先进行一次旋转将不平衡转移到左右两侧
  • 先右后左
• 插入元素：
  • 在插入新结点后（向二叉搜索树那样进行失败的查询后在原位置进行插入），需从插入结点沿通向根的路径向上回溯。如果在某一结点发现高度不平衡，停止回溯。从发生不平衡的结点起，沿刚才回溯的路径取直接下两层的结点。
  • 如果这三个结点处于一条直线上，则采用单旋转进行平衡化。单旋转可按其方向分为左单旋转和右单旋转。如果这三个结点处于一条折线上，则采用双旋转进行平衡化。双旋转分为先左后右和先右后左两类。
  • 插入新结点并修改 pr 的平衡因子值后，pr 的平衡因子值有三种情况：
  • 结点 pr 的平衡因子为 0：什么也不需要做（说明向矮的树插入），树的高度不发生变化
  • \(|bf|=1\): 说明插入前 pr 的平衡因子是 0，不需要旋转，但是子树高度加一，需要继续考察双亲节点的平衡状态
  • \(bf=-2\)
  • \(bf=2\)
  • 
• 删除元素：同样先做删除，删除之后还要进行维护
  • 被删除节点没有子女：直接删除，并将双亲指针置 NULL，父节点子树高度减一
  • 只有一个子女：双亲指针指向这个子女，父节点子树高度减一
  • 有两个子女：搜索被删除节点 x 中序下的直接前驱 y (或后驱)把 y 传送到 x ，之后再删除 y
  • 删除之后的维护：（沿结点 x 的父结点通向根的路径反向追踪高度的变化对路径上各个结点的影响）
  • 用 shorter（一个 bool 变量）指明子树高度是否缩短，初始为 True，在向上遍历检查中，如果 shorter 编程 false 算法终止（影响不会再向上传递了），否则要进行检查及操作
  • 若节点的 bf 为 0，则有一个子树缩短，bf 变为-1/1，但是 shorter 为 false，停止向上
  • 若 bf 不为 0 且较高的子树被缩短。则 p 的 bf 改为 0，同时 shorter 置为 True。还要继续检查上层结点的平衡因子。
  • 结点 p 的 bf 不为 0，且较矮的子树又被缩短。则在结点 p 发生不平衡（bf 变成-2/2）。需要进行平衡化旋转来恢复平衡。
    • 如果 q（较高的子树）的 bf 为 0，执行一个单旋转来恢复结点 p 的平衡，置 shorter 为 False。无需检查上层结点的平衡因子。
    • 如果 q 的 bf 与 p 的 bf 同号，则执行一个单旋转来恢复平衡，结点 p 和 q 的 bf 均改为 0，同时置 shorter 为 True。还要继续检查上层结点的平衡因子。
    • 如果 p 与 q 的 bf 相反，则执行一个双旋转来恢复平衡。新根结点的 bf 置为 0，其他结点的 bf 相应处理，同时置 shorter 为 True。还要继续检查上层结点的平衡因子。
  • 

算法思想

动态规划与贪心

• 动态规划的关键
  • 重叠子问题：动态规划的基本动机就是减少子问题的重复计算
  • 蛮力找最优：动态规划本质是一种"蛮力"，从所有情况中找到最优解
  • 最优子结构：从子问题得到大问题，这就要求大问题的最优解必须是由小问题的最优解组合得到
  • 无后效性：一旦某个阶段的最优状态决定之后，这个阶段的决策不会再影响之后阶段的决策，即后续的决策只基于后续的状态，而与之前的状态无关（确保子问题相互独立，不需要考虑子问题之间的交互影响）
• 贪心算法的关键
  • 局部最优：每一步都选择当前看起来最优的选择
  • 通常使用数学归纳法或交换验证法证明
• 动态规划算法与贪心的区别
  • 动态规划是一种递归解决问题的方法，它将问题分解为重叠的子问题，并通过保存这些子问题的解来避免重复计算，这种技术称为"记忆化"。动态规划通常用于解决具有明确阶段、每阶段有多个状态，并且每个状态都是由上一个阶段的状态转移而来的问题。
  • 心算法采用一种局部最优化的策略，每一步都选择当前看起来最优的选择，希望通过局部最优达到全局最优。贪心算法通常更简单、更快，但它并不总是得到全局最优解。

分治算法

CDQ 分治

• 基本思想：分别计算左串和右串的共享，然后进行合并（计算跨越中介的贡献）

• 寻找常见项元素（找出出现次数大于 n/k）

  • 将原始数组分为左右两半，在数组中出现次数大于 n/k 的元素，一定会在其中一半出现次数大于 n/2k
  • 这样的元素就作为一半数组的候选元素，用于传递给下一层进行检查合并
  • 每次合并遍历整个数组（左右两半）检查候选元素是否还符合条件（每次要求数目*2）
  • 最后可能还需要对结果去重

• 偏序问题，给定许多点，查找多少个点（x, y）满足不存在点使得 (x<x'&&y<y')

  • 首先对 x 排序，然后在左一半和右一半分别处理（标记不符合的点）
  • 然后对左边和右边分别对 y 进行排序，计算跨越贡献（当今当左边一个点的 y 大于右边 y 最大值时这个点才可能是候选）
  • 最后整理没有被标记的点并进行计数

• 平面内有多个点，求解最近距离

  • 分治（假设左右划分）：统计左边最近点对，右边最近点对，以及左边一点与右边一点的点对（这个是核心）
  • 设 \(D=min(D_{l},D_{r})\) 即左右得到的距离最小值，
  • 对左边每一个点构建一个宽为 \(D\)，长度为 \(2D\) 的矩形框（只需要判断这个氛围内对面点的距离）
  • 这个框内不可能不会有太多点的，实际上最多只能 6 个（划分为 6 块，鸽笼原理证明）

• 基于归并排序的逆序对计数

  • 将一个数组分成两部分，逆序分为一下几种类型：全部在左侧；全部在右侧；一个在左侧一个在右侧。前两种通过子问题求解，第三种可以在合并时进行计数
  • 对于左边一个元素，右边能和它组成逆序对的元素就是比它更小的元素数目，这在合并过程中很容易获得（或者也可以理解成左边所有剩下元素都和右边这个元素形成逆序对）
  • 如果想要原地算法，可以在合并时使用快速排序，不过复杂度就是 \(O(b\log^2 n)\) 了

其他

• 摩尔投票法：用于寻找数组中出现次数超过一半的元素（多数元素）

  • 初始选定第一个元素作为候选元素，并设置一个计数器 count（1）
  • 遍历数组，如果元素等于候选元素，那么 count+1；否则-1，如果变为 0 说明候选元素被抵消了，选择当前遍历到的元素作为新的候选元素，并将 count 设置为 1
  • 遍历结束后的候选元素还要进行检查，如果出现次数大于 n/2 那么就找到了多数元素

• 两个有序数组找中位数

  • 扩展为找第 \(k\) 大的元素，那么比较 \(arr_{1}\left[ \frac{k}{2} \right],arr_{2}\left[ \frac{k}{2} \right]\)，小的那一半可以直接去掉（一定不包含第 k 大的元素），之后对 \(k\) 进行更新（减去去掉的元素）
  • 即每次能去掉一半的元素，时间复杂度接近 \(\log k\)

• 权值中位数

  • 一个数组（无序），每个数有一个权值，求解权值中位数 (\(\sum_{x_{i}\leq x_{k}}w_{i}\leq \frac{1}{2}\))
  • \(O(n)\) 时间求出中位数，之后进行 partition 并求出两边的权值和，较小的那一边应该舍去，并把其权值和加到中位数上

• 大数乘法

  • 将输入的整数均匀划分为，那么原式就转化为了 \(xy=(x_{1}2^{n/2}+x_{0})(y_{2}^{n/2}+y_{0})\)
  • 即 \(x_{1}y_{1}2^n+(x_{1}y_{0}+x_{0}y_{1})2^{n/2}+x_{0}y_{0}\) 成功将问题转化为子问题，复杂度为 \(W(n)\leq 4W\left( \frac{n}{2} \right)+O(n)=O(n^2)\) 没有任何优化
  • 进一步转化 \(x_{1}y_{1}2^n+(p-x_{1}y_{1}-x_{0}y_{0})2^{n/2}+x_{0}y_{0}\)
  • 其中 \(p=((x_{1}+x_{0})(y_{1})+y_{0})\)
  • 复杂度为 \(W(n)\leq 3W\left( \frac{n}{2} \right)+O(n)=O(n^{\log_{2}3})\)

算法正确性与复杂度分析

决策树

• 决策树用于求解问题下限（但是并不紧）

对手论证（选择问题引出）

• 用于寻找更紧的下界

• 对手论证是两个角色的较量：算法设计者与对手（选择最坏输入作为算法的输入），即构造最坏输入

• 选择最大/最小元素

  • 至少进行 \(n-1\) 次比较
  • 反证：一定有一个元素没有和最小元素比较过，只要让这个元素为最值，就说明算法得不到正确的结果

• 同时选择最大最小元素

  • 下界为 \(\left\lceil \frac{3n}{2} \right\rceil-2\)
  • 所有元素的初始状态为 N，赢过为 W，输过为 L，WL 表示输过也赢过，最后要得到 n-2 个 WL 一个 W 一个 L
  • 因此要获得 2 n-2 的信息量
  • 
  • 假设有偶数个元素，先来两两比较（每次获得两个信号量）之后每次比较获得一个信息量，进行 \(\frac{n}{2}+n-2=\frac{3n}{2}-2\) 次比较

• 选择次大元素

  • 只有在选举最大元素的过程中直接输给最大元素的才可能是次大元素
  • 在单败淘汰锦标赛中二叉树的高度为 \(\lceil \log n \rceil\) 也就是最大元素要进行 \(\lceil \log n \rceil\) 次比较（这 \(\lceil \log n \rceil\) 个元素再决出最大值），这样代价为 \(n-1+\lceil \log n \rceil-1\)
  • 下面证明这是最优的：初始时每个元素有 1 个金币，两个人比较后胜者拿走所有金币
  • 
  • 对手的策略如上，保证硬币的数目每次最多乘 2，这就说明冠军至少与 \(\lceil \log n \rceil\) 个元素进行比较（即说明上面的算法就是最优的）

• 选择中位数

  • 至少要进行 \(\frac{3}{2}n-\frac{3}{2}\) 次比较，下面说明：
  • 关键比较：帮助确定了中位数和某个元素的关系（直接或间接，如比确定小于中位数的元素更小）
  • 非关键比较：无法帮助确定~，如比确定比中位数更大的元素更小
  • 确定中位数就是需要 n-1 次关键比较（中位数就是比 \(\frac{{n-1}}{2}\) 个元素大，并且比 \(\frac{{n-1}}{2}\) 个元素小的元素）
  • 状态定义：N 表示元素还未参加过比赛；L 表示被赋予大于中位数的值；S 表示被赋予一个小于位数
  • 
  • 设计 N 的元素比较都可以转化为非关键比较，一次比较最多能消除 2 个 N（两两比较），因此能迫使进行 \(\frac{{n-1}}{2}\) 次非关键比较，之后再 \(n-1\) 次关键比较得到结果，共 \(\frac{{n-1}}{2}+n-1\)

平摊分析 (并查集引出)

• 用于分析有多种不同操作时的均摊（最坏）复杂度
  • 有些操作很廉价，有些很昂贵，但是昂贵的操作不是总能发生
• 平摊分析的基本方法
  • 实际代价 \(C_{act}\) 每个操作的实际执行代价
  • 记账代价 \(C_{acc}\) 为廉价的操作计一个正的帐，为昂贵的操作计一个负的帐（但要保证"存的钱"必须始终是正的，这才能保证求得的是最坏复杂度）
  • 平摊代价 \(C_{amo}\)：\(C_{amo}=C_{act}+C_{acc}\)

• 最终得到 l 次操作的时间复杂度，就是用 l 乘以均摊复杂度

• multipop 栈

  • push 操作；popall 操作
  • 可知 popall 的代价是与 push 的次数相关联的 (一个元素只会入栈出栈各一次)

操作	\(C_{amo}\)	\(C_{act}\)	\(C_{acc}\)
PUSH	2	1	1
POP-ALL	0	k	-k

• 数组扩充
  • 插入一个元素到数组；数组大小已满时需要复制到大小为 2 的新数组
  • 每个新加入的元素，除了要支付自己移动的代价，还需要帮扶之前已经加入了数组，但是花光了自己的钱的元素

操作	\(C_{amo}\)	\(C_{act}\)	\(C_{acc}\)
普通 insert	3	1	2
扩充 insert	3	1+k	-k+2

• 二进制计数器
  • 每次对二进制值加一；昂贵的操作是+1 后可能导致前面的位发生变化（末尾为 1 时+1）
  • 每次操作实际只会新增加一个 1，以及把若干个 1 置 为零，因此可以将原先的操作转化为置 0/1

操作	\(C_{amo}\)	\(C_{act}\)	\(C_{acc}\)
置 0	2	1	1
置 1	0	1	-1

• 基于栈实现队列
  • 两种操作入队和出队
  • 开销较大是当用于出队的栈为空时需要将入队栈全部 pop 到另一个栈当中
  • 关键是一个元素入队之后，只会分别进入两个栈各一次最后出栈

操作	\(C_{amo}\)	\(C_{act}\)	\(C_{acc}\)
入队	3	1	2
出队	1	1	0
出队（且为空）	1	1+2k	-2k
### NP-C 理论
- 优化问题：如寻找最大解
- 判定问题：判断一个值是不是解
- 优化问题比判定问题更难，由优化问题可以很容易的得到判定问题的结果

• P 问题：可以在多项式时间内解决的问题
  • 多项式的封闭性：多项式运算仍然是多项式
• NP 问题：一个问题的解可以在多项式时间完成验证（任意猜测一个解，之后可以在多项式时间内检查这个解是不是该问题的一个解）
• NP-hard 问题：\(\forall Q \in NP,Q\leq_{P}P\) 即比所有 NP 问题难
• NPC 问题：\(P\in NP,P\in NP-hard\)
• 

问题规约

• 问题 P 到 Q 的规约，判定问题 P 到 Q 的规约为一个转换函数 \(T(x)\)

  • 将问题 P 的一个合法输入 x 转化为问题 Q 的一个合法输入 \(T(x)\)
  • \(P(x)==True \ \iff \ Q(T(x))==True\)
  • 即解决了问题 Q，问题 P 就也被解决了（说明问题 Q 比问题 P 更难）

• 多项式规约：如果 T 转化是多项式时间的，那么就称 P 可以多项式时间规约到 Q，记为 \(P\leq_{P} Q\)

  • 这个规约具有传递性

NP 完全性理论

• 证明一个问题是 NPC 问题（假设已知 P 是 NPC，欲证 Q 也是 NPC）
  • 首先证明 \(\forall P\leq_{P}Q\)
  • 再证明 \(Q\in NP\)
  • 称作 P 到 Q 的规约

常见的 NPC 问题

• 最大团：最大完全子图（节点数最多并且是完全图的子图）
• 点覆盖：图 G 中任意一条边均和顶点集合 C 中的某个顶点相关联，则 C 为 G 的一个点覆盖
• 独立集：一个点集中任意两点之间没有边相连，称为独立集，独立集的大小就是节点的数目
  • \(<V,E>上的独立集\iff<V,\overline{E}>上的最大团\)
  • \(I 是<V,E>上独立集\iff V-I是点覆盖\)
• 子集划分：将输入划分为两个子集，使得物品大小之和相同
  • 子集划分是背包问题的子问题
• 背包问题：大小不超过 C，价值之和不低于 k
• 稠密子图问题：是否存咋一个子图，有 k 个节点和至少 y 条边
  • 可以有最大团规约
• 3-SAT 问题（使布尔表达式为真的输入）
• 哈密顿（环）路问题

文件系统

• 能够唯一标识一个记录的数据项或数据项集称为主关键码项，其值称为主关键码；
• 不唯一标识一个记录的数据项或数据项集称为次关键码项，其值称为次关键码。
• 文件记录分为逻辑记录和物理记录。前者是面向用户的基本存取单位，后者是面向外设的基本存取单位。

文件的存储结构

• 文件的存储结构：顺序存储、直接存取组织（散列函数）、索引组织

顺序存储

• 顺序文件中的记录按它们进入文件的先后顺序存放，其逻辑顺序与物理顺序一致
• 如果按主关键码有序，则称为顺序有序文件，否则为顺序无序文件
• 只能顺序搜索存取
• 连续文件：存放在外存的连续区域
• 串联文件，成块存放，但是块与块之间可以不连续，通过块状指针顺序链接

直接存取

• 利用散列进行组织，可以通过记录的关键码直接确定记录的地址
• 优点：随机存放，记录不需要进行排序，插入删除方便，不需要存储索引

• 缺点：不能顺序存取，多次插入删除后需要重新组织文件

• 按桶散列：若一个组能存储 m 个记录，那么第 m+1 个同义词出现时，发生溢出

• 溢出链
  • 将第 m+1 个同义词存放到溢出桶（前 m 个所在的为基桶），当基桶中检索不成功时，到溢出桶中进行检索
  • 删除时只做逻辑删除标记，系统周期性重构时再做物理删除
  • 
• 分布式溢出空间
  • 溢出桶按照一定间隔分布在基桶之间，如果有一个基桶溢出了，系统就将记录存放在下一个溢出桶，溢出桶溢出了再溢出到下一个溢出桶
  • 
• 相继溢出法
  • 当发生溢出时，溢出记录直接存放到下一个相继的桶中
  • 优点是对溢出不需要漫长的寻找，但是如果临近多个桶存满会导致要检查多个桶
  • 
• 可扩充散列：根据桶的大小进行合并分裂等操作

索引文件

• 由索引表和数据表组成，索引表表示逻辑记录与物理记录的对应关系
• 索引顺序文件：数据顺序分组，一组记录对应一个索引项（稀疏索引）
  • 
• 索引非顺序文件，每一个记录分别对应一个索引项，稠密索引
  • 
• 静态索引：多级索引结构，每一级索引都是一个有序表，在运行中结构不发生变化（可能导致不平衡，效率降低）

• 动态索引：动态调整的平衡搜索树结构，保持最佳的搜索效率

• 索引的时间效率：主要取决于访问外存的次数（索引树的高度）

倒排表

• 只使用关键码无法根据存储的内容进行查询
• 可以把常用的搜索属性作为次关键码，建立次索引；次索引中列出属性的取值，对取值建立有序链表，把具有相同属性值得记录按存放地址/主关键码的顺序连接。由次关键码、链表长度、链表本身三部分组成。
• 
  • 仅通过搜索次索引就能找到所有具有相同属性值的记录。
• 单元式倒排表：（解决倒排表中链表长度大小不一的问题）
  • 索引项不再储存具体地址，而是用 01 表示在哪些硬件（存储）区域中出现
  • 
  • 对于希望的属性值的做 AND 就得到了目标硬件区域，到这些区域中去查找即可

多级索引结构

• 数据记录比较大时索引表也会太大，可以建立（常驻内存的）索引的索引

• ISAM 索引：盘组、柱面、磁道三级地址索引

• m 路搜索树（B 树就是自平衡的 m 路搜索树）

  • 

B 树

• B 树通过多叉树降低深度，可以减少磁盘 IO 读取次数，适用于磁盘存储
• 定义：
  • 根节点至少有两个子女（就是根节点至少要有一个关键字），其它所有节点至少有 \(\left\lceil \frac{m}{2} \right\rceil\) 个子女
  • 所有失败节点 （叶） 位于同一层
  • 符合 m 路搜索树的所有定义
  • 每个节点的关键码个数 \(\left[ \left\lceil \frac{m}{2} \right\rceil -1,m-1\right]\)，对应子节点 \(\left[ \left\lceil \frac{m}{2} \right\rceil,m\right]\)
  • 每一个关键码就对应一个搜索结果
• B 树树高公式：\(\log_{m}(n+1)\leq h\leq \log_{\left\lceil \frac{m}{2} \right\rceil}\left( \frac{n+1}{2} \right)+1\) 其中 n 为关键字的数目 (小心区分关键字数目和节点数目的区别)
  • 注意下层节点数是关键字数目+1
  • 即 \((m-1){\frac{{1-m^n}}{1-m}}=m^n-1\) 这也是为什么 \(\log\) 里要 \(+1\)
• m 的选择：
  • B 树的搜索由两部分组成：在节点内的搜索和寻一条路径向下一层搜索交替进行的过程
  • 提高 m 可以减少 h 的高度，但是 m 过大会导致节点的大小超出内存，增加磁盘 io 降低效率
• 搜索
  • 继承了 m 路搜索树 Mtree 上的搜索算法
  • 搜索成功的时间取决于关键码所在的层次，不成功的时间取决于树的高度

• 插入

  • 插入总是在叶节点进行，之后可能进行自底向上的调整（关键码数目超过 m-1）
  • 如果插入后关键字数目大于 \(m-1\) 则要对插入后的节点进行分裂操作：\(\lceil m/2\rceil\) 关键字放入父节点中，其左侧节点留在原先的子树中，右侧节点放入新节点中。（即把中间节点提升到父节点）
  • 
  • 

• 删除

  • 首先先通过搜索找要删除的关键码的位置
• 删除终端节点：
  • 若删除后关键字数目过少，且兄弟够借（临近的兄弟节点的关键字个数 \(>=\lceil m/2 \rceil\) 则从兄弟节点借一个关键字
  • 兄弟不够借，则与一个不够借的兄弟节点合并，并把双亲中的一个节点下移
• 删除非终端节点：
  • 使用右子树中最小关键码（被删除节点的后继节点）代替被删除的关键码，再从子树中删除最小关键码
  • 这就转化为删除终端节点的问题

B+树

• 定义：
  • 每个节点最多 m 个子树
  • 根节点最少 1 棵，其它节点至少 \(\left\lceil \frac{m}{2} \right\rceil\) 棵，一棵子树对应一个关键码
• 所有的数据都保存在叶子结点，关键字只用来索引；叶子节点被指针串联起来，支持顺序访问
• 所有的非终端结点可以看成是索引部分，结点中的关键字表示其子树（根结点）中的最大（或最小）关键字。
• 插入
  • 如果节点中有多余的空间放入元素，则直接插入即可。
  • 如果插入后叶节点关键码个数大于 m，则将其分裂为两个节点，并将其中间元素的索引放入到父节点中 （叶节点拷贝，非叶结点直接上移）
• 删除
• 仅在叶节点中删除元素，如果节点还满足 B+树的要求，则直接删除。
• 如果元素个数过少，并且其邻近兄弟节点有多余的元素，则从邻近兄弟节点中借一个元素，并修改父节点中的索引使其满足新的划分。
• 如果其邻近兄弟节点也没有多余的元素，则将其和邻近兄弟节点合并，并且我们需要修改其父节点的索引以满足新的划分。

外排序

• 待排序的记录数目太多，无法在内存中一次处理，必须以文件形式存放于外存，排序过程中一部分一部分调入内存进行处理，这种基于外部存储设备的排序就是外排序。

• 外排序的基本过程

  • 首先建立内存缓冲区，并根据内存缓冲区的大小对文件进行划分，对每一段数据分别进行排序，得到初始归并段，写回到外存
  • 按照归并树的模式对初始归并段进行归并，不断扩大归并段，最终归并为一个大的归并段（如对于两路归并来说：将缓冲区划分为两个输入缓冲区一个输出缓冲区，一旦某个输入缓冲区中的数据被完全消耗，就从对应的归并段中读取更多数据填充这个缓冲区。同理，当输出缓冲区被填满时，其内容将被写回外存，并清空输出缓冲区以便再次使用）

• 外部排序的耗时 \(t_{ES}=m^{*}t_{IS}+d^{*}t_{IO}+S^{*}n^{*}t_{mg}\)

  • 分别为：每个初始段内排序时间；外存快访问次数；取得内存中记录时间
  • m 为归并路，S 为归并趟数
  • 时间瓶颈在于 io 磁盘读取时间，因此希望减少 io 的次数（使用多路归并）

k 路归并

• 
• 假设每趟归并 n 个元素，则一次大致进行 \((n-1)*(k-1)\) 次比较
  • 即总共进行约 \((n-1)*(k-1)*\lceil \log_{k}m \rceil\)
  • 也就是说 k 增大会使得内部归并的时间增大
  • 使用败者树优化（获取最大元素复杂度 \(\log_{2}k\) ）复杂度变为 \(\lceil \log_{2}m \rceil*(n-1)\) 与 k 无关
• 归并路数 k 不是越大越好。归并路数 k 增大, 相应需增加输入缓冲区个数。如果可供使用的内存空间不变, 势必要减少每个输入缓冲区的容量, 使内外存交换数据的次数增大。

败者树

• 在非叶结点中败者数存储败者（假设从小到大排序，那么就存储排序码较大的节点）
  • 败者树记录败者，但仍然派胜者继续向上
• 根结点的上一层另外增加一个结点，存放树中当前记录排序码最小的结点 (最终胜者)。
• 在初始建立败者树时使用: 存放一个最小的在各归并段中不可能出现的排序码: -MaxValue。
• ![[多路合并.pdf]]

败者树、胜者树与堆

• 这三者都可以用于实现优先队列，并且渐进时间复杂度相同，但是常数有所区别
• 堆
  • 堆取出最小值之后将新的值取出的值放到堆顶，之后对堆进行调整，每一层父节点都需要与两个子节点进行比较，即比较两次
• 胜者树
  • 胜者树更新叶子节点之后从下向上进行维护，每次需要与兄弟节点进行比较，即比较一次，但是每次都要先获取父节点，再获取兄弟节点，再进行比较
• 败者树
  • 败者树维护时只需要与父节点进行一次比较（更新的一定是有胜节点这一边，因此父节点上的败者就是兄弟节点）
• 由此，败者树的效率最高，因此使用败者树来实现多路归并

置换选择算法

• 使用置换选择算法可以得到平均长度为 2n 的多个归并段（n 为缓冲区可以容纳的元素数目），由此实现减少层数，减少 io 提高效率
• 
• 填入元素装满缓冲区，每次选择最小元素取出到 FO，并从 FI 装入一个元素
• 当最小元素小于当前 FO 的末尾时截断，创建新的 FO（这就得到了一个完成内排序的串）

最佳归并树

• 
• 使用霍夫曼树思想，每次选择最短的几个归并段进行归并
• 为了实现完美的多路归并，还需要添加几个零段（长度为 0 的归并段），使得每次合并都是 3 项合并
  • 即使得 \((n_{0}-1)\%(k-1)=0\)，添加 \(k-u-1\) 项