这是DSA 2023 Spring LAB 3的BBST的解题报告，介绍了在实验中实现AVL树和Splay树，并设计测例分析两种树效率特点的过程。
数据结构的实现过程及复杂度分析
我所实现的是 AVL 树 和 Splay 树
AVL 树
- AVL 树中的每个节点，维护其高度和从左子树还是右子树中获得这一高度的标记。
- 插入、删除和查询的过程，在逻辑上比较一致，都是从根节点开始，按照当前节点的key和目标key的大小关系，决定下一步走向左子树还是右子树，直到找到目标位置。不同的是，在插入和删除后，会计算当前节点高度和左右子树高度差，并在必要时进行重平衡操作。
- 单次重平衡和高度计算的复杂度均为$O(1)$，即使重平衡沿搜索路径不断向上，也不超过$O(logn)$。而插入、删除、查询的过程耗时与搜索路径长度成正比，不超过树高$O(logn)$。因此，插入、删除和查询操作的总的时间复杂度均为$O(logn)$。（n表示总计插入的节点个数，不是题中的n）
- 我采用指针方式构建树，在新建节点时new一个空间，在删除节点时delete一个空间，所有的信息都占用常数大小空间，因此空间复杂度为$O(n)$。
Splay 树
- Splay 树中的每个节点，维护其指向父节点的指针。
- 插入、删除和查询的过程，在逻辑上比较和 AVL 树一致。不同的是，在找到节点后，会将这个节点 splay 到根节点。对于删除操作，会在 splay 到根节点后再删除，之后考察这个节点的左右子树。如果右子树为空，则左子树就是剩下的树；反之，则在右子树中找最小节点（即被删除节点的直接后继），将它 splay 成为根节点，让左子树接在它的左边。
- splay 过程中，采用双层伸展策略，仅在与目标位置距离为1的情况下进行单层伸展。
- 可见，插入、删除和查询单词操作复杂度仍为$O(logn)$，而 Splay 树的 splay 操作均摊复杂度为$O(logn)$，所以可以认为 Splay 树单次操作均摊复杂度为$O(logn)$。
- 空间复杂度仍然为$O(n)$。
设计测例的思路
- 讨论 Splay 树和 AVL 树的优劣，就需要对数据的局部性进行设计。为了得到局部性较好的数据，我使插入和查询操作的key在随机生成之后，按照顺序由小至大排列，这样可以确保上一次操作完成后，下一次操作的目标数据就在原数据的附近，也就是说，局部性好。作为对比，我计划构建一组key顺序完全随机的数据，这个数据局部性显然会更差。（这一组变量，我简称为key有序和key无序）
- 受 HASHFUN 的启发，我还想到：是否可以研究操作顺序对效率的影响？为此，我设计了一组完成所有插入后再删除、完成所有删除后再查询的数据，并构造一组插入、删除和查询操作随机分布的数据作为对比。（这一组变量，我简称为操作有序和操作无序）
- 其他无关变量，如：插入、删除、查询操作各自的次数，key的最大值等，控制不变。
测例如何生成
- 在数据生成器中，先得到一组两组随机生成的数组，分别代表插入的key和查询的key。他们都是无序且不重复的。
- 如果这组数据需要key有序，则对以上两组数分别排序。
- 删除操作需要控制被删除的key此前在插入数组中出现过，为此，构建数组restA，表示在插入数组中出现过，且还没有被删除的key。每次插入一个key，就将其加入restA；删除这个key时，将它从restA中删除。
- 如果这组数据需要操作有序，那么先生成所有的插入操作，再生成所有的删除操作，最后生成所有的查询操作。
- 如果这组数据需要操作无序，那么生成每次操作时，随机在0、1、2中生成一个数，来决定这一次该生成哪种操作。如果此时随机数结果表示要生成的操作已经达到了设定的该操作总次数，或者计划生成删除操作但restA为空，则重新选取随机数，直到满足条件或者所有数据生成完毕为止。
- 无关变量控制如下：
插入次数：120000
删除次数：40000
查询次数：1000000
最大key值：4000000
最终，得到如下四组数据：
| 组数 | key情况 | 操作情况 |
|---|---|---|
| 第1组 | key有序 | 操作有序 |
| 第2组 | key无序 | 操作有序 |
| 第3组 | key无序 | 操作无序 |
| 第4组 | key有序 | 操作无序 |
不同数据结构在不同测例下的性能描述及原因分析
性能描述
使用程序完成运行的耗时作为性能描述标准，表格中数据单位均为毫秒。
| 实验组数 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| AVL 树 | 5838 | 6733 | 6468 | 5679 |
| Splay 树 | 5714 | 7063 | 6751 | 5612 |
原因分析
- 对比第1组和第4组中两种树的耗时情况，可以发现：在 key 有序的情况下，Splay 树性能优于 AVL 树。这符合理论分析，因为 Splay 树更好地利用了数据的局部性，节省了时间。
- 对比第2组和第3组中两种树的耗时情况，可以发现：在key无序的情况下，Splay 树性能劣于 AVL 树。这可能是因为 Splay 树做的结构调整操作更多，但数据局部性差，使得这些耗时操作努力白费。
- 不论对于哪种树，有序操作性能劣于无序操作（第1、4组对比，第2、3组对比）。这可能是因为如下两个原因：
- 有序操作时，树的形态不稳定，需要更多调整才能满足要求；无序操作时，结束前任一时刻的数据分布更加均匀，需要做的调整次数更少。
- 有序操作时，查询操作在最后完成，所有节点均已插入，树的规模较大；无需操作下，查询操作分散完成，很多查询操作进行时还有很多节点没有插入，树的规模较小。证据是：我检查了第2、3组输出，发现第3组的100万次查询有 2155 次以 -1 输出，而第2组则只有 25 次。这可以支持上述论断，因为两组数据的 key 均为随机生成，树的规模小才会多出很多无法查询到的值。