我已经创建了一个 AVL 树实现，但是由于 AVL 树是一个相当复杂的结构，我需要对其进行测试。所以问题是 - 我该如何测试它？
到目前为止，我有以下测试:
基本完整性检查 - 检查 对于每个节点高度等于最大值。 子节点的高度+1，平衡在[-1, 1]，左 child 的 key < 这个节点的 key < right child 的 key ，并且没有 循环引用(如左 child 一个节点本身就是一个节点)；
检查 AVL 树上的中序遍历 (以及整体上的二叉搜索树) 将按顺序从底层集合返回值；
检查 AVL 树的高度是否严格小于 1.44*log2(N+2)-1(N 是元素的数量)- 由 AVL 树创建者证明；
视觉检查 - 效果不佳，我尝试画一棵树(第一行是根节点，下一行是他的直接子节点，第三行是根节点的直接子节点的子节点，依此类推) ，但这只适用于小树，对于大树，它变得一团糟；
俄罗斯维基百科说，实验证明，两次插入需要一次重新平衡，五次删除也需要一次重新平衡，但事实真的如此吗？英文维基百科对此只字未提，对于我的 AVL，两次插入或四次删除需要一次重新平衡，这并不完全相同。
也许这些测试就足够了，但如果还有更多的测试，实现起来并不困难，为什么不做呢？
最佳答案
本着所有这些答案的精神，我想我会提供几个具体的例子来证明基本案例是不够的。
插入 - 左/右再平衡
考虑以下用于插入操作的 AVL 平衡二叉树:
20+ 20+ __20+__
/ / \ / \
4 4 26 4 26
/ \ / \ / \
3 9 3+ 9 21 30
/ / \
2 7 11
将 8 或 15(例如)插入任何这些树中将触发基本相同的左/右重新平衡，但最终结果对于每棵树和插入值都大不相同。也就是说，插入值的最终落地位置和节点(4)和节点(20)的最终平衡因子完全取决于节点(4)下的右 child 的相对值——如果有的话。单独对这些案例中的任何一个进行测试并不一定能证明任何其他案例的正确性。注意:对于这些情况，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。
案例一
2 2 4
/ \ \ / \
1 4 => 4 => 2 5
/ \ / \ \
3 5 3 5 3
案例二
___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
案例三
___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
关于algorithm - 如何检查我的 AVL 树实现是否正确？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/3955680/