DSA PA4 REPORT

CST 4-1 Report

算法构思

本题需要维护这样一个数据结构：对于$\forall i, i\in[0,n)$

• 存有$[max(0,i-k-1),min(n-1,i+k+1)]$这一区间窗口内所有原件的信息
• 可以查询这一范围内和i异或值最大的字符串id
• 可以动态删去某个字符串和添加某个字符串到这个数据结构中

基于此，我们最终选择字典树这一数据结构，下面对其进行详细介绍。

字典树：规则

对字典树的理解可以类比有限状态自动机（DFA），本题中字母表$\Sigma = \{0,1\}$，树的根节点相当于是自动机入口。从入口开始，每经过一个结点，01串将自己的第一个字符取出，如果是0则转向结点的左子树，是1则转向右子树，直到走到树的叶结点为止，每个叶结点可以视作自动机的一个终态

对于每个结点，用cnt存储路径经过这个结点的字符串数量

对于每个叶结点，还要记录这个终态对应的字符串的id值，由于可能存在多个id值的字符串相同的情况，这里的id值记录的是所有存在树中对应这一终态的字符串id最小值，$ _id = min(\{id | str[id] \land id\in [max(0,i-k-1),min(n-1,i+k+1)]\}) $，这一操作是为了满足题目要求中“输出所有窗口内和id=i异或值最大的字符串id的最小值”要求。

字典树：初始化

由于本题字母表中只有两个字母，所以字典树实际上是一棵高度等于64的二叉树。每个结点的左右子树分别代表接受0和1后转移到的状态。

字典树：动态变化

每当我们变换窗口时，字典树中都可能会插入一个字符串并删除一个字符串（当窗口移动到两端附近时，也可能出现不删除或不插入的情况）

字典树：插入

考虑插入一个64位的01字符串original[i]。

从根节点开始，按照字典树转向规则深探，如果结点并没有对应的孩子，则创建它，同时我们将沿途经过的所有结点计数值加1，表示经过这一节点的字符串多了一个。

探到叶结点后，更新叶结点的id值，这要求我们插入的字符串一定是当前窗口中的最小值，因此，我们的窗口应该是从右往左移动，而非从左往右移动。

字典树：删除

考虑删除一个64位的01字符串original[i]，这一字符串此前一定已经插入在树中。

从根节点开始，按照字典树转向规则深探，同时我们将沿途经过的所有结点计数值减1，表示经过这一节点的字符串少了一个。

字典树：查询

考虑查询j，使得$j\neq i \land j \in [max(0,i-k-1),min(n-1,i+k+1)]$且original[j]和original[i]异或值最大。异或值查询满足贪心条件，只需要每次都转向异或值最大的方向即可，具体来说就是如果有结点两个孩子的话，接收0后转向右子树，接收1后转向左子树，这样最终到达的终态得到一个id值即是所求结果。

一般来说，上述办法找到的id值和i是不同的，除非一种情况：i=0且窗口内所有字符串相同，此时找到的id为0，但根据题目要求，id值应该为1，这里需要特判一下。

时间和空间复杂度的估算

时间复杂度：每个元件至多被插入一次、删除一次，对于每次插入、删除操作，时间复杂度均正比于树高$O(64)=O(1)$，而对n个元件，我们的时间复杂度为$O(n)$

空间复杂度：考虑到每个字典树的结点都可能代表一个字符，字典树的总结点个数应该不大于$O(64n)$，其它的数组空间规模也符合$O(n)$，总的空间复杂度应是$O(n)$的。但这只是一个相当宽泛的上界，存在被卡常的可能。考虑到字典树靠近根节点的结点应该是可以复用的，下面对其进行更精细的分析：

考虑n的最大值$n=5\times10^5$，假设某一时刻窗口能够涵盖所有的字符串，n对2取对数后可以得到，前19层的树是满的，从第20层开始每个字符串对应一条单链，这样的结点数就达到了理论上的最大值，总个数为$2^{20}+5\times10^5\times(64-19)=23548576$。因此，理论上字典树占的空间为359.32MB（每个结点存4个int，空间大小为16byte）

