BBST

CST LAB3

BBST

一、数据结构

我所实现的数据结构为 AVLTree 与 SplayTree, 现说明两个数据结构的核心接口与公共接口实现方法.

1. AVLTree

struct AvlNode {
    AvlNode* l; // 左孩子.
    AvlNode* r; // 右孩子.
    int v;      // 节点值.
    int h;      // 节点高度.
};

struct AvlTree {
    int cnt;       // 节点计数器.
    AvlNode* Root; // 根节点.
    AvlNode f[N];  // 节点数组.
}

参考了这篇文章实现了 AvlNode 结构体, 并以数组形式给出 AvlTree 结构.

1.1 Maintain()

Maintain(current) 首先根据当前节点的平衡因子 BanlanceFactor(current) 判断是否需要调用 LeftRotate() 与 RightRotate() 接口进行左旋、右旋重构, 同时利用这两个接口实现了 LeftAdjust() 与 RightAdjust() 接口进行双旋重构.

1.2 Insert() 与 Remove()

AVLTree 在 Insert() 与 Remove() 后首先通过 PushUp(current) 进行高度更新, 将当前节点高度更新为子节点的最大高度加 $1$.

AVLTree 在 Insert() 与 Remove() 中 PushUp(current)后通过 Maintain(current) 进行重平衡.

1.3 Search()

AVLTree 在 Search() 中依次判断查询值与当前节点值的大小关系, 若不相等则决定深入搜索左或右子树. 在搜索时使用 AvlNode* tmp 记录数值不大于查询值的最大节点. 若查询得到目标节点, 直接返回; 否则到达叶节点, 若节点值小于查询值, 根据查询方法必为数值小于查询值的最大节点, 直接返回; 若节点值大于查询值, 则返回 tmp 节点.

1.4 复杂度分析

一高度为 $h$ 的 AVLTree 至少有 $S(h) = fib(h) = \varPhi^h$ 个节点, 故大小为 $n$ 的 AVLTree 的高度为 $O(\log n)$.

每次 Search() 操作的复杂度正相关于树高, 为 $O(\log n)$;

每次 Insert() 导致的失衡通过至多一次单旋或者双旋调整即可解决, 复杂度为 $O(1)$, 总复杂度取决于搜索高度, 为 $O(\log n)$;

每次 Remove() 导致的失衡可能从删除节点到根节点均需进行旋转调整, 旋转次数至多为 $O(\log n)$, 总体复杂度仍为 $O(\log n)$;

综上所述, AVLTree 的基本操作接口的时间复杂度均为 $O(\log n)$, 共计 $n$ 次操作, 总体时间复杂度为 $O(n\log n)$.

2. SplayTree

struct SplayNode {
    int son[2]; // 孩子.
    int father; // 父亲.
    int val;    // 节点值.
};

struct SplayTree {
    SplayNode t[N]; // 节点数组.
}

参考了这篇文章实现了 SplayNode 结构体, 并以数组形式给出 SplayTree 结构.

2.1 Splay()

首先实现了 Rotate() 接口进行单旋操作, 接着利用 Rotate() 接口实现了 Splay() 接口进行双旋操作.

2.2 Insert()

SplayTree 在 Insert() 时逐层查询需要插入节点的位置, 直到到达叶节点. 插入节点后执行 Splay(pointer, 0) 将其伸展至根节点即可.

2.3 Remove()

SplayTree 在 Remove() 中首先得到待删除节点的前驱与后继 pred与 succ. 因为预先插入了最小与最大节点, 这样的前驱与后继总是存在的. 通过 Splay(pred, 0); Splay(succ, pred); 将 pred 旋转至根节点, 并将 succ 旋转为其右孩子. 根据 BBST 的定义, 此时待删除节点必为 succ 的左孩子, 将其置零即可.

2.4 Search()

SplayTree 在 Search() 中依次判断查询值与当前节点值的大小关系, 若不相等则决定深入搜索左或右子树. 在搜索时使用 int tmp 记录数值不大于查询值的最大节点值. 若查询得到目标节点, 直接返回; 否则到达叶节点, 若节点值小于查询值, 根据查询方法必为数值小于查询值的最大节点, 直接返回; 若节点值大于查询值, 则返回 tmp 即可.

同时, SplayTree 对于搜索到的节点需要进行 Splay() 操作, 将其伸展至根节点.

2.5 复杂度分析

根据讲义 $P664-P668$ 对 SplayTree 的势能分析, 对于 SplayTree 的连续 $m\gg n$ 次 Insert(), Remove(), Search() 操作的均摊时间复杂度为 O(logn).

二、测例设计

1. 测试环境

操作系统: Linux version 4.4.0-22621-Microsoft.

编译器: gcc version 5.4.0 (GCC).

2. 设计思路

一共设计了四类测例, 存放在本地 /Data 路径中, 其相应生成器文件存放在本地 /Generator 路径中：

• 第一类测例模拟完全随机进行插入、删除、查找操作. 操作数分别为 100, 10000, 1000000 次. 对应生成器文件为 generator_1.cpp, 测例文件为 01.in ~ 03.in.
• 第二类测例模拟先插入后删除操作, 分为两组进行, 第一组 80% 次操作进行插入操作, 20% 次操作进行删除操作; 第二组 60% 次操作进行插入操作, 40% 操作进行删除操作. 操作数分别为 100, 10000, 1000000 次. 对应生成器文件为 generator_2.cpp, 测例文件为 04.in ~ 09.in.
• 第三类测例模拟先插入后查找操作, 且查找范围为全局数值, 分为两组进行, 第一组 80% 次操作进行插入操作, 20% 次操作进行全局查找操作; 第二组 20% 次操作进行插入操作, 80% 操作进行全局查找操作. 操作数分别为 100, 10000, 1000000 次. 对应生成器文件为 generator_3.cpp, 测例文件为 10.in ~ 15.in.
• 第四类测例模拟先插入后查找操作, 且查找范围为局部数值, 数值极差不超过总操作数的平方根, 分为两组进行, 第一组 80% 次操作进行插入操作, 20% 次操作进行局部查找操作; 第二组 20% 次操作进行插入操作, 80% 操作进行局部查找操作. 操作数分别为 100, 10000, 1000000 次. 对应生成器文件为 generator_4.cpp, 测例文件为 16.in ~ 21.in.

