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