bool original[500001][64]数组存储了所有原件字符串信息，空间复杂度为$O(64n)=O(n)$，占空间大小为$64\times500001B=30.51MB$

因为窗口是从右往左移动的，还需要int res[500001]数组来存储结果，空间复杂度为$O(n)$，占空间大小为$4\times500001B=1.97MB$

总的占空间大小为$359.32+30.51+1.97=391.8MB< 512MB$

CST 4-2 Report

算法构思

本题所要完成的任务和Dijkstra算法相似，都是求从起点到终点的最短距离，不同之处在于权重由边转移到了点，但这并不会对算法本身造成过大的改动；另一个不同是本题要求还要求出最短路径的数量，这需要我们基于Dijkstra算法进行改进。此外，如果使用蛮力Dijkstra算法的话时间复杂度为$O(n^2)$代入n简单计算便可知会导致超时，因此我们需要设计一种数据结构，能够返回当前非永久性节点中路径长度最小的结点，避免$O(n)$的轮询，优先级二叉堆可以满足我们的这一需求。

建图过程

每个游戏关卡存储为一个Node结点，每个结构体中存有以下成员变量：

• minlen：从起点开始，到结点的最短长度
• num：到结点的最短路径的数量
• time：通过结点所需的用时
• flag：标记结点是否为永久结点

边的信息保存在Edge e数组中，本题中每条边都是一条无向边，我们将其转化为两条方向相反的边，这样便于建立以起始点为索引的链表，链表表头存储在数组head中。

设计优先级二叉堆

二叉堆中每一个结点PQNode存储两个变量：

• id：记录这个点对应结点的id值
• num：记录在结点插入时，到达该结点的最短路径

二叉堆堆顶的元素满足，堆顶的结点的num值为全堆最小。

每当插入一个PQNode结点时，我们将其添加在当前堆的末尾，然后根据其num值”上浮“。删除一个PQNode结点时，我们首先记录堆顶的值，然后将其和堆尾元素交换，随后让堆顶元素”下沉“。这些都是二叉堆的基本操作。

Dijkstra算法：初始化

一开始，将起点的最短路大小赋为该关卡的耗时，将其添加到堆中，并将起点设为工作结点

Dijkstra算法：过程

每次确定一个工作结点后，将其变为永久结点，并更新所有和它相邻的非永久性结点的最短路径值和最短路径数量，对于工作结点p和其相邻结点q，更新规则如下：

• $minlen(p)+time(q)>minlen(q)$，保持q的最短路径距离和最短路径数不变
• $minlen(p)+time(q)=minlen(q)$，q的最短路径距离不变，最短路径数在原有基础上加上$num(q)$
• $minlen(p)+time(q)<minlen(q)$，q的最短路径距离更新为$minlen(p)+time(q)$，最短路径数更新为$num(q)$

这样就实现了同时记录最短路径长度和最短路径数。

将所有相邻结点更新完后，从优先级二叉堆中不断取出堆顶元素p，直到取出的p表示的是一个现在为非永久节点为止，此时的p一定是所有非永久结点中最短路径距离最小的结点。将p确定新的工作结点，重复上述过程，直到终点变为永久结点为止。

时间和空间复杂度的估算

时间复杂度：由于每条边至多只有一个方向上的结点会被插入到二叉堆中，所以二叉堆结点数至多为m，二叉堆的插入和删除操作时间复杂度均正比于其树高，也就是$O(log(m))$，由于每条无向边至多会插入一次，因此插入的总时间复杂度为$O(mlog(m))$，删除也是同理，每次取出的堆顶元素不一定就是我们需要的那个结点，可能某次寻找工作结点时需要多次取出堆顶元素，但取出的总元素个数不会大于堆中最大元素个数，因此取出操作的时间复杂度上界应该也是$O(mlog(m))$。因此，算法的时间复杂度为$O(mlog(m))$

