ads知识

2024年10月24日 3.4k 字大概 14 分钟

hw1 AVL树和红黑树

知识1 在AVL树中四种样例的划分是来自于 troublemaker、 troublefinder retated child 与 troublefinder
（总结：关注trouble finder（距离案发现场最近的trouble finder）的孩子的孩子树是否包括troublemaker，例如 LR，表示的是 Trouble Maker 在 Trouble Finder 的 L 孩子节点的 R 孩子树中。）
知识2 在AVL中四种样例的具体调整方法还是不太清楚（并且由于对称性，我们综合下来就是两种情况，一种情况进行单次旋转，一种情况进行两次旋转）
知识3 AVL树的节点数量递推式
$n(h)=n(h-1)+n(h-2)+1$
知识4 若AVL树进行删除操作只会影响到一个节点，但是当我们修复后矛盾可能往上移动，所以可能需要$Olog(n)$次旋转
知识5 红黑树的定义
1. 每一个节点都是黑色或者红色
2. 根一定为黑色
3. 叶子（要注意叶子节点一定是空节点，这个概念是很关键的）都为黑色
4. 红色节点的孩子一定为黑色
5. 对每一个节点，从该节点到叶子的路径中均有数量相同的黑色节点。
知识6 红黑树的插入以及相关的不平衡调整情况
1. 先将整个红黑树当作一个普通的二叉搜索树，将目标数据插入到树的末端（也就是置换一个 NIL 节点），并将它染为红色，再调整使之在保证黑高不变的情况下，满足红色节点不能相邻的要求。（因为我们这样操作后，原有的黑高性质不会被破坏，但是可能出现红色节点相邻的情况）
2. 此时，插入操作后可能存在下述三种情况：
  
  （操作为染黑加旋转）
  
  （操作为旋转，转化为上面的样例1）
  
  （操作为染黑与染红，矛盾上移，则可能会出现4种情况(其中可能存在这三种情况的相互转化，但是核心都是解决问题并将矛盾上移)）
知识7 红黑树的删除以及相关的平衡调整情况

ex1:

解释：当对avl树进行删除操作后，则只能有一个点发生不平衡，现在对一这个点为根的子树进行分析。因为我们调整整颗avl树，则首先这颗树的高度会减少1。如果整棵树已经平衡，则停止操作。但是如果因为这颗子树的高度减一导致上方节点的左右子树的高度差大于等于2，则需要上移矛盾再进行操作，则这颗子树的高度可能最终保持不变。

ex2:

解释：这道题需要结合红黑树的几个基本性质进行解决，u是红黑树的内部节点，其中u有两个孩子，其中一个孩子v是红黑树的内部节点，另一个孩子是nil节点。由红黑树的第五个定义，因为另外一个节点为内部节点则一定有两个nil，由第五个性质，则v一定为红色，再由第四个性质，u一定为黑色。

hw2 摊还分析与splay树

知识1 splay树的具体操作还得记一记喵
1. splay树的操作相当简单，首先按照bst进行操作，然后每一次对于操作的节点都进行旋转直到转到根节点处。
对摊还分析的思考(常用的是势能法)
接下来，我们需要设计一个势能函数
Φ(x)，并且根据我们提到过的势能分析法的特性，
Φ(x) 应该具有这么几个特征：
开销大的操作应当倾向让势能降，开销小的操作应当倾向让势能升；
势能高倾向于让某些操作开销大，势能低倾向于让某些操作开销小；
Φ(final)>Φ(initial)；
ex1

解释：这是splay树的一个特殊情况，也是最坏情况。当我们将一个递增的序列添加到一个空树中的时候，
每次都是最大值在根节点，所以添加的新的节点在它的右侧，旋转到根节点，均会退化为链表。

解释：这道题感觉比较有迷惑性，因为如果这颗树要找某个键值的节点，最多就是O(h)的时间复杂度
而我们根据摊还分析可以证明高度为O(logn),而后每次寻找都在根节点即为O(1),所以综上，时间复杂度为O（m+logn）

