在本次lab中，需要实现两种平衡树的数据结构，实现插入元素、删除元素、查找元素、查找某个数的前驱与后继的操作，并分析两种平衡树的性能。

一、数据结构的实现过程

在本次lab中，我选择了AVL树与splay树两种数据结构进行了实现。

1. AVL树的实现

AVL树的平衡条件为：每个结点的左右子树的高度之差的绝对值不超过\(1\)。这个值被称为平衡因子。事实上，在进行结点的插入与删除时，都有可能破坏AVL树的平衡状态。因此，AVL树实现中的核心目标就是在操作的同时执行对平衡状态的维护。
首先，我们定义存储数据的结构体AVL_node和基本的辅助函数。update函数用于更新结点的高度，定义为两子树高的最大值加一。get_balance函数用于获取当前结点的平衡因子。考虑到对称性，此处直接获取左子树的高与右子树的高之差。 

struct AVL_node {
    int ch[2], val, height;//左右儿子，结点值，高度
} t[N];
int total;//结点总数

void update(int &u) {
    t[u].height = max(t[t[u].ch[0]].height, t[t[u].ch[1]].height) + 1;
}//更新结点的高度

int get_balance(int u) {
    return t[t[u].ch[0]].height - t[t[u].ch[1]].height;
}//获取平衡因子

接下来实现AVL维护平衡的核心操作——左旋和右旋操作。这两个操作是完全对称的，因此以右旋为例进行说明。
对于某个不平衡的结点u，若其左子树高与右子树高的差大于\(1\)（事实上，由于我们在插入和删除结点时只对一个结点进行操作，对树高的影响不超过\(1\)，因此这个差值最多为\(2\)），则需要进行右旋来保持平衡。将其左儿子的右儿子变为自己的左儿子，其自身变为其左儿子的右儿子，之后更新对应结点，这样就实现了重新平衡。 

void right_rotate(int &u) {
    int p = t[u].ch[0];
    t[u].ch[0] = t[p].ch[1];
    t[p].ch[1] = u;
    update(u);
    update(p);
    u = p;
}//右旋，左旋函数的实现完全对称

现在我们就可以进行AVL树的插入、删除与查找了。

定义插入函数insert(int &u, int x)，插入结点时，我们从根开始根据数据的大小向两侧递归。若遇到不存在的结点，则在此处新建即可： 

if(!u) {
    u = ++total;
    t[u].val = x;
}

若插入的值比当前结点的值小，则根据二叉搜索树的性质应插入左子树，往左子树递归调用insert(t[u].ch[0], x)即可。注意此时我们要对平衡性进行检查与维护。若当前结点u的平衡因子为\(2\)，则说明需要进行旋转来保持平衡。若u的左儿子的平衡因子为\(1\)，则对u进行一次右旋操作即可；否则需要先对左儿子进行一次左旋操作，再对u进行一次右旋操作。这样可以起到维护平衡的作用。 

else if(x < t[u].val) {
    insert(t[u].ch[0], x);
    if(get_balance(u) == 2) {
        if(get_balance(t[u].ch[0]) == 1) right_rotate(u);
        else left_rotate(t[u].ch[0]), right_rotate(u); 
    }
}

若插入的值比当前结点的值大，则往右子树递归调用insert(t[u].ch[1], x)即可。之后维护平衡的操作与上一情况完全对称，此处则不再赘述。在平衡维护完毕后，需要在u结点处进行一次更新。

接下来定义删除函数del(int &u, int x)，删除结点时也是从根开始根据数据的大小向两侧递归。当前结点不存在，则直接返回；若需要删除的值小于当前结点值，则往左子树递归调用del(t[u].ch[0], x)；若需要删除的值大于当前结点值，则往右子树递归调用del(t[u].ch[1], x)。
若当前结点就是需要删除的结点，此时继续分类讨论。若该结点为叶子结点，则直接令u=0删除即可。若某方向的子结点不存在，则用另一方向的子结点代替其本身即可。若两侧子结点均存在，则应找到当前结点的前驱结点，用前驱的值更新当前结点值，之后在左子树递归调用即可。实现如下： 

