T4 指定关键字集合 能够构成不同的AVL树的数量

和 T9_AVL_树最少结点数的递归性质 问题类似又有不同

例如 对关键字集合 $\{1,4,5,10,16,1721\}$.

• 由于左右子树的高度差不能超过 1，故只有5,10,16 可以作为根节点
  • 以10为根节点时，左子树关键字集合为 $\{1,4,5\}$, 右子树关键字集合为 $\{16,17,21\}$
    • 由于AVL树的性质，左子树只能以4为根节点, 右子树只能以17为根节点
    • 所以以10为根节点的AVL树只有1种
  • 以5为根节点时，左子树关键字集合为 $\{1,4\}$, 右子树关键字集合为 $\{10,16,17,21\}$
    • 左子树可能以4为根节点或1为根节点，高度为2
    • 右子树可能以16为根节点或17为根节点，高度为3
      • 以 16为根节点时，右子树可能为 17为根节点或21为根节点
    • 所以以5为根节点的AVL树有 $2\times 4=8$ 种
  • 以16为根节点时，与以5为根节点时类似，也有8种
• 所以总共有 $1+8+8=17$ 种不同的AVL树