解释：这是一道均摊分析的题目，所谓摊还分析就是对于任何情况下的操作$cost=actual cost+\Delta \phi=O(target)$,因为题干要求amortized cost为O(1),不妨定义$\phi=the opposite of the number of available cells in the array$,则当普通的添加操作一定符合O(1),研究扩展space时的操作$cost=c+nc+-nc=c$符合O(1),经验证其他选项都不满足条件。

hw3 b+tree

hw3选择与判断小题

skewed heap和leftist heap
斜堆也需要满足大根堆（小根堆）的性质，而它的合并和左偏堆的合并也十分类似，只不过我们这次无条件的交换左右子树，换句话来说，不管左偏性质如何变化，我们都会选择交换参与合并的左右子树，这样我们就不需要在回溯的时候才进行左右子树的交换，于是就实现了完全的自上而下。
从二叉堆的结构说起，它是一棵二叉树，并且是完全二叉树，每个结点中存有一个元素（或者说，有个权值）。
零距离(英文名NPL，即Null Path Length)则是从一个节点到一个”最近的不满节点”的路径长度。不满节点是指该该节点的左右孩子至少有有一个为NULL。叶节点的NPL为0，NULL节点的NPL为-1
ex1

解释：现在我们考虑b+树中的插入操作，因为题目的前提条件是leaf node没有发生分裂，则不需要更新internal node中的key。

解释：（我觉得这个问题主要在于我的目光局限于2-3B+树）因为没有underflow操作。

hw4 倒序查找与二向堆

倒排索引（inverted file index）是一种常见的文本检索技术，用于快速查找包含特定单词或短语的文档。它通过将单词或短语作为关键字，并将它们出现在文档中的位置记录在一个索引中，从而支持快速的文本检索
知识1
解释：主要是一些概念的明晰。 relevant irrelevant
retrieved(检索) RR IR
not retrieved RN IN
precision=RR/（RR+IR）
recall=RR/（RR+RN）
知识2
注意document和query的评判标准
知识3
distributed indexing中，each node contains index of a subset of collection
知识4
主要研究我们的评判标准，注意区分data和information
知识5
对于单词的存储（采用哈希还是其他树）
哈希的速度更快，但是但是range searches are expensive

hw5 回溯

选填小题

知识1 tic-tac-toe 题目

解释：一般做这个题的时候就直接把所有空全部填满，然后分别查看人与电脑获胜的情况的数目

知识2 阿尔法贝塔剪枝问题

总结：当利用阿尔法贝塔剪枝时解题顺序：左子树–根–右子树（基于深度优先搜索）
解释：在这道题目中，因为剪枝的情况是不会选用它的父亲则它被剪枝，当我们遍历知道它的父亲不选择时，此时它父亲的左孩子已经完成遍历，则右孩子被剪枝。

ex1 dfs与bfs加剪枝的速度

解释：其实这道题可以从老师的hint中看，假设一个例子左边的叶子的深度十分深而右侧的叶子深度较浅，则我们一定存在这样的例子，当使用bfs时并没有像dfs一样遍历完那么深的深度就已经提前进行剪枝操作，则我们的时间就比dfs要短。

hw6 贪心

知识1
贪心算法的基本概念
只有当局部优解等于全局优解时可以使用；贪心算法的使用是一个逐步逼近最佳方法的过程
知识2（activity selection problem）

这是一个常见的贪心问题，在一定的时间内有一系列活动安排，但是两个活动的进行时间不能有交叉，需要求的这个时间内所能举行的最多的活动数量。
寻找贪心法则：每次寻找结束时间最早的活动
我们想要证明我们理论的正确性，我们利用反证法，若A是按照理论取得的解，若存在一个S，但是S比A更优，我们假设A和S前t个活动都相同，那么在t+1个活动时，因为A按照最优则$f_{i(t+1)}<=f_{j(t+1)}$，则我们再后面遇到不一样时都可以用i替换j，但是最终我们会发现S不可能比A会多出活动，则假设矛盾，则我们得证。

知识2（haffuman coding）

