问题标签 [search-tree]

我正在寻找一种算法来解决一个问题，在该算法中我维护一个树结构，我需要在该结构上找到数据节点的最接近匹配。如果没有完全匹配，则回退到最接近的前缀。

例如，如果说我有以下结构，其中单词（单词中的数字）是分支，带方括号的数字是数据（叶节点）；我正在寻找一种算法，该算法将返回下表所示的一组结果。请注意，路径分隔符是">"

我真的很喜欢 C++（STL或boost基于）的库；但是为此目的仅指向一个漂亮的算法也同样好。

因此，对于我的班级，我被要求为下面的查询编写一个完整的搜索树。我得到了一个示例表，但老实说，我的眼睛盯着它看。有人可以一步一步地引导我完成这个过程，并尽可能地向我解释，你会非常感激。

这是我得到的：

和查询

对不起，如果这是一个愚蠢的问题，但我很困惑。Negamax 在开始时检查是否已达到结束状态或最大深度。然后，您插入一个评估函数，该函数返回该状态的负分或正分（一个对一方有利，对另一方不利，反之亦然）。我发现很难理解的是下面的否定。这是否意味着返回的分数乘以-1？这能达到什么目的？我很欣赏叶子状态的“泡沫”备份在最小/最大分数之间交替。

线：-NegaMax(c, depth+1, 1-color)

我已经完成了一项家庭作业，100 分中的大约 3 分用于以下问题。

“假设你在有向图上构建了一个 DFS 树。之后你注意到没有任何后边。这对图有什么说明？”

我已经对此进行了一些思考，我所能推断的是，这意味着存在隐含的依赖关系，因此只有一个特定的路径可以拓扑遍历图。不幸的是，我无法在网络上的任何地方找到有关此的任何信息，所以我想我会在这里发布我的答案，看看是否有人可以权衡它的（不）正确性。如果您有任何其他想法或建议可以帮助我解决此问题，请告诉我。

非常感谢！

您将什么称为拆分因子为 的搜索树，存储在树中的数据点的维度在2^k哪里？k（数据点是向量x_1, ... x_k）

因为k=1我们会得到一个正常的二叉搜索树。因为k=2我们会在树的每个节点中分成 4 个象限，等等。

这种树的正确名称是k什么？

我正在创建一个类似报表生成器的应用程序，目的是制作一个对新手非常友好的前端。

应用程序的后端将由可以构建“报告模型”的开发人员管理，该报告模型将指定要包含哪些表、字段和连接以供最终用户使用。

我还希望添加不需要报表模型的功能。我的应用程序将扫描目标 SQL 数据库，并创建一个映射了所有连接和字段的虚拟模型。

在此之后，我将需要能够在表之间生成最“合乎逻辑”或最有效的路径，例如使用最少的连接。有点类似于旅行推销员的场景。

我决定通过使用树来映射来自将成为起始节点的特定表的所有连接以及它可能连接到的所有其他表来解决这个问题。这样我可以进行广度优先树遍历，理论上找到最“合乎逻辑”的加入路径。

我的问题是，并非所有数据库都将以特别机器逻辑友好的方式设置。这意味着由于特定的表或字段名称，人类可能会看到逻辑连接，而我的算法可能看不到。（下面是我的算法在c#中的一个简单迭代，它还没有记录表之间的路径）

我的问题是真的。我上面计划的方式似乎是对整个问题的一个不错的解决方案，还是有更好的方法来执行上述操作以获得更准确的表连接。

我正在尝试解决以下问题：

返回二叉搜索树的根 t 修改为仅包含值 <= k。（使用正常的 BST 类，我们有一个项目，左右）

我认为我做错了。也许有一些简单的递归方法可以做到这一点？

我需要知道如何为特定查询绘制搜索树以及如何在 prolog 中跟踪代码，这是一个示例：

a) 为以下查询绘制搜索树：

我在序言中有一个快速排序的代码：

例子是quicksort([3,2,4,1,5], Sorted)。我几乎画了这个，但我只找到了一个列表的踪迹Small=[2, 1]，然后我不能对一个Big数字列表做同样的事情。有没有人可以帮我画出这段代码的图表？我想了解程序的运行跟踪。我真的很感激！

我需要存储一组从 1 到 10^9的 n 数字，这样

1. 初始化需要 O(n) 时间 - 这是数学期望
2. 搜索需要 O(1) 时间 - 这是最坏的情况
3. 结构占用 O(n) 内存

您能否帮助我了解是否可以实施以及如何实施？

我认为可以使用哈希函数或搜索树。