比较基于旋转的树平衡算法的成本 该项目实现了三种算法,可以通过旋转来完全平衡二叉搜索树,如Luccio等人在论文中所述。 这些算法采用任意二叉树S和几乎完整的二叉树T ,它们都包含相同的密钥集,并且旋转S的边直到S等于T。 作者在定理1到3中声称,这些算法将S精确地或上限地转换为T。 该项目从经验上验证了这些定理。 我广泛使用了基于属性的测试(特别是 )来测试我的二进制搜索树和树平衡算法实现的功能正确性。 能够指定方法必须具有的高级属性,而无需手动生成输入数据,这有助于发现许多错误。 参见 。 这是乔治·梅森大学算法分析课程的最后一个项目。 假设条件 在实现算法时,我做了以下假设: 在定