问题标签 [multiway-tree]

我目前正在自学各种数据结构，并且对各种类型的树有点沮丧。我可以理解将某些东西组织成二叉搜索树的目的，但看不到多路搜索树的任何实际应用。有人可以举一些他们使用多路搜索树实现的问题的例子吗？

你如何找到多路树的高度？如果我想找到二叉树的高度，我可以这样做：

但我不确定是否可以将类似的递归方法应用于多路树。

我需要为 c# 实现一个基于文件的多路 B-Tree 类。C++ 和 C 也有类似的功能，但我想在 C# 中使用它。它还需要作为源代码提供，因为我希望将其与一些替代的 .NET 实现（如 MonoTouch）一起使用。

如果有人知道非基于文件的Multiway b-Tree，那么这可以很容易地适应失败以基于文件。您使每个多路页面/节点数组成为文件中的记录/扇区。并在它们更改时保存它们。

任何人？

我们需要具有搜索和排名功能的 ADT。即除了STL map的接口外，还需要一个函数'int get_rank(key)'。

这种功能的标准实现需要在自平衡搜索树的每个节点中支持和更新一个额外的整数字段（例如，在黑红树中，用于 STL 映射/集）。但似乎，STL map/set 不这样做。

我们正在寻找一种基于标准容器（STL，Boost）的解决方案，具有最佳的时间复杂度：查找/添加/擦除元素需要 O(log n) （如在 STL 映射/集合中），通过 a 计算排名key 也需要 O(log n)。

元素的排名是指元素在地图/集合的所有元素的排序序列中的位置。

例子。set = {0, 4, 6, 7, 8} rank(0)=1, rank(4)=2, rank(6)=3, rank(7)=4, rank(8)=5。

在我们看来，在上述时间复杂度约束下，不能通过两个映射的组合来解决问题，一个按 key 排序，另一个按 rank 排序。

谢谢。

这应该不是一个困难的问题，但我只是希望有人在我继续之前将其反弹。我只需要根据这些预期的活动来决定使用什么数据结构：

1. 需要按排序顺序频繁迭代（从头部开始）。
2. 需要从/a 排序视图中删除/恢复任意元素。
3. 稍后我将经常使用数据并使用多个排序视图。
4. 稍后我将经常更改元素在其排序视图中的位置。

顺便说一句，这是在 Java 中。

我最好的猜测是，我要么滚动一些自定义链接哈希集（以排序顺序排列链接），要么可能只使用树集。但我还不能完全确定。建议？

编辑：我想由于任意删除/恢复，我可能应该坚持使用树集，对吧？

其实，不一定。嗯……

我有一个 C++ 类，它表示一个非常大的分层组织的数据树（〜 Gb，基本上与我在内存中可以摆脱的一样大）。它使用一个 STL 列表来存储每个节点的信息以及其他节点的迭代器。每个节点只有一个父节点，但有 0-10 个子节点。抽象，它看起来像：

我想实现 load() 和 save() 到磁盘，它应该相当快，但是明显的问题是：

1. 我事先不知道尺寸；

2. 数据包含易变的迭代器；

3. 我对 C++ 的无知是惊人的。

有人可以建议一个纯 C++ 解决方案吗？

有一个很棒的问题集叫做九十九Prolog Problems。问题 P70 是标题中提到的问题。这是这个问题的一个很好的 Prolog解决方案，只需要 5 行。但是，我对 Prolog 的理解是有限的。

这个解决方案在类似 C 的形式中看起来如何（没有可用的 itertools）？

应要求编辑。我希望我不侵犯版权。

问题：

BNF 中的语法：

使用差异列表的一个很好的解决方案：

更新：
我发现了更多我想要实现的示例：Managing Hierarchical Data in MySQL。我想这样做，但在 JavaScript 中，因为我正在构建一个应用程序，它接受分层结构的评论，更具体地说是 reddit.com。如果您的 chrome Web 浏览器上有 Pretty JSON 扩展，请转到 reddit 并单击线程评论，然后将 .json 添加到 url 以查看我正在解析的内容。
我得到 JSON 数据就好了，它只是解析注释并添加适当的 HTML 以显示它的嵌套。
解决方案的想法？

旧问题：
我正在编写一个程序，并且在编写代码之前我需要弄清楚逻辑。我正在接受树格式的数据，但每个父节点可能有几个子节点，我似乎可以找到的唯一树是具有权重的树或树，其中每个节点最多有两个子节点。所以我试图找出算法来评估树的每个节点，如下所示：

现在，当我尝试写出我的算法将如何工作时，我最终编写了嵌套的 for/while 循环，但我最终为树的每个高度级别编写了一个循环，该循环用于动态数据和高度未知且数量未知的树每个节点的孩子这不起作用。我知道在某个时候我学会了如何像这样遍历一棵树，但它现在完全逃离了我。任何人都知道这是如何在循环方面完成的？

我又开始研究数据结构了。我发现它的实际用途很少。其中之一是关于磁盘上的文件系统。有人能给我更多关于 m-way tree 实际用途的例子吗？

想象一下下面的树：

我正在寻找一种方法来查询例如 F 是否是 A 的后代（注意：F 不需要是 A 的直接后代），在这种特殊情况下是正确的。只有有限数量的潜在父节点需要针对更大的潜在后代节点池进行测试。

在测试一个节点是否是潜在父池中某个节点的后代时，需要针对所有潜在父节点进行测试。

这是一个想出的：

• 将多路树转换为特里树，即为上述树中的每个节点分配以下前缀：

  /li>

• 然后，为每个可能的前缀大小保留一个位数组并添加要测试的父节点，即如果将 C 添加到潜在的父节点池中，请执行以下操作：

  /li>

• 当测试一个节点是否是潜在父节点的后代时，取其 trie 前缀，在第一个“前缀数组”（见上文）中查找第一个字符，如果存在，则在第二个“前缀”中查找第二个前缀字符数组”等等，即测试 F 导致：

  所以是的，F，是 C 的后代。

这个测试似乎是最坏情况 O(n)，其中 n = 最大前缀长度 = 最大树深度，所以它的最坏情况完全等于直接上树并比较节点的明显方法。但是，如果测试的节点靠近树的底部并且潜在的父节点位于顶部的某个地方，则此方法的性能要好得多。结合这两种算法将减轻两种最坏的情况。但是，内存开销是一个问题。

还有另一种方法吗？任何指针都非常感谢！