nimizes their average depth is a completely balanced tree。这个其实也很显然，如果不是平衡二叉树，说明最深的节点减去最浅的节点的高度差大于等于二，这时我们可以把最深的那两个节点移接到最浅的那支上，这样我们减小了average heights，但是没有影响到别的，这也就说明了只有对于任何不平衡的树，我们都可以使他的average height更小一些，所以也就说明了average depth of leaves must be at least nlgn。证毕。
顺便可以证明一下对于所有的randomized sorting algorithm，比较次数的lower bound也是nlgn。http://en.wikipedia.org/wiki/Randomized_algorithm
决定把这个放到下一篇文章中讲。O(∩_∩)O~
后面举几个例子来简单具体阐述一下上面说的两个方法。
例 有两个长度为n的已经排好的list，a1
假设我们用adversarial strategy证明，假设我们只比较了2n-2次，也就是我们只想神询问了2n-2次，这时我们知道有一个元素ai，他一定是没有和bj或者是bj+1比较的，假设我们的ai = 2i-1，也就是所有的奇数，bi = 2i，所有的偶数，那么这个时候，我们的算法已经给出了output，但是对于无所不能的神来说，它知道你没有比较ai和bj或者是没有比较ai和bj+1。
如果你没有比较ai和bi，你输出的是aibi，但是神可以交换ai和bi的值，这个时候ai = 2i，bi = 2i-1，交换的同时，依然保证a1
同理，如果你没有比较ai和bi+1，神依旧可以交换ai和bj+1的值，导致你的算法还是错的，所以你的2n-2的算法悲剧了，所以证明lower bound是2n-1。
例 给定一个长度为n的已经排好的list，a1
这个我们可以用decision tree的方法找到这个lower bound，考虑下面的decision tree：
从这个树上我们可以得出：
1）对于每一个非叶子节点，都有两个分支。
2）这个树一共有n个叶子节点（对应了我们n个可能的答案）
假设树的高度是h，我们知道最多可能出现的叶子节点数是 2^0+2^1+2^2+。。。+2^k-1，这是等于2^k-1的，当然，这个是大于等于n的，所以，就有 2^k-1 >=n, 可以得到 k >= lg(n+1)，这也就是，一路比较下去我们至少要用 lg(n+1)次比较。