除此以外，对结点和边的读入操作其复杂度为$O(n)$和$O(m)$，考虑题目并没有给出m和n的大小关系，但m和n具有相同的量级，因此总的时间复杂度也可以写作$O((m+n)log(m))$，这样写可以涵盖n很大但m很小的情况。

空间复杂度：存储边的数组和二叉堆数组空间复杂度均为$O(m)$（这两个数组我都开到了2m的大小，实际上二叉堆数组大小开到m已经足够），存储邻接表表头的的数组和关卡结点数组的空间复杂度均为$O(n)$，因此，总的空间复杂度为$O(m+n)$

CST LAB3 BBST Report

数据结构

本题我选择实现的数据结构为Splay树和Avl树，下面对这两个数据结构的核心功能和公共接口进行说明。

1. 树结构实现

1.1 二叉树结点 BinNode

仿照课本的继承关系，Splay树和Avl树中的二叉树结点均用结构体BinNode实现，其中存储数据为：

• data：结点键值
• parent，l，r：父节点和左右孩子结点的数组下标
• height：结点高度（在Avl树中使用）
• index：该结点对应的数组下标

1.2 旋转 zag,zig

这同样是两种树可以通用的函数，函数参数为需要旋转的结点v下标id，v和其左右孩子构成了一个”旋转单元“，zag逆时针旋转，zig顺时针旋转。旋转重置父子之间指向关系（包括三个结点之间相互关系和他们与父亲或孩子结点之间的关系），并更新高度。

1.3 伸展 Splay

Splay操作每次将最后访问的结点伸展至根，为了避免出现逐层旋转在一字型下可能会导致树高过高的问题，采用双层伸展的办法。当祖孙三代呈一字型时，先旋转祖父结点再旋转父亲结点；当祖孙三代呈之字型时，先旋转父亲结点再旋转祖父结点（其实也可以先祖父再父亲，主要为了和教材保持一致），旋转时，还需对父亲和祖父是否存在等情况做讨论，处理特殊情况。

1.4 搜索 search

基础搜索算法和普通二叉搜索树一致，都是从根节点开始深探直至找到对应节点或发生不存在孩子节点的情况，搜索过程中_hot始终指向查找结点的父节点。

Splay树要求对每一次查找操作都要将查找到的结点伸展至根，因此每次搜索后需要做一次判定：如果查找成功，则将命中结点伸展至根，否则将_hot结点伸展至根。

1.5 插入 insert

首先通过搜索函数search找到结点需要插入的位置，由于Splay树的搜索函数内置了伸展操作，所以执行完搜索后_hot结点就已伸展至根，此时根据插入节点和_hot结点的关系判断插入到其左孩子还是右孩子即可，Avl树无需伸展，但插入后需沿深探路径回溯至根，沿路检查结点是否处于平衡状态，如果遇到非平衡状态，则对该结点进行重平衡操作，教材给出的是3+4重构，这里并未对3+4重构进行封装，而是通过分情况讨论选择旋转方式zig/zag实现，当发现一个失衡结点并重平衡后，即可退出不再上溯。

1.6 删除 remove

首先还是搜索需要删除的结点并将其伸展至根，删除该结点后，取其后继succ为新的根节点，如果没有后继，则取其前驱pred。

对于Avl树，删除后需要沿路检查各父亲结点是否失衡并使其重平衡，而Splay树则不需要这样的操作。

2. 复杂度分析

2.1 Avl树

