右单旋的具体情况

右单旋的具体情况1、h为02、h为13、h为24、h为3在“AVL树的模拟实现”一文中我们学习到旋转调整方法的时候使用的需要旋转调整的示例都是一些抽象的二叉搜索树如图的树a, b, c都是抽象的树。插入节点红色方框之前三个树的高度都是h。我们设下图的树为原树然后对h做一点讨论进而展示出具体的需要旋转调整的例子的个数。1、h为0h为0那就只剩下节点⑩和节点⑤了。我们不可能在一个nullptr之下再插入一个节点所以h为0就没有需要右单旋的情况。2、h为1h为1就是一个节点是一个树此时节点④是树a节点⑨是树b节点15是树c。要想构成一个需要右单旋的不平衡二叉搜索树我们就要让树a的高度增加所以我们可以在节点④的两边插入所以h为1有两种情况需要右单旋。3、h为2h为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^14C41​4第三层有两个节点C 4 2 6 C_4^26C42​6第三层有三个节点C 4 3 4 C_4^34C43​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^34C43​4种。所以节点的插入有8 4 * 4 24种。那么h为3最终有225 * 24 5400种情况需要原树进行右单旋。所以我们举出具体的例子来演示右单旋是有很多具体例子的。