if(!t[u].ch[0] && !t[u].ch[1]) u = 0;
else if(!t[u].ch[0]) u = t[u].ch[1];
else if(!t[u].ch[1]) u = t[u].ch[0];
else {
    int p = t[u].ch[0];
    while(t[p].ch[1]) p = t[p].ch[1];
    t[u].val = t[p].val;
    del(t[u].ch[0], t[p].val);
}

删除结点之后，同样需要进行平衡维护。若当前结点的平衡因子为\(2\)，且左儿子的平衡因子为\(-1\)，则此时需要先对左儿子进行一次左旋操作，再对u进行一次右旋操作；否则直接对u进行右旋操作即可。 

if(get_balance(u) == 2) {
    if(get_balance(t[u].ch[0]) == -1) left_rotate(t[u].ch[0]), right_rotate(u);
    else right_rotate(u);
}

另外仍有一种完全对称的情况，也即当前结点的平衡因子为\(-2\)，所进行的旋转操作与判定条件同样完全对称，此处不再赘述。在平衡维护完毕后，需要在u结点处进行一次更新。

之后的查询前驱和后继的操作则更为简单。以查询前驱为例（查询后继操作也是完全对称的），从根结点开始递归，最终若无法查询则返回一个设定的最小值；若查询的值比当前结点值小，则向左子树递归；否则向右子树递归，最终的答案与当前结点值取max。实现如下： 

int pre(int u, int x) {
    if(!u) return -1e8;
    if(t[u].val >= x) return pre(t[u].ch[0], x);
    return max(t[u].val, pre(t[u].ch[1], x));
}//寻找前驱，后继完全对称

综上，我们实现了一棵AVL树。

2. splay树的实现

splay树通过将结点旋转到根结点的方式来保持平衡。首先定义存储数据的结构体splay_node和基础的辅助函数update，用于更新当前结点的大小： 

struct splay_node {
    int father, cnt, ch[2], val, size;
    //父亲，重复次数，左右儿子，结点值，结点规模
} t[N];
int root;//根结点
int total;//结点总数
void update(int x) {
    t[x].size = t[t[x].ch[0]].size + t[t[x].ch[1]].size + t[x].cnt;//左子树+右子树+自身的重复个数
}//更新

splay树的操作基础为旋转函数rotate。对于结点x，获取其父亲y和祖父z，以及x相对y的位置z（0表示左儿子，1表示右儿子），将z的原来y所在的位置变为x，将x的z ^ 1这一侧的儿子变为y的z侧儿子，之后对父子连接关系一一更新，最后用update函数上传修改即可。具体实现如下： 

void rotate(int x) {
    int y = t[x].father, z = t[y].father;
    int k = (x == t[y].ch[1]);//0表示左儿子，1表示右儿子
    if(z) t[z].ch[y == t[z].ch[1]] = x;
    t[x].father = z, t[y].ch[k] = t[x].ch[k ^ 1];
    if(t[x].ch[k ^ 1]) t[t[x].ch[k ^ 1]].father = y;
    t[x].ch[k ^ 1] = y, t[y].father = x;
    update(y), update(x);//更新修改
}//旋转

有了旋转操作之后，我们就可以进一步进行核心的伸展操作splay。这一操作主要是用于解决三点共线——x相对于父亲y的位置以及y相对于祖父z的位置均相同的情况。若出现了上述情况，则先对y进行旋转，之后再旋转x；否则直接对x进行旋转即可。实现如下： 

void splay(int x, int target) {//将x旋转为target的儿子，target=0表示旋转到根
    while(t[x].father != target) {
        int y = t[x].father;
        int z = t[y].father;
        if(z != target) (t[z].ch[0] == y) ^ (t[y].ch[0] == x) ? rotate(x) : rotate(y);//根据是否共线来进行旋转
        rotate(x);//最后一定要旋转x
    }
    if(target == 0) root = x;
}//伸展

