clrs

1热度

1回答

我试图从CLRS的书，这是关于字符串算法，天真模式搜索假设解决练习32.1-2，在模式P中的所有字符是不同的。显示如何加速 NAIVE-STRING-MATCHER在n字符文本上在时间O（n）上运行。所以我试图优化我想出的天真蛮力解决方案，但我不认为我可以做得更好，以减少O（n）的整体运行时间。 <?php //naive search $a = array('a', 'b', 'u',

1热度

1回答

什么被认为是红黑树上的一片叶子？

我正在研究从CLRS红黑树。我有两个关于红黑树属性讨论部分的问题。从CLRS通道如下：红黑树是二叉树满足以下红黑属性：每个节点是红色或黑色根是黑色每个叶（NIL）是黑如果一个节点是红色的，那么这两个其子黑对于每个节点，从该节点的所有简单路径，以后代叶中含有相同数量的黑色节点首先的，它说为红色黑树是二叉树。为什么他们不说红黑树是二叉查找树。我认为红黑树的全部目的是为了在搜索树中保持

0热度

2回答

分段树的惰性传播

对于分段树的惰性传播算法，我还有一些不清楚的地方。根据下面的代码，在查询间隔完全重叠时，更新值只会添加到父节点，并且孩子被标记为延迟更新。但是，正如你在附图中看到的那样，如果更新完成了+4范围0,1，那么结果在两棵树中完全不同！（左图：没有惰性传播）。 void update_tree(int node, int a, int b, int i, int j, int value) { if(

0热度

1回答

这是这个循环的正确不变吗？

这对于在阵列中的线性搜索伪代码，如果在阵列A所需元素e被发现返回一个索引i，NIL否则（这是来自CLRS书，第3版，运动2.1-3）： LINEAR_SEARCH (A, e) for i = 1 to A.length if A[i] == e return i return NIL 我试图从中推断循环不变的，所以根据我的理解，我认为，一个是由事

3热度

1回答

在CLRS中实现DFS和BFS实现灰色的目的是什么？

在实施DFS和BFS时，CLRS作者为每个顶点区分3种颜色 - 灰色，黑色和白色。我明白，黑色和白色表示节点是否被访问过。为什么我们需要灰色？我的猜测是检测周期，但是我们是否也可以检测只有黑色（即没有灰色）的黑色周期？

0热度

1回答

C中的红黑树

我试图在C中实现红黑树。对于参考，我使用的是CLRS。但是，当我运行代码时，我得到“分段错误（核心转储）”错误消息。我无法弄清楚我的代码有什么问题，所以有谁能告诉我我的代码有什么问题？该问题似乎在功能rb_insert_fixup()，但我不知道它有什么问题。 #include <stdio.h> #include <stdlib.h> //constants #define RED

1热度

1回答

邻接列表indegree

我正在解决这个CLRS问题，它要求找出图的每个顶点的indegree G(V,E)。我发现解决方案为O(|E|)，因为我们只需扫描所有边来找出所有顶点的度数。但我在网上找到的大多数解决方案都说它是O(|V|+|E|)。怎么来的？顶点如何占用时间？

0热度

1回答

CLRS 18-2.4假设我们将密钥{1,2，...，n}插入到一个空的B树中，其最小度数为2，最终的B树有多少个节点？

假设我们将密钥{1,2，...，n}插入到一个空B树中，其最小度数为2，最终的B树有多少个节点？

0热度

1回答

m-way B-tree可以奇怪吗？

我读的书CLRS，我们有M路B树，其中m为偶数。但是有没有B树是m的奇数，如果有的话，我们该如何修改本书给出的代码。

0热度

1回答

解决通过替换

的方法的复发时在学习的算法和参照CLRS，我碰到 T(n) = T(n-a) + T(a) + cn ; a >= 1 and c > 0 it is Big-theta(n^2), can be easily proved by recursion tree method 我可以通过递归树的方法解决它的问题。在我的实验室与朋友们讨论时，一位朋友从不知情的地方宣布，这个问题永远无法通过替代