书上写着一个BDT的叶节点数是n！怎么了！？

Question

书中的文字：“让我们将树的外部路径长度定义为从根到每个叶节点的路径长度之和，然后基于比较的排序算法的平均时间复杂度等于该算法对应的二叉树的外部路径长度除以叶节点数，即n!”。叶节点的数目是多少？

(与平均情况下界排序有关)

Answer 1

这项索赔似乎假定所有内容都是唯一的(没有重复的)。N个唯一元素的排列(排序)数是n!，因此在决策树中，每一叶表示唯一元素的特定排序，就有n个！叶，其中只有一个表示排序顺序。