我正在阅读关于Robert Segdewick在C++中的算法中的随机二叉搜索树。
随机数生成器仍然有可能在每个机会导致错误的决策，从而给我们留下不平衡的树，但是我们可以从数学上分析这个机会，并证明它是消失的小。
财产13.2：随机bst的施工成本大于α乘以平均值的一个因子的概率小于e–
例如，建立一个10万个节点的随机bst需要大约230万个比较，但是比较次数超过2300万的概率远小于0.01%。这样的性能保证足以满足处理这种大小的真实数据集的实际需求。当使用标准的bst执行这样的任务时，我们不能提供这样的保证：例如，如果数据中存在显著的顺序，我们就会遇到性能问题，这在随机数据中是不可能的，但在实际数据中肯定不会异常，原因有很多。
与属性13.2类似的结果也适用于quicksort的运行时间。但结果在这里更为重要，因为这也意味着在树中搜索的成本接近平均值。不管构建树的额外成本如何，我们都可以使用标准的bst实现来执行搜索操作，其成本仅取决于树的形状，而不需要额外的成本来进行平衡。这种特性在典型的应用程序中非常重要，因为在这些应用程序中，搜索操作的数量远远超过其他任何操作例如，前一段中描述的100000节点bst可能包含电话目录，并且可能用于数百万次搜索。我们几乎可以确定，每一次搜索都将在23次比较的平均成本的一个小常数因子内，而且，出于实际目的，我们不必担心大量搜索将花费接近100000次比较的可能性，而对于标准的bst，我们需要担心。
我对以上文字的问题是
作者所说的“我们几乎可以确定，每一次搜索将在23个比较的平均成本的一个小常数因子内，而且，出于实际目的”。这里是小常数因子。
谢谢
最佳答案
好吧，你已经提到了quicksort，它是这种算法的一个完美例子quicksort最糟糕的性能是O(N^2)。然而，它是目前应用最广泛的排序算法之一。
为什么使用这种算法？因为最坏的情况真的很少见。如此罕见以至于即使算法出现一两次也值得使用。它可能比保证的解决方案更容易实现，它可以更好地与现代硬件（缓存）等配合。
通常最好使用quicksort而不是heapsort，尽管heapsort在理论上更好（在最坏的情况下会消耗O(1)额外的内存和O(N log N)时间）。
所以，在我看来，这本书想说，随机的英国夏令时是值得使用的，即使事情可以南下。仅仅因为这种情况发生的概率非常非常低。在实时系统的关键部分使用这种结构不是一个好主意。然而，对于一般的应用，使用随机结构可能会有帮助因为和自平衡树一样好的概率是相当高的。因为不用编写自平衡代码可以节省很多时间。CPU时间很便宜，开发人员的时间很昂贵。
我个人在编写union-find时使用随机方法。对于保证的最坏情况复杂度，你应该加入一个较小的集合，以较大的一个，我这样做随机。它节省了几行代码和一些内存，我还没有注意到随机化版本和保证版本在实践中的区别。
关于algorithm - bst分析，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/23608258/