有了splay操作，我们就可以进行splay树的结点插入。从根结点开始，若当前结点存在且并没有移动到要插入的值，则根据大小关系向对应位置的子树找： 

while(u && t[u].val != x) {
    fa = u;
    u = t[u].ch[x > t[u].val];//向对应位置的子树找
}

若存在这个值，则出现次数加一；若不存在，则新建一个节点，并且初始化对应的结点信息。 

if(u) t[u].cnt++;
else {
    u = ++total;
    if(fa) t[fa].ch[x > t[fa].val] = u;
    t[u].ch[0] = t[u].ch[1] = 0;
    t[total].father = fa, t[total].val = x;
    t[total].cnt = 1, t[total].size = 1;
}//不存在就新建

在插入操作结束后，需要将当前结点旋转至根结点以保持平衡。

对于splay树的查找功能，我们首先定义函数find，作用为查找x的位置，并且把x旋转到根。 

void find(int x) {
    int u = root;
    if(!u) return;//树空情况
    while(t[u].ch[x > t[u].val] && x != t[u].val) u = t[u].ch[x > t[u].val];
    //跳转到对应的那个儿子 
    splay(u, 0);
}//查找x的位置，并且把x旋转到根

之后就可以方便地查找前驱和后继。这两个操作完全对称，以下以前驱为例。首先调用一次find函数，找出待查找值的位置，之后从根结点开始，先向左子树移动一次，之后不断向右子树移动至叶子，即可找到前驱所在的位置。 

int pre(int x) {
    find(x);
    int u = root;
    if(t[u].val < x) return u;
    u = t[u].ch[0];
    while(t[u].ch[1]) u = t[u].ch[1];
    return u;
}//查找前驱，查找后继方法完全一致，方向相反。

最后，利用查找前驱和后继的方式，可以方便实现删除函数del。我们首先获取待删除元素x的前驱last和后继next，之后将前驱旋转到根，将后继旋转到前驱，则此时x就是后继last对应的左儿子。之后就可以进行元素修改以删除当前值。 

int temp = t[next].ch[0];//前驱后继已经旋转到位，x为后继的左儿子
if(t[temp].cnt > 1) t[temp].cnt --, splay(temp, 0);
else t[next].ch[0] = 0;

综上所述，我们实现了一棵splay树。

二、数据结构的复杂度分析

对于两种数据结构，空间复杂度自然都是\(O(n)\)的，因为空间开销都是为了存储\(n\)个结点的信息。以下我们将会讨论二者进行相关操作的时间复杂度。

1. AVL树操作的时间复杂度

我们首先研究一棵AVL树达到平衡后的树高。设\(f_n\)表示高度为\(n\)的AVL树所包含的最少结点数，则我们有如下的等式成立：

则可以知道\(f_n+1\)是一个斐波那契数列，且

于是对于树高我们有

于是我们可知结点数为\(n\)的AVL树的树高为\(O(\log{n})\)。

由树高可知，AVL树上的查询操作时间复杂度为\(O(\log{n})\)。插入结点时，每次插入对平衡造成的影响可以通过一次单旋或双旋来解决，维护的深度去取决于向下搜索的深度，因此插入操作的时间复杂度为\(O(\log{n})\)。删除结点时，最劣情况下从删除的结点到根结点的路径上都需要进行平衡维护，旋转次数为\(O(\log{n})\)，结合查询操作的时间复杂度，可得整体删除的时间复杂度为\(O(\log{n})\)。

综上所述，AVL树上插入、删除、查询操作的单次时间复杂度均为\(O(\log{n})\)。

2. splay树操作的时间复杂度

设一次操作的当前结点为x，其父亲为p，祖父为g。我们采用势能分析法来分析splay操作的均摊时间复杂度。设一棵splay树有\(n\)个结点，进行了\(m\)次splay步骤，令\(w(x)=\log{(\text{size}(x))}\)，定义势能函数为\(\varphi=\sum w(x),\varphi(0) \leq n\log{n}\)，第\(i\)次操作后势能为\(\varphi(i)\)。结合zig与zag操作的对称性，我们只需要对zig，zig-zig，zig-zag三种操作分析复杂度。

  1. zig操作，势能变化量为

  2. zig-zig操作，势能变化量为

  3. zig-zag操作，势能变化量为

