问题标签 [clrs]

来自 CLRS 的问题，3ed。

12.3-5
假设不是每个节点 x 保持属性 xp 指向 x 的父节点，而是保持 x.succ 指向 x 的后继节点。使用这种表示法在二叉搜索树 T 上给出 SEARCH、INSERT 和 DELETE 的伪代码。这些过程应该在 O(h) 时间内运行，其中 h 是树 T 的高度。（提示：您可能希望实现一个返回节点父节点的子程序。）

我知道如何实现一个在 O(h) 时间内返回节点父节点的子程序。

要找到节点的父节点，我们应该首先找到以子树为根x的最大键。然后，我们从 向右下。当我们到达时，我们之前遇到的节点是的父节点。MxM.succ.leftxxx

查看代码。

时DELETE x，x前身的succ应该被修改为指向x.succ，不再x。那么问题来了——如何x在 O(h) 时间内找到 的前身？

当 的左子树不x为空时，它是 的左子树中最右边的节点x。但是，当 的左子树x为空时，前驱是x的祖先，要找到调用 的 O(h) 次PARENT。这需要 O(h*h) 时间吗？还是应该从根向下搜索？

请注意，操作INSERT, 还需要找到一个节点的前任。

有一个问题——如果所有的键共享相同的值怎么办？那么我们不能通过x比较找到 ' 的前任，因为与 keya相等的 keyx可能出现在x' 的左子树或右子树中。

我今天正在阅读 CLRS，以更好地了解合并排序的复杂性。我遇到了一行，上面写着“其中常数c表示解决大小为 1 的问题所需的时间，以及除法和组合步骤中每个数组元素的时间。” 我知道作者所说的大小为 1 的问题是什么意思，但是除法和组合步骤的每个数组元素的时间到底是什么，为什么它是“cn”？

下面给出文字的图像以供参考。

我正在自学 CLRS，我已经达到了这一点——我要回答的问题是：

我把它减少到

现在，在这一点上，所有解决方案手册似乎都很少使用哦

=o(lglgn⋅lglgn)

这一步让我有点困惑；我以为我理解的很少——哦，但显然不够好——有人可以在这个特定的背景下框架它吗？接下来的步骤也从

至

这仅仅是L'hopitals规则的应用吗？

我在这上面花了几个小时，但我是 C++ 面向对象编程的新手，所以可能某些函数参数没有按应有的方式传递，但我找不到它。对于此代码，我得到以下输出：1 2 7 10 3 2 4 15

在 CLRS 的第 260 页上，它说，

如果哈希表槽的数量至少与表中元素的数量成正比，我们有 n = O(m)，因此，a = n/m = O(m)/m = O(1) . 因此，搜索平均花费恒定的时间。

如何得出 n = O(m) 的结论？n（表中元素的总数）如何被 m（槽数）限制？不应该是 m = O(n) 吗？

我正在研究CLRS的红黑树。关于讨论红黑树属性的部分，我有两个问题。来自CLRS的段落如下：

红黑树是满足以下红黑性质的二叉树：

1. 每个节点不是红色就是黑色

2. 根是黑色的

3. 每片叶子（NIL）都是黑色的

4. 如果一个节点是红色的，那么它的两个子节点都是黑色的

5. 对于每个节点，从节点到后代叶子的所有简单路径都包含相同数量的黑色节点

首先，它说红黑树是二叉树。为什么他们不说红黑树是二叉搜索树。我认为红黑树的全部目的是保持搜索树的平衡以确保logN操作。其次，为什么红黑树中的叶子是NIL？

在常规二叉树中，我们习惯于这样：

在这种情况下，3、2 和 7 是叶子。为什么在 CLRS 中叶子被描绘成 Nil 的？

在算法介绍 P657，第 3 版中，它说：

关键路径是通过 dag 的最长路径，对应于执行任何作业序列的最长时间。因此，关键路径的权重提供了执行所有作业的总时间的下限。

我明白第一句话。但在第二句话中，它说

关键路径提供了一个下限

为什么它提供了执行所有工作的总时间的下限而不是上限？

我想我可能会误解关键路径？

我正在阅读CLRS的第 2 章和第 3 章，并且经常被卡住，尤其是在每章末尾提供的问题中，我想知道是否值得付出这么多的努力。我无法理解这样的在线解决方案：http: //clrs.skanev.com/02/problems/01.html

我听说这本书是大学 CS 课上最受欢迎的教科书之一，但是人们会跳过复杂的部分而只记住重要的东西吗，比如插入排序有这种增长顺序，合并排序有这种增长顺序，然后继续?

仅仅熟悉许多有用的算法就足以像拥有 CS 学位的人一般对计算机科学有同样多的了解吗？

我正在通过 CLRS 中的插入排序算法。我不确定哪个是正确的实现 -

来自 CLRS 的算法 -

实施1：

实施2：

谢谢

不知道我在 python 中实现合并排序时哪里出错了。

如果有人能指出是什么破坏了我当前的合并排序实现，我将不胜感激。