10

我已经创建了一个 AVL 树实现,但是由于 AVL 树是一个相当复杂的结构,我需要对其进行测试。所以问题是 - 我该如何测试它?

到目前为止,我有以下测试:

  1. 基本健全性检查 - 检查每个节点高度是否等于最大值。子节点的高度+1,平衡在[-1, 1],左孩子的key <这个节点的key <右孩子的key,并且没有循环引用(就像一个节点的左孩子就是一个节点自己);

  2. 检查 AVL 树(以及整个二叉搜索树)上的中序遍历是否会按顺序返回底层集合中的值;

  3. 检查 AVL 树的高度是否严格小于 1.44*log2(N+2)-1(有 N 是元素数) - 由 AVL 树创建者证明;

  4. 视觉检查 - 效果不太好,我尝试画一棵树(第一行是根节点,下一行是他的直接子节点,第三行是根节点的直接子节点的子节点,依此类推),但这仅适用于小树,大树变得一团糟;

  5. 俄罗斯维基百科说,实验证明,两次插入需要一次重新平衡,五次移除也需要一次重新平衡,但真的如此吗?英文维基百科对此一无所知,对于我的 AVL 来说,两次插入或四次移除需要一次重新平衡,这并不完全相同。

也许这些测试已经足够了,但如果还有更多的测试,不难实现,为什么不做呢?

4

5 回答 5

40

本着所有这些答案的精神,我想我会提供几个具体的例子来证明基本案例是不够的。

插入 - 左/右重新平衡

考虑以下用于插入操作的 AVL 平衡二叉树:

  20+       20+           __20+__
 /         /  \          /       \
4         4    26       4         26
         / \           / \       /  \
        3   9         3+  9    21    30
                     /   / \
                    2   7   11

将 8 或 15(例如)插入这些树中的任何一个都会触发基本相同的左/右重新平衡,但最终结果对于每个树和插入值都有很大不同。也就是说,插入值的最终落地位置以及node(4)和node(20)的最终平衡因子完全取决于node(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
于 2012-12-12T16:16:21.427 回答
6

书籍和互联网上有很多关于 AVL 轮换的示例,但我发现似乎是任意的,似乎没有一个地方包含所有 4 种插入和删除案例的简单示例。

这些是我能为 4 种旋转提出的最简单的测试用例。为了便于描述,我使用 ascii 字符作为键,因此可以将测试用例表示为字符串。例如,字符串“abc”将插入“a”,插入“b”,然后插入“c”。

完整的测试用例创建了一些非常复杂的树,所以我创建了两个测试套件。第一个导致旋转,但对于正在旋转的节点有空的子树,因此很容易看到实际发生的情况。第二个套件具有非空子树来全面测试轮换代码。

旋转似乎有两种不同的命名法——我学到的是 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

删除“d”时的“cadb”将需要 2R 轮换

  c                  b
 / x                / \
a   d   == 2R ==>  a   c
 \
  b

更复杂的测试用例有子树,大多数只是一个节点。为了使这篇文章更短,插入和删除测试用例被结合起来。通过跳过删除字符的插入,删除示例变为插入示例。例如,使用“cadb”上面的2R简单删除案例通过跳过“d”的插入变成插入案例“cab”。这样做的一个结果是下面的双轮换情况需要在插入要删除的节点后插入一个额外的节点以保持树的平衡。这导致插入盒不是最小的。

删除“a”或跳过“a”时的“cbedfag”,插入“g”将需要在 c 处旋转 1L

      c                 e
     / \               / \
    b   e  == 1R ==>  c   f
   x   / \           / \   \
  a   d   f         b   d   g
           \
            g

“ecfbdga” 删除“g”或跳过“g”并插入“a”将需要在 e 处旋转 1R

      - e -                 c
     /     \               / \
    c       f  == 1R ==>  b   e
   / \       x           /   / \
  b   d       g         a   d   f
 /
a

“ecjadhkgilbf” 删除“b”或跳过“b”和插入“f”将需要在 j 然后 e 处旋转 2L。插入盒可以选择性地跳过插入“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

“hckbeiladfjg” 删除“j”或跳过“j”并插入“g”将需要在 c 然后 b 处进行 2R 旋转。insert case 可以选择性地跳过插入“l”</p>

      - 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 来验证按要求重新平衡的树(即,验证树仍然有序且平衡)。如果您想真正确定,请将可视化测试用例转换为包含最终树的深度和平衡值列表,以在中序遍历期间进行验证。

于 2014-06-05T15:43:22.017 回答
3

AVL 树的一个关键特性是它的每个子树也是 AVL 树。这意味着涵盖基本场景应该可以让您广泛了解 AVL 树的功能。

换句话说,在允许它们的最小树结构上完成的这些测试是最重要的:

  • 创建一棵新树。
  • 插入第一个值。
  • 插入更大的值。
  • 插入一个较小的值。
  • 插入一个导致 LL Rotation 的值。
  • 其他旋转也一样。
  • 删除也一样。
  • 查找值的所有变体。

如果您的实现通过了这些测试,它可能会在更大的树上通过它们。请注意,此处未测试性能和内存使用情况。

于 2010-10-18T11:31:33.100 回答
2

如果您真的想锤击您的实现,您应该使用许多不同的插入顺序和删除顺序模式进行一些黑盒测试。以下是一些想到的想法:

  • 随机顺序
  • 增加订单
  • 递减顺序
  • 交错两个流,一个是递增的,一个是递减的
    • 从相似的值开始,然后发散
    • 从末端开始,在中间相遇
    • 从两端开始并交叉到相反的两端
  • 具有向上、向下和中性偏差的随机游走
  • 在上述模式的组合中混合插入和删除。

根据上述模式,您不仅应该测试正确性,还应该测试性能,这可能需要建立较大的数据集,以便您可以有意义地衡量性能。使用 100 个元素,一切都很快,但是使用 10 5 个元素,O(N 2 ) 和 O( N log N )之间的差异将是巨大的。

您还应该测试错误的输入,例如两次添加或删除相同的值(假设您不允许重复)。

于 2010-10-17T23:15:41.623 回答
1

对于插入和删除,可能会发生特定数量的树操作(我记得每个大约五个)。

您需要在这些操作之一之前立即设置一棵树,以便添加另一个特定元素将导致这些操作中的一个已知操作发生。

然后您检查树 - 将其丢弃。这将是一个相当简单的树,不超过十个元素。

如果每个插入/删除操作都正常工作,您将验证树的重要核心行为。

(注意,其中一个(我认为是)插入操作不能以这种方式检查 - 它是暂时存在的中间状态)。

于 2010-10-18T09:39:18.290 回答