这一道题目我们需要寻找到一个最优的编码映射满足：the cost of $\sum_{}{}d_{a}*f_{a}$ is mininum（分别为霍夫曼树对应字符的深度和字符在字符串中出现的频次）;且没有一个字符的编码是另一个字符编码的前缀（也就是说，每一个字符都在叶子上面）
霍夫曼解决此问题的算法如下：首先创造一系列单节点的树，然后找到两颗频次最小的树进行合并，这两颗小树则被森林删除，取而代之的是他们合并的结果，这颗大树的频次则是两颗小树频次之和。重复上述操作直到森林只有一颗树。
下面有一个ppt的样例，我觉得是频次小的放在合并的左子树
时间复杂度为O（NlogN）
证明算法的正确性：首先有一个lamma，如果a和b是频次最低的两个字符，那么a和b在霍夫曼树中一定是兄弟。利用归纳假设加上反证法：即假定存在一棵树A，不满足霍夫曼算法但是是最优的，我们将最下层的两个结点合并得到A1，同理对霍夫曼树我们也能得到H和H1，但是在k-1个节点时我们已经知道H1是最优的，所以A不可能是最优的。

ex1（greedy）

解释：其实C也很容易举出反例，因为可能存在d很大但是p很小，并且这种情况很多时当我们去到ddl很靠近的事件时已经早已逾期ddl了。我们再来正面思考情况，很容易知道

hw7 分治

知识1 counting inversion

定义一个数组，如果$A[i]>A[j]，i<j,(i,j) is a inversion$
output #inversion（inversion的数量）
若采用枚举$O(n^2)$,分治$O(nlogn)$
将这个数组左右等分为两半,那么所有的inversion分为三种情况(leftinversion,rightinversion,splitinversion),前两种情况的结果都可以使用递归得到,第三种情况如果使用暴力枚举其实时间还是n的平方的数量级=》优化：假如此时左右两侧都是排好序的,我们直接利用归并的merge将两侧合并，每次数量都加上左侧剩余的数量即可，那么就能在O(n)时间内解决问题。
总结(sort-and-countinv)

if n<=1:
   return (A,0);
else
   L=lefthalf of A;
   R=righthalf of A;
   (B,leftINv)=sort-and-countinv(L);
   (C,rightInv)=sort-and-countinv(R);
   (D,spiltInv)=merge-and-countInv(B,C);
   return (D,leftInv+rightINv+spiltInv);

Merge-and-countInv(B,C):
i=1,j=1,splitinv=0;
int D[n];
for k=1 to n:
  if B[i]<C[j]
    D[k]=B[i];
    i=i+1;
  else
    D[k]=C[j];
    j=j+1;
    splitInv+=n/2-i+1;
 return (D,splitInv);

时间T(n)=2T(n/2)+O(n);->T(n)=O(nlogn)

知识2 closest pair

首先根据横坐标分为两部分(leftpair,rightpair,splitpair)
当分治时，左右两侧的最小值我们都可以通过递归得到，所以现在就能产生一个较小的距离记作$\delta$，接着我们按照上述的中轴线在水平位置$\delta$的距离形成一条带子，再对里面的每一个点以$\delta$\2为半径形成8个正方形，则每个正方形都至多有一个点(因为如果有两个点就与我们前面递归得到的结果相矛盾)
伪代码

Px:sort P by x-cord
Py:sort P by y-cord
closest pair(Px,Py)
if n<=3
  final
Lx=pts on the lefthalf plane,sorted by x-cord
Ly=pts on the lefthalf plane,sorted by y-cord  在Rx和Ry的前提下都能以o(n)
Rx=pts on the righthalf plane,sorted by x-cord
Ry=pts on the righthalf plane,sorted by y-cord
(l1,l2)=closest pair(Lx,Ly)
(r1,r2)=closest pair(Rx,Ry)
$\delta$=min(d(l1,l2),d(r1,r2))
(s1,s2)=closest split pair(Px,Py,$\delta$)
return min($\delta$,d(s1,s2))

closeSplitPair(Px,Py,$\delta$):
  x1=largest x-cord of the lefthalf plane;
  Sx={points q1,q2.....with x1-delta<=qi.x<=x1+delta} sorted by y-cord
  mindist=$\infty$;
  colset=null;
  for i=1 to k
    for j=1 to 8
       if(d(qi,q(i+j))<delta)
         delta=d(qi,q(i+j))
         closet=(qi,q(i+j))

本文总阅读量次