根据讲义P540页的分析，考虑高为h的结点最少的Avl树，其结点个数满足递推式$S(h)=1+S(h-1)+S(h-2)$，因此，高度为h的AVL树，至少包含$S(h)=fib(h+3)-1$个结点，由于斐波那契数列通项公式为 $fib(n)=\frac{1}{\sqrt 5}[(\frac{1+\sqrt 5}{2})^n-(\frac{1-\sqrt 5}{2})^n]$，由于斐波那契数列大致呈指数增长，因此含n个结点的Avl树其最大树高也是$O(logn)$的，由于满二叉树，也就是最”胖“的Avl树高度也是$O(logn)$，所以这个界是严格的。

Avl树的搜索和普通二叉树是相同的，其算法复杂度均正比于树高$O(logn)$，而对于插入操作，在插入后只需要沿路回溯至非失衡结点重构，由于回溯深度不会超过深探的深度，也就是树高$O(logn)$，而重构操作本身又是$O(1)$的，因此插入算法时间复杂度也是$O(logn)$。删除操作和插入不同之处在于要一路回溯至根才停止，沿路重构所有失衡结点，而由于访问的结点个数和深探深度相同，因此最坏情况下也只需重构$O(logn)$次，因此删除操作的算法时间复杂度也是$O(logn)$。

综上，Avl树的搜索、插入、删除操作时间复杂度均为$O(logn)$，共m次操作，因此总的时间复杂度为$O(mlogn)$

2.2 Splay树

根据讲义，我们需要用势能分析的方法来分析其均摊复杂度。首先，我们定义Splay树中结点v的势能为$\phi(v)=log|v|$，$|v|$表示这个结点子树的结点个数，树的势能定义为$\Phi(T)=\Sigma_{v\in T}\phi(v)$，直觉告诉我们，越平衡的树，其势能越小，越倾侧的树，其势能越大，具体来说，单链的势能最大，为$log(n!)=O(nlogn)$。

给出势能的定义后，我们开始计算时间复杂度，首先，我们将问题简化，考虑单次将结点$x$旋转至根的时间复杂度，其他操作均可以视作这个操作的组合。而对于每次旋转至根的操作，可以分为两部分讨论：双旋和单旋。前者我们将用势能增量来表示复杂度，而后者由于单次旋转复杂度本身难以计算，但我们可以考虑经过m次旋转至根的操作后，单旋造成的时间复杂度本身应该不会不会超过树自身势能的bound，即$O(mlogn)$，我们只需要最后将其加上就可以，

下面我们重点分析单次双旋至根的时间复杂度，分为两种情况讨论：一字型和之字型

• 一字型

假设x,y,z分别为孩子，父亲，爷爷结点，旋转后对应的结点为x’,y’,z’。变化后的总势能为

