AVL型顺序统计树（OS树）：左子树维度为2时右子树最大维度是多少？

首先明确核心规则：

• 整个树是AVL树，要求任意节点的左右子树高度差绝对值不超过1；
• 此处的“维度”指子树的节点总数。

当左子树节点数为2时，左子树作为合法AVL树有两种结构：

• 平衡结构：根节点带一个子节点（单侧），此时左子树高度为1（以根节点高度为0计算）；
• 链式结构：根节点仅单侧有子节点（形成两级链式），此时左子树高度为2（同样以根节点高度为0计算）。

根据AVL平衡限制，右子树的高度最多比左子树高1：

• 若左子树是高度1的平衡结构，右子树允许的最大高度为2。高度为2的满二叉树（同高度下节点数最多的AVL结构）节点数为 2^(2+1)-1 = 7，也就是你构造的“根节点+2个子节点+4个叶子节点”的结构，完全符合AVL平衡要求（左右子树高度差为1）。
• 若左子树是高度2的链式结构，右子树允许的最大高度为3，对应满二叉树节点数为15，但这种左子树结构属于AVL树的边缘情况，从常规场景来看，你的结论更贴合普遍讨论的情况。

综上，当左子树节点数为2时，右子树的最大节点数为7，你的判断是正确的。

内容的提问来源于stack exchange，提问作者SF40