右单旋的具体情况

在“AVL树的模拟实现”一文中，我们学习到旋转调整方法的时候，使用的需要旋转调整的示例，都是一些抽象的二叉搜索树：

如图的树a, b, c都是抽象的树。插入节点（红色方框）之前，三个树的高度都是h。

我们设下图的树为原树，然后对h做一点讨论，进而展示出具体的需要旋转调整的例子的个数。

1、h为0

h为0，那就只剩下节点⑩和节点⑤了。我们不可能在一个nullptr之下再插入一个节点，所以h为0，就没有需要右单旋的情况。

2、h为1

h为1，就是一个节点是一个树：

此时，节点④是树a，节点⑨是树b，节点15是树c。

要想构成一个需要右单旋的不平衡二叉搜索树，我们就要让树a的高度增加，所以我们可以在节点④的两边插入：

所以h为1，有两种情况需要右单旋。

3、h为2

h为2的树有三种：

对于原树，⑤节点的左边必须入树1这个满二叉树。如果入了树2或树3，那么就会有两种情况：

• 新插入节点，不会使得原树的平衡被破坏
• 新插入节点，⑤节点的左子树自己就需要旋转

而⑤节点的右边，和⑩节点的右边，三种h为2的树都可以选。

⑤节点的右边，和⑩节点的右边三种树都可以选，那么就有：3 * 3 = 9种情况。

而对于⑤左边的满二叉树，插入一个节点，可以插在4个地方：

那么一共有：4 * 9 = 36种情况。

4、h为3

我们必须明确，原树的节点⑤的左边，必须插入：

• 满二叉树
• 前两层符合满二叉树，第三层有3个节点

否则插入节点后，就会出现后无需旋转，或子树自身旋转的情况。

而原树节点⑤的右边，节点⑩的右边，插入的h为3二叉树，其前两层也必须是满的，否则也会出现插入后无需旋转，或子树自身旋转的情况。

h为3的二叉树：

满二叉树：1种情况

树-C-n-4：

• 第三层有一个节点：C 4 1 = 4 C_4^1=4C41​=4
• 第三层有两个节点：C 4 2 = 6 C_4^2=6C42​=6
• 第三层有三个节点：C 4 3 = 4 C_4^3=4C43​=4

那么树-C-n-4：共有14种情况

那么对于原树，树c（节点⑩的右边）和树b（节点⑤的右边）就各有15种情况，组合起来有：15 * 15 = 225种情况。

对于树a，如果树a是满二叉树，那么就有8个插入位置，可以构成原树需要右单旋的情况：

如果树a是由满二叉树缺了一个节点得来的，那么插入节点，必须插入到树a第三层的相邻两个节点的其中之一的下面：

插入到下面，有4种情况；h为3的满二叉树缺一个节点的情况，也为C 4 3 = 4 C_4^3=4C43​=4种。

所以节点的插入，有8 + 4 * 4 = 24种。

那么h为3，最终有：225 * 24 = 5400种情况，需要原树进行右单旋。

所以我们举出具体的例子来演示右单旋，是有很多具体例子的。