Gra*_*raf 9 testing algorithm avl-tree data-structures
家伙.我想我已经创建了一个AVL树实现,但由于AVL Tree是一个非常复杂的结构,我需要测试它.所以问题是 - 我该如何测试呢？你有什么想法吗？到目前为止,我有以下测试:
基本健全性检查 - 检查每个节点高度是否等于最大值.子节点的高度+ 1,余额在[-1,1],左子键<此节点的键<右子键,并且没有循环引用(如节点的左子节点本身就是节点);
检查AVL树上的inorder遍历(以及整个二进制搜索树)将按顺序从底层集返回值;
检查AVL树的高度是否严格小于1.44*log2(N + 2)-1(N是元素数) - 由AVL树创建者证明;
视觉检查 - 效果不好,我尝试画一棵树(第一行的rootnode,下一行的直接孩子,第三行的rootnode直接孩子的孩子,等等),但这只适用于小树,大树变得一团糟;
(?????)俄罗斯维基百科说,实验证明,两次插入需要一次重新平衡,五次移除也需要一次重新平衡,但实际上是这样吗？英语维基百科对此一无所知,对于我的AVL,需要进行两次插入或四次删除所需的重新平衡,这并不完全相同.
也许这些测试已经足够,但如果还有更多测试,不难实现,为什么不这样做？
Gri*_*fin 28
根据所有这些答案的精神,我想我会提供一些具体的例子来证明基本案例是不够的.
考虑以下AVL平衡二叉树进行插入操作:
20+ 20+ __20+__
/ / \ / \
4 4 26 4 26
/ \ / \ / \
3 9 3+ 9 21 30
/ / \
2 7 11
将8或15(例如)插入任何这些树中将触发基本相同的左/右重新平衡,但最终结果对于每个树和插入值显着不同.也就是说,插入值的最终着陆位置和节点(4)和节点(20)的最终平衡因子完全取决于节点(4)下的右子节点的相对值 - 如果有的话.完全根据这些案例中的任何一个进行的测试不一定证明任何其他案例的正确性.注意:node(4)必须首先针对这些情况进行平衡; 节点(4)中的初始不平衡最终对节点(20)没有影响.
案例1a:插入15
20+ 20++ 20++ 15
/ / / / \
4 => 4- => 15+ => 4 20
\ /
15 4
案例2a:插入15
20+ 20++ 20++ 9
/ \ / \ / \ / \
4 26 => 4- 26 => 9+ 26 => 4+ 20
/ \ / \ / \ / / \
3 9 3 9- 4+ 15 3 15 26
\ /
15 3
案例3a:插入15
__20+__ _20++_ __20++_ ___9___
/ \ / \ / \ / \
4 26 => 4- 26 => 9+ 26 => 4+ __20__
/ \ / \ / \ / \ / \ / \ / \ / \
3+ 9 21 30 3+ 9- 21 30 4+ 11- 21 30 3+ 7 11- 26
/ / \ / / \ / \ \ / \ / \
2 7 11 2 7 11- 3+ 7 15 2 15 21 30
\ /
15 2
案例1b:插入8
20+ 20++ 20++ 8
/ / / / \
4 => 4- => 8+ => 4 20
\ /
8 4
案例2b:插入8
20+ 20++ 20++ 9
/ \ / \ / \ / \
4 26 => 4- 26 => 9++ 26 => 4 20-
/ \ / \ / / \ \
3 9 3 9+ 4 3 8 26
/ / \
8 3 8
案例3b:插入8
__20+__ _20++_ __20++_ ___9___
/ \ / \ / \ / \
4 26 4- 26 9+ 26 4 _20-
/ \ / \ / \ / \ / \ / \ / \ / \
3+ 9 21 30 => 3+ 9+ 21 30 => 4 11 21 30 => 3+ 7- 11 26
/ / \ / / \ / \ / \ / \
2 7 11 2 7- 11 3+ 7- 2 8 21 30
\ / \
8 2 8
当我在优化平衡因子的计算时(即,仅针对受影响的节点调整平衡因子而不是重新计算整个树),更复杂的情况对我来说是一个问题.
现在考虑这些树进行删除操作:
2 ___6___ ___5___
/ \ / \ / \
1 4 2 9 2 8
/ \ / \ / \ / \ / \
3 5 1 4 8 B 1 3 7 A
/ \ / / \ \ / / \
3 5 7 A C 4 6 9 B
\ \
D C
从每个树中删除节点(1).请注意,案例1有效地证明了案例2,但并未完全证明案例3.
情况1
2 2 4
/ \ \ / \
1 4 => 4 => 2 5
/ \ / \ \
3 5 3 5 3
案例2
___6___ ___6___ ___6___
/ \ / \ / \
2 9 2 9 4 9
/ \ / \ \ / \ / \ / \
1 4 8 B => 4 8 B => 2 5 8 B
/ \ / / \ / \ / / \ \ / / \
3 5 7 A C 3 5 7 A C 3 7 A C
\ \ \
D D D
案例3
___5___ ___5___ ___5___ ____8____
/ \ / \ / \ / \
2 8 2 8 3 8 _5_ A
/ \ / \ \ / \ / \ / \ / \ / \
1 3 7 A => 3 7 A => 2 4 7 A => 3 7 9 B
\ / / \ \ / / \ / / \ / \ / \
4 6 9 B 4 6 9 B 6 9 B 2 4 6 C
\ \ \
C C C
在书籍和互联网上有很多AVL旋转的例子,但我发现它似乎是任意的,似乎没有一个地方包含插入和删除的所有4个案例的简单例子.
这是我为4种旋转提出的最简单的测试案例.为了便于描述,我使用了ascii字符作为键,因此测试用例可以表示为字符串.例如,字符串"abc"将是插入"a",插入"b"然后插入"c".
完整的测试用例创建了一些非常复杂的树,所以我创建了两个测试套件.第一个导致旋转,但是有旋转节点的空子树,这使得很容易看到实际发生了什么.第二个套件具有非空子树,以完全测试旋转代码.
旋转似乎有两种不同的nomanclature - 我学习的是2L旋转,有些书称为rl旋转,2R旋转称为lr旋转.以下文字使用2R/2L.
这些是插入的简单测试用例
"abc",插入"c"将需要1L旋转
a b
\ / \
b == 1L ==> a c
\
c
"cba",插入"a"将需要1R旋转
c b
/ / \
b == 1R ==> a c
/
a
插入"b"时的"acb"将需要2L旋转
a b
\ / \
c == 2L ==> a c
/
b
插入"b"上的"cab"将需要2R旋转
c b
/ / \
a == 2R ==> a c
\
b
删除
"bcad",删除"a"将需要1L旋转
b c
x \ / \
a c == 1L ==> b d
\
d
"cbda",删除"d"将需要1R旋转
c b
/ x / \
b d == 1R ==> a c
/
a
删除"a"时"bdac"将需要2L旋转
b c
x \ / \
a d == 2L ==> b d
/
c
"cadb"删除"d"将需要2R轮换
c b
/ x / \
a d == 2R ==> a c
\
b
更复杂的测试用例具有子树,大多数只是单个节点.为简化此帖子,将插入和删除测试用例组合在一起.删除示例通过跳过删除字符的插入而成为插入示例.例如,使用上面的2R简单删除情况"cadb"通过跳过"d"的插入而成为插入案例"cab".这样做的一个结果是下面的双旋转情况需要在插入要删除的节点之后插入额外的节点以保持树平衡.这导致插入情况不是最小的.
删除"a"或跳过"a"的"cbedfag"和"g"的插入将需要在c处进行1L旋转
c e
/ \ / \
b e == 1R ==> c f
x / \ / \ \
a d f b d g
\
g
关于删除"g"或跳过"g"的"ecfbdga"和插入"a"将需要在e处旋转1R
- e - c
/ \ / \
c f == 1R ==> b e
/ \ x / / \
b d g a d f
/
a
"ecjadhkgilbf"删除"b"或跳过"b"并插入"f"将需要在j处旋转2L然后e.插入盒可以选择性地跳过插入"d".
- e - —- h —-
/ \ / \
c j - e- j
/ \ / \ == 2L ==> / \ / \
a d h k c g i k
x / \ \ / \ / \
b g i l a d f l
/
f
关于删除"j"或跳过"j"的"hckbeiladfjg"和"g"的插入将需要在c然后b处进行2R旋转.插入盒可以选择跳过插入"l"
- h - - e -
/ \ / \
c k c - h -
/ \ / \ == 2R ==> / \ / \
b e i l b d f k
/ / \ x / \ / \
a d f j a g i l
\
g
使用问题中的方法1和2来验证树根据需要重新平衡(即,验证树仍处于有序和平衡状态).如果您想要确定,请将可视化测试用例转换为包含最终树的深度和平衡值列表,以便在顺序遍历期间进行验证.
小智 4
AVL 树的一个关键属性是它的每个子树也是 AVL 树。这意味着涵盖基本场景应该可以让您广泛了解 AVL 树功能。
换句话说，在允许它们的最小树结构上进行的这些测试是最重要的：
如果您的实现通过了这些测试，它可能会在更大的树上通过它们。请注意，此处未测试性能和内存使用情况。