从头开始形成$ n $元素红黑树的紧张的上限

Question

我学会了在一个统计树（增强红黑树，其中每个节点 $ x $ 包含一个额外的字段，表示节点的数量源于 $ x $ ）的子树查找 $ i $ th订单统计信息 $ o（lg（n））$ 时间在最坏的情况下。现在，如果有一个表示动态元素集的数组的情况下查找 $ i $ th订单统计可以在 $中实现o（n）$ 时间在最坏的情况下。[其中 $ n $ 是元素的数量]。

现在我觉得发现一个紧张的上限，用于形成 $ n $ 元素红黑树，以便我可以评论哪个替代方案更好：“维护阵列中的集合元素，并在 $ o（n）$ 时间“或”维护红黑树中的元素“（形成为 $ o（f（n））$ 时间说），然后在 $ o（lg（n））$ 时间“。

---

因此，非常粗略的分析如下，将元素插入 $ n $ 元素红黑树take $ o（lg（n））$ 时间，并且有 $ n $ 元素要插入，因此它需要 $ O（nlg（n））$ 时间。现在这个分析非常松散，因为红黑树只有很少的元素，高度相当少，所以在树中插入的时间是时候。

我试图尝试详细分析如下（但是失败了）：

允许在尝试插入 $ j= i + 1 $ th元素树的高度最多 $ 2 .lg（i + 1）+1 $ 。对于适当的 $ c $ ，总运行时间，

$$ t（n）\ leq \ sum_ {j= 1} ^ {n} c。（2.lg（i + 1）+1）$$

$$= c。\ sum_ {i= 0} ^ {n-1}（2.lg（i + 1）+1）$$ < / p>

$$= c。左[\ sum_ {i= 0} ^ {n-1} 2.lg（i + 1）+ \ sum_ {i= 0} ^ {n-1} 1 \右] $$

$$= 2c \ sum_ {i= 0} ^ {n-1} lg（i + 1）+ cn \ tag1 $$

现在

$$ \ sum_ {i= 0} ^ {n-1} lg（i + 1）= lg（1）+ lg（2）+ lg（3）+ ... + lg（n）= lg（1.2.3 .... n）\ tag2 $$

现在 $$ \ prod_ {k= 1} ^ {n} k \ leq n ^ n，\ text {它是一个非常松散的上限} \ tag 3 $$

使用 $（3）$ 在 $（2）$ 中，并将结果替换为 $（1）$ 我们有 $ t（n）= o（nlg（n））$ 哪个是与粗略分析相同...

我可以比 $（3）$ ？

更好

---

所谓的所有节点都是红黑树中的内部节点。

Answer 1

在 $ n $ 元素上构建一个红黑树，您需要花时间 $ \ oomga（n \ log n）$ ，如果只允许比较元素的键。 要查看此通知，任何BST的按次数递增键的次数访问节点。

如果您能够在时间中构建红黑树 $ t（n）= o（n \ log n）$ 那么您也是能够排序 $ n $ 元素 $ o（t（n）+ n）= o（n \ log n ）$ ，与基于比较的算法进行排序的下限相矛盾。

另一方面，如果元素已经排序，那么您可以在时间中构建一个红黑树 $ o（n）$ ：刚递归构建一个平衡的BST，如果最后一个级别是不完整的颜色，其节点为红色，以及每个其他节点黑色的颜色。 这需要线性时间，因为递归方程可以描述递归算法的时间复杂度 $ t（n）= 2t（n / 2）+ o（1）$ 。