三、判定树

  用来模拟排序过程的二叉树，每个结点代表了所有可能的排序集合，而边代表了记录之间的比较，也就是一个判断。判定树每个叶结点对应一种排列情况，因此一共有n！个叶结点。此判定树的最小深度为log(n！)＝Ω(nlogn)，也就是说基于比较的排序问题的下限也为Ω(nlogn)。