问题标签 [ropes]

我正在为完全抽象的对象在 C++ 中实现 Rope 数据结构。我遇到的问题是我无法弄清楚关键“拆分”操作的实现。维基百科页面很有帮助，但含糊不清且理论性很强，并且附在文本中的图像无助于我对算法的理解。有没有好的实现，或者提供示例代码的论文？我已经尝试阅读原始论文，但它们也没有真正的帮助。

什么是ropesJava

如何在 Java 中将它们初始化为 Java 中的替代品Strings？

为什么要引入这个概念？

我正在尝试制作一个绳索数据结构。它是一种二叉树，即递归数据结构。

绳索的目的是分裂和连接应该很快，这意味着您避免复制整个绳索。
因此，例如，用户应该能够rope1 + rope2在〜对数时间内说出并期待结果。

但是，这会带来一个问题：
如果修改了一条绳索，它的父项也会间接修改。
因为我的目标是直接rope替换string，这是不可接受的。

我对此的解决方案是：每当对 a 进行任何更改时rope，我都会创建一个新节点，稍作更改，而旧节点保持不变。

从理论上讲，我认为这会很好。

但是，在实践中，它涉及（几乎？）字符串的每次修改的堆分配。
即使是一个字符的更改也会导致一个新的堆对象，这不仅本身很慢，而且还会显着降低内存局部性，对性能产生非常负面的影响。

我应该如何解决这个问题？

我正在阅读绳索数据结构。我对使用 C++ 和 Qt 构建文本编辑器很感兴趣。我的问题是：C++ 等编程语言中的内置字符串操作函数是否使用绳索数据结构？或者我是否需要编写自己的代码来实现绳索，以便更有效地执行连接和删除等字符串操作？

维基百科条目说：

每个节点的“权重”等于其字符串的长度加上其左子树中所有权重的总和。因此，具有两个孩子的节点将整个字符串分成两部分：左子树存储字符串的第一部分。右子树存储第二部分，其权重是两部分之和。

我有点困惑，它首先说节点权重是其字符串的长度加上其左子树中所有权重的总和。然后它说如果一个节点有两个孩子（因此有一个左子树和一个右子树），那么权重是两个部分的总和，而不仅仅是左子树。看图是有道理的（22 正下方的 9 是 9 并且不是更大，因为 7 的右子树/子树对权重没有贡献）但是措辞对我来说似乎是错误的，还是我误解了什么？

在编写一些 Python 代码时，我发现需要一种类似字符串的数据结构，它可以快速插入、访问和删除任意位置。想到的第一个数据结构是绳索。Python 是否已经在某处实现了绳索数据结构？我浏览了标准库和 PyPI，但我还没有看到。（有一个名为 Rope 的 Python 重构库以及一家名为 Python Rope 的公司销售钢丝绳，这无济于事。）

String例如，对于任何给定的

如何c: Char在位置 2 之后插入一个字符b？

更新

在随机位置进行多次有效插入和删除时要考虑哪个 Scala 集合？（假设 aString可以转换为该集合。）

抱歉，如果我问一个愚蠢的新手问题。我是 C++ 新手（熟悉 C 和目标 C）并且想使用标准模板库中的绳索。这是否包含在 Xcode 使用的库中？我已经#include <vector>成功地尝试过同样的地图ext/hash_map。然而，绳索似乎不可用。我只需要下载源代码并将其包含在我的项目中吗？

两周前，我完成了一个展开树的实现，它允许基本功能，如插入、删除、查找键和获取三者的一系列元素的总和。您可以在此处找到此实现作为此问题的参考或出于好奇。

作为一项额外的任务（它是可选的，它是过期的，我解决这个问题不是为了一个成绩，而是因为我相信它是一个有用的数据结构不容易“谷歌关于它”），我被要求实现一个 Rope 数据结构来操作字符串，因此如果字符串是“warlock”并且给定的键是 0 2 2，那么字符串将是“lowarck”（0 2 是子字符串“war”，“lock”是删除“war”后剩下的内容，然后插入它在第二个字符之后变成“lo”+“war”+“ck”）。这只是一个查询，但对于 300k 字符长的字符串，它最多可以查询 100k，所以一个简单的解决方案是行不通的。

我的第一个疑问是初始化树（对于那些已经阅读要点的人，我将使用 Node 而不是 Vertex，以便大多数人易于理解）。

这是 Node 类和 NodePair 类：

之后，我以这种方式创建树：

这会创建一个非常不平衡的树，其中字符串的第一个字符（作为 node.key）具有 node.size 1 并且是最左边的孩子；字符串的最后一个字符是 size=sb.length() 的根。

我不完全确定这是否正确初始化。我用键和大小做了一个中序遍历打印，我得到了整个字符串的大小顺序，这是我所期望的。

之后，我修改了 Update 方法：

为此：（基于 CLRS 第 14.1 章）

然后是find方法，来自原文：

为此：（基于 CLRS 第 14.1 章的 Order Statistics-SELECT）

但是，此时我已经遇到了问题，因为如您所见，原始 find 返回一个 NodePair，而此方法返回一个 Node。根据讲师对 NodePair 的解释是：

返回结果和新根的对。如果找到，result 是指向具有给定键的节点的指针。否则，result 是指向具有最小较大键的节点的指针（顺序中的下一个值）。如果键大于树中的所有键，则结果为空。

这使我的拆分方法变得复杂，因为它使用 Find 方法来查找要拆分的节点。除此之外，我在这个 find 方法中获得了 NullPointerException，从其他学生那里我了解到，为了避免其他错误，我们应该使用非递归版本，所以基本上我需要实现 OS-Select 的非递归版本，它返回一个NodePair 作为以前的 find 方法或修改我的 split 方法是：

如您所见，find 方法被分配给 NodePair findAndRoot。我相信除了将 OS-Select 转换为非递归之外，我的主要问题是要了解 NodePair 使用之前的 find 方法和 split 方法的方式。

最后，这是我接收树和键并操作它们的方法的实现：

正如您必须从我的代码中意识到的那样，我是一个只有 5 个月开始学习编程的初学者，我选择了 Java，所以从我收集到的信息中，我了解到这种类型的数据结构更多地处于中间状态 -专家级别（我已经很惊讶我能够实现以前的 splay tree。所以请在你的回答中考虑我的初学者级别。

PD：这是非递归 OS-Select 的伪代码版本，仍然有 NullPointerException..

给定一个rope，假设我们需要知道它的散列（通过一些散列函数传递所有叶子的连接）。

现在，当一个绳子叶发生变化时，重新计算整个绳子的哈希值的有效方法是什么？即像 O(log n) 而不是 O(n)。

一种方法是使用Merkle 树。但是，这会导致诸如...

• 空的非叶节点或具有零长度子串的叶节点会影响哈希，即使它们对有效的绳索内容没有影响；
• 将节点从子树的右侧移动到该子树右侧兄弟的左侧会影响最终哈希，但不会影响有效的绳索内容。

有没有更好的算法呢？散列函数不必是加密安全的，只要足以避免可能的冲突即可。