概率与渐近
Probability and Asymptotics
考虑我们有 n 个相同输入的情况，用于二叉搜索树。我们从x.left和x.right中随机select，同时插入节点。
clrs (12-1-(d)) 中有一个问题，要求我们推导出此设置的预期 运行 时间。直觉上，答案很简单 O(n lg n)。但我如何证明呢？
感谢任何建议。
月亮。
想象一下，完成此过程后您将拥有最后一棵树。使用数字 1、2、3、...、n 标记树中的每个节点，以便生成的树是二叉搜索树。现在，想象重播构建树的过程，知道每个元素在哪里结束。您最终追踪的过程最终等同于根据每个元素的数值对每个元素进行常规 BST 插入。所以这个问题最终等同于以下问题：如果将元素 1、2、3、...、n 的随机排列插入到二叉搜索树中，您将花费的预期时间是多少那么？
如果您已经知道这个问题的答案，那么您就完成了。如果不是，一个可爱的技巧是意识到这个过程最终等同于对元素 1、2、3、...、n 的数组进行 运行 随机快速排序。这是一种查看方式。树中的根元素对应于选择的第一个枢轴元素——每个插入的元素都会与其进行比较，并放入左子树或右子树中。根的左子节点对应于在递归调用小于初始主元的元素时选择的主元——每个小于初始主元的元素都会与左侧的主元进行比较。您可以使用归纳法将此论证形式化：通过归纳法证明，对于任何长度为 n 的数组，将元素 1、2、3、...、n 的随机排列插入二叉搜索树时进行的比较次数对应于使用结构遵循树中给定模式的枢轴对该数组执行快速排序。
一旦建立连接，就大功告成了，因为随机快速排序的预期成本是 Θ(n log n)。
考虑我们有 n 个相同输入的情况，用于二叉搜索树。我们从x.left和x.right中随机select，同时插入节点。
clrs (12-1-(d)) 中有一个问题，要求我们推导出此设置的预期 运行 时间。直觉上，答案很简单 O(n lg n)。但我如何证明呢？
感谢任何建议。
月亮。
想象一下，完成此过程后您将拥有最后一棵树。使用数字 1、2、3、...、n 标记树中的每个节点，以便生成的树是二叉搜索树。现在，想象重播构建树的过程，知道每个元素在哪里结束。您最终追踪的过程最终等同于根据每个元素的数值对每个元素进行常规 BST 插入。所以这个问题最终等同于以下问题：如果将元素 1、2、3、...、n 的随机排列插入到二叉搜索树中，您将花费的预期时间是多少那么？
如果您已经知道这个问题的答案，那么您就完成了。如果不是，一个可爱的技巧是意识到这个过程最终等同于对元素 1、2、3、...、n 的数组进行 运行 随机快速排序。这是一种查看方式。树中的根元素对应于选择的第一个枢轴元素——每个插入的元素都会与其进行比较，并放入左子树或右子树中。根的左子节点对应于在递归调用小于初始主元的元素时选择的主元——每个小于初始主元的元素都会与左侧的主元进行比较。您可以使用归纳法将此论证形式化：通过归纳法证明，对于任何长度为 n 的数组，将元素 1、2、3、...、n 的随机排列插入二叉搜索树时进行的比较次数对应于使用结构遵循树中给定模式的枢轴对该数组执行快速排序。
一旦建立连接，就大功告成了，因为随机快速排序的预期成本是 Θ(n log n)。