3. 测例生成

使用 bitmap 数据结构记录 Tree 中数据的存在情况. 如果 bitmap 某一位设置为 1, 则相应值的节点存在于树中, 只能进行删除操作; 如果 bitmap 某一位设置为 0, 则相应值的节点不存在于树中, 只能进行插入操作。

// 随机数种子.
srand((int)time(0));

使用当前时间作为随机数种子, 充分保证了生成数据的随机性. 尝试生成一个 Insert() 数据点时, 随机访问一个位置, 若 bitmap->test(rand_num) == 0, 则可以在该处进行插入操作, 否则随机查询下一个位置; 尝试生成一个 Remove() 数据点时, 随机访问一个位置, 若 bitmap->test(rand_num) == 1, 则可以在该处进行插入操作, 否则遍历查询其之后的位置, 直到找到一个可以删除的数据点; 尝试生成一个全局 Search() 数据点时, 随机访问一个位置即可; 尝试生成一个局部 Search() 数据点时, 首先随机访问一个位置, 并在一定范围内随机生成数据即可.

4. 测试脚本

编写了 avl.sh 脚本对 AVLTree 数据结构进行测试.

#avl.sh
#!/bin/bash
for i in {1..21}
do
    echo "Test Case $i:" >> avl.out
    { time ./avl <Data/$i.in >Data/$i.out; } 2>> avl.out
done

编写了 splay.sh 脚本对 SplayTree 数据结构进行测试.

#splay.sh
#!/bin/bash
for i in {1..21}
do
    echo "Test Case $i:" >> splay.out
    { time ./splay <Data/$i.in >Data/$i.out; } 2>> splay.out
done

三、性能分析

1. generator_1.cpp 数据

对应于 01.in ~ 03.in.

数据规模	AVL	Splay
1e2	time:0.027s	time:0.028s
1e4	time:0.026s	time:0.153s
1e6	time:0.540s	time:0.737s

• 在完全随机数据下, AVLTree 性能优于 SplayTree.
• 由于数据的随机性, SplayTree 数据访问的局部性差, 缓存策略效果不大, 其每次操作都需进行 $O(\log n)$ 次的旋转, 性能不如 AVLTree. 随着数据规模的增大, AVLTree 的性能优势逐渐扩大.

2. generator_2.cpp 数据

对应于 04.in ~ 09.in.

数据规模	AVL	Splay
1e2(8:2)	time:0.022s	time:0.015s
1e2(6:4)	time:0.021s	time:0.015s
1e4(8:2)	time:0.026s	time:0.023s
1e4(6:4)	time:0.025s	time:0.020s
1e6(8:2)	time:1.455s	time:1.730s
1e6(6:4)	time:1.273s	time:2.057s

• 在先插入后删除数据下, 数据规模较小时 SplayTree 性能占优, 数据规模较大时 AVLTree 性能占优.
• 数据规模较小时, 两种数据结构插入与删除操作的效率相近, SplayTree 性能略占优; 数据规模较大时, AVLTree 相较 SplayTree 在删除操作的优势体现的更为明显.

3. generator_3.cpp 数据

对应于 10.in ~ 15.in.

数据规模	AVL	Splay
1e2(8:2)	time:0.021s	time:0.023s
1e2(2:8)	time:0.027s	time:0.026s
1e4(8:2)	time:0.025s	time:0.024s
1e4(2:8)	time:0.025s	time:0.026s
1e6(8:2)	time:1.232s	time:1.512s
1e6(2:8)	time:0.739s	time:1.288s

• 在先插入后删除数据下, 数据规模较小时 AVLTree 性能略占优, 数据规模较大时 AVLTree 性能明显占优.
• 数据规模较小时, AVLTree 的性能略微优于 SplayTree. 随着数据规模的增大, 数据访问的局部性下降, AVLTree 和 SplayTree 性能均略微下降; 由于 SplayTree 每次操作都需进行 $O(\log n)$ 次的旋转, 受到的影响较大, 因此 AVLTree 性能明显占优.

4. generator_4.cpp 数据

对应于 16.in ~ 21.in.

数据规模	AVL	Splay
1e2(8:2)	time:0.021s	time:0.020s
1e2(2:8)	time:0.021s	time:0.022s
1e4(8:2)	time:0.026s	time:0.023s
1e4(2:8)	time:0.025s	time:0.024s
1e6(8:2)	time:1.094s	time:1.073s
1e6(2:8)	time:0.358s	time:0.276s

• 在先插入后局部查找数据下, 数据规模较小时两种数据结构性能相近, 数据规模较大时 SplayTree 性能略占优.
• SplayTree 的理想优势在于数据访问的局部性, 在连续局部查找下, 搜索的数据越发集中, 随着数据规模的增大与查找操作比例的提高, SplayTree 的优势逐渐体现.

四、小结

在数据较为随机或无法确定数据局部性时, 应选用 AVLTree, 它的时间常数小, 单次时间复杂度较为稳定. 在数据访问的局部性较强时, 应选用 SplayTree, 可以实现较优的性能.