由上可见，三种操作的势能变化量最后都可以放缩为以\(3(w’(x)-w(x))\)为上界。

我们设

同时设splay操作一次访问了\(x_1,\cdots,x_n\)结点，最终根结点为\(x_1\)，则我们有

进一步可得

因此可得基于splay的插入、删除、查询操作的单次均摊时间复杂度均为\(O(\log{n})\)。

三、效率测试

1. 测例的设计与生成

在本次lab中，我一共设计了如下三种测例。

  1. 随机进行插入、删除、查询操作，操作总次数为\(1000\)次与\(100000\)次。为此编写了makedata_rand.cpp。在具体实现时，通过读取命令行参数的方式读取操作次数\(n\)，之后利用一个check数组来记录数据范围内某个数当前状态——是否存在于树中。若存在树中，则可以删除，不能再次插入；若不在树中，则可以插入，不能进行删除，在选取数进行操作时均采取了随机数对数据范围取模的方式。

  2. 先进行插入操作，后进行删除操作，设计多组测例使插入操作的占比不同。最终生成时，操作总次数为\(100000\)次与\(1000000\)次，插入操作的占比为\(60 \%\)和\(90 \%\)，共生成四个测例。为此编写了makedata_i+d.cpp。由于插入和删除具有先后顺序，因此可以通过较为简单的方法选取数进行操作。设数据上界为\(m\)，我们将\([0,m]\)范围内所有数加入一个vector中，之后对这个vector随机shuffle，然后按顺序取，即可保证插入数据的随机性。在插入数据的同时，用另一个vector记录已经插入的数，插入完成后吗对这个vector进行上述相同操作，即可保证删除数据的随机性，同时删除的数据一定存在。

  3. 先进行插入操作，后进行查询操作。设计两组测例，其中一组为随机查询，另一组为固定一点查询。最终生成时，两组的操作总次数均包含\(100000\)次与\(1000000\)次两种情况共四个测例。为此编写了makedata_i+s.cpp。设数据上界为\(m\)，我们将\([0,m]\)范围内所有数加入一个vector中，之后对这个vector随机shuffle，然后按顺序取，即可保证插入数据的随机性。在进行查询时，若随机查询，则在全部数据范围内随机一个数即可；若定点查询，在本实验中设置此顶点为整个数据范围的中位数。

2.测试结果记录

随机插入、删除、查询操作：

结果1

先插入后删除操作：
|操作次数|插入操作所占比例|树的种类|所花时间|
结果2

先插入后查询操作（查询方式为0表示随机查询，查询方式为1表示定点查询）:
结果3

3. 测试结果分析

整体结果

整体上，我们可以显而易见地看出，AVL树的性能是显著优于splay树的性能的，偶有splay树优于AVL树的情况，优势也可以忽略不计。

原因分析

splay树中，为了维护操作后树的平衡，对每个操作的结点都需要将其旋转至根结点处。而在AVL树中，至多只有删除操作可能需要一直旋转维护到根结点处。因此，尽管splay树和AVL树单次操作的均摊时间复杂度均为\(O(\log{n})\)，但splay树的操作显然具有更大的常数，导致效率更低。

具体测例结果分析

  • 随机插入、删除、查询操作
    由于随机性，几乎每次操作splay树都要将当前结点旋转到根结点，总体旋转次数应大于AVL树，因此性能较差，且这种差距会随着数据规模增大而越发显著。

  • 先插入后删除操作
    AVL树的插入操作效率优于splay树，而二者的删除操作效率相当，因此理论上，插入操作的占比越大，AVL树的性能优势越明显。而实际数据也验证了这一点。

  • 先插入后查询操作
    考虑到splay树数据访问的结构性，定点查询的效率应该高于随机查询的效率。事实也确实如此，但是仍然是AVL树的效率更高。

综上所述，我们得出结论：在实际应用中，AVL树的性能高于splay树的性能。