$$\begin{align} \Delta \Phi(T)&=\phi(x')+\phi(y')+\phi(z')-\phi(x)-\phi(y)-\phi(z) \\&= \phi(y')+\phi(z')-\phi(x)-\phi(y) \end{align}$$

而复杂度应该为$O(1)+\Delta \Phi(T)$，下面我们尝试将其放缩为$k(\phi(x’)-\phi(x))，k为常数$的形式，由于常数k本身值是多少并不重要，所以我们可以将$O(1)$视作1来简化计算。我们可以先做这样的放缩：

$$1+\Delta \Phi(T)\leq \phi(y')+\phi(z')-\phi(x)-\phi(y)\leq 1+ \phi(x')+\phi(z')-2\phi(x)$$

另一方面，根据一字型变化满足的条件，我们有：$|x’|=|z’|+|x|+1$，利用均值不等式我们可以进一步得到

$$\phi(x)+\phi(z')-2\phi(x') = log\frac{|x||z'|}{|x'|^2}\le log\frac{|x'|^2}{4|x'|^2}=log\frac{1}{4}<-1$$

代入原式，可以解得

$$\begin{align} 1+\Delta \Phi(T) &\le 1+ \phi(x')+\phi(z')-2\phi(x) \\&<\phi(x')+\phi(z')-2\phi(x)-(\phi(x)+\phi(z')-2\phi(x')) \\&=3(\phi(x')-\phi(x)) \end{align}$$

旋转结束后，总复杂度应小于$3(\phi(root)-\phi(x_0))<3logn$

• 之子型

假设x,y,z分别为孩子，父亲，爷爷结点，旋转后对应的结点为x’,y’,z’。同样我们可以得到变化后的总势能为

$$\begin{align} \Delta \Phi(T)&=\phi(x')+\phi(y')+\phi(z')-\phi(x)-\phi(y)-\phi(z) \\&= \phi(y')+\phi(z')-\phi(x)-\phi(y) \end{align}$$

但我们不具备一字型的放缩条件，我们需要换一种方法放缩，具体的，我们有$|y’|+|z’|+1 = |x’|$，采用相似的放缩方法，不难得到

$$\phi(y')+\phi(z')-2\phi(x')<-1$$

那么我们有：

$$\begin{align} 1 + \Delta \Phi(T) &= 1+\phi(y')+\phi(z')-\phi(x)-\phi(y) \\&< 1+\phi(y')+\phi(z')-\phi(x)-\phi(y) - (\phi(y')+\phi(z')-2\phi(x')) \\&=2\phi(x')-\phi(x)-\phi(y) \\&<2(\phi(x')-\phi(x)) \end{align}$$

旋转结束后，总复杂度应小于$2(\phi(root)-\phi(x_0))<2logn$

综上，加上先前单旋的时间复杂度，n个节点的splay树做m次旋转至根操作的时间复杂度为$O((n+m)logn)$，而对于查找和删除操作，所做的无非就是找到其前驱或者后继并用$O(1)$的操作更新根节点，复杂度不会超过$O(n)$，因此，对于插入和删除操作来说，总时间复杂度与上述结果相同，因此，m次操作的时间复杂度为$O((n+m)logn)$

效率测试

测试环境

Windows x86-64操作系统，处理器为11th Gen Intel(R) Core(TM) i7-1185G7 @ 3.00GHz 3.00 GHz

评测环境采用LemonLine 0.3.4，相比c语言的clock函数，评测系统的测试结果更准确

测例设计

我一共尝试设计了五类测例：

1. rand_data：假设用户会随机的进行增删差操作，且增删差的值也是完全随机的。每组测例的操作指令数量均为200000，生成程序为rand_data.cpp。
2. qd_data：这里试图模拟的环境是，用户在插入随机大小的数据时会随机地查询当前树内的元素，并且每次查到对应的元素后都将其取出，插入和查询的概率相等。每组测例的操作指令数量均为200000，生成程序为qd_data.cpp。
3. queue_data：这里试图模拟一种队列式的数据操作，即控制树内总结点个数window_size不变，每次向其中添加一个新的结点，并删除最早插入的结点。每组测例的操作指令数量为200000，window_size为2000，生成程序为queue_data.cpp。
4. readonly_data：只读类数据，即随机进行插入和查询两种操作，不删除树中结点，每组测例的操作指令数量为100000。生成程序为readonly_data.cpp。
5. local_data：设计这个环境主要是为了模拟Splay树的使用环境，用户会以10%的概率做插入操作，并以5%的概率做删除操作，否则做查询操作，且在删除和查询时，如果上一次访问的元素没有被删除，则优先对该元素执行查询/删除操作，如果该元素已经被删除，则随机取元素删除/查询。每组测例的操作指令数量为200000。生成程序为local_data.cpp。

对于上述数据中的每一类，我都生成了五组程序，分析时对运行时间取平均，这样可以有效降低实验中IO操作以及测试环境不稳定产生的误差。

此外，对于local类型数据，为了探究不同数据规模下两树的性能的差异，我取n = 50000，100000，200000，300000，400000，500000下，分别对两棵树的性能进行测试。

此外，我还写了std.cpp用来对每组输入数据生成正确的答案，命名为<类型>.out。

运行脚本datamaker.bat可以实现一组测例的生成，所有测例生成程序保存在/datamaker目录下

测例生成器

测例生成器的思路就是使用c++标准库中的set来记录当前树中的所有结点，需要插入一个随机数时，不断生成随机数并查询该随机数是否在set中，直到找到一个不存在于set中的随机数，将该随机数插入set中，并输出插入信息。输出删除或查询操作时，通过advance(it, rand() % data.size())的方法实现随机选取set中的某个元素查询或删除。

测试结果

• 五种不同类型的数据在两棵树下的运行时间：

类型	local	qd	queue	rand	readonly
Avl	0.1216 s	0.1340 s	0.1556 s	0.1434 s	0.0778 s
Splay	0.1184 s	0.1556 s	0.1996 s	0.1558 s	0.1186 s

• 不同规模的local类型数据在两棵树下的运行时间：

n	50000	100000	200000	300000	400000	500000
Avl	0.031 s	0.062 s	0.125 s	0.187 s	0.265 s	0.328 s
Splay	0.062 s	0.062 s	0.125 s	0.171 s	0.281 s	0.312 s

具体结果保存在/result目录下

数据分析

总体结论

多数情况下，Splay树的性能都落后于Avl树，而在少数有优势的情况下，这种优势又微弱到几乎可以忽略不计。

结论及分析

Splay树付出的额外时间用于旋转

Splay树的复原需要用到splay操作，伸展操作需要将最后访问的结点旋转至根，尽管Avl树在一些特殊情况下也会出现多次旋转至根的情况（删除操作），但和Splay树任何操作都需旋转至根相比，Avl树的旋转次数还是要远远小于Splay树，而对于删除操作不是很多的数据（比如readonly类型），Avl在旋转次数上的优势会更加明显，这也就解释了相比其它数据类型，为什么readonly类型下Avl性能会比Splay性能快很多。

为了具体说明Splay树和Avl树在旋转次数上的差异，我又做了进一步的实验，对于前面生成的local类型数据，记录以这些数据为输入时，两棵树的旋转次数（即zig/zag函数的调用次数）

	Splay旋转次数	Splay时间消耗(s)	Avl旋转次数	Avl时间消耗(s)
1	500108	0.140	14219	0.109
2	497590	0.125	14082	0.109
3	495890	0.14	14290	0.14
4	493757	0.078	14152	0.125
5	489016	0.109	14067	0.125

实验结果显示旋转次数上，Splay树和Avl树存在数量级上的差异，而Splay树相比Avl树运行更快的几组数据，也恰恰是Splay旋转次数和Avl旋转次数之比较小的几组。

Splay树的思想是通过额外的旋转将最近访问的结点旋转至树根，从而让局部数据的访问和操作更加便利，而在除了local类型的数据中，由于没有局部性条件，所以Splay付出额外旋转的成本并没有带来预期的收益，导致其效率不如Avl树。而在我设计的local类型数据中，Splay确实通过付出额外的旋转成本获得了查询时的高效，但这种高效并不十分惊艳。

数据规模增大并不会使Splay树效率提升

通过观察不同规模的local类型数据在两棵树下的运行时可以发现一些有趣的现象：在数据规模较小（n=50000）时，Splay树落于下风，而随着n的增大，Splay树开始显现出一定的优势，但这种优势并不像我们预期的那样随着n的增大而增大，同时它还具有一定的不稳定性（ n=400000时Avl树更优），不过对于为什么会产生这样的现象，还给不出很好的解释。

总结

Avl和Splay树作为两种常见的平衡树，在操作数远大于树结点个数的前提下，大O记号分析表明其均摊时间效率相同，但在具体实验表现中，Av的整体表现是略优于Splay树的。事实上，在尝试构造测例的过程中，的确可以通过构造一些具有极端局部性的数据来让Splay体现优势，这说明Splay树的优势只有在一些特殊情况下才能体现出来，而就总体而言，Avl树对数据的敏感度更低，性能也更优。