考虑对于二叉搜索树，我们有 n 个相同输入的情况。我们从x.left和x.right中随机选择，同时插入节点。
clrs (12-1-(d)) 中有一个问题，要求我们推导出此设置的预期运行时间。直观地说，答案就是 O(n lg n)。但是我怎么证明呢？
任何建议表示赞赏。
月亮。
问问题
22 次
1 回答
0
想象一下，在此过程完成后，您拥有最终的树。使用数字 1、2、3、...、n 标记树中的每个节点，以便生成的树是二叉搜索树。现在，想象一下重播构建树的过程，知道每个元素在哪里结束。您最终要追踪的过程最终等同于根据每个元素的数值对其进行常规 BST 插入。所以这个问题最终等同于以下问题：如果你将元素 1、2、3、...、n 的随机排列插入到二叉搜索树中，你将花费的预期时间是多少？所以？
如果你已经知道这个问题的答案，那么你就完成了。如果不是，一个可爱的技巧是意识到这个过程最终等同于对元素 1、2、3、...、n 的数组运行随机快速排序。这是看待这一点的一种方式。树中的根元素对应于选择的第一个枢轴元素 - 每个插入的元素都与它进行比较并放入左子树或右子树。根的左子节点对应于在小于初始轴的元素的递归调用中选择的轴 - 每个小于初始轴的元素都与左侧的轴进行比较。您可以使用归纳法形式化此论点：通过归纳法证明对于任何长度为 n 的数组，插入元素 1、2、3、...的随机排列时进行的比较次数。
一旦你有了这个连接，你就完成了，因为随机快速排序的预期成本是 Θ(n log n)。
于 2016-10-25T04:11:35.677 回答