问题标签 [tree]

Hello fellow stackoverflowers!

I have a word list of 200.000 string entries, average string length is around 30 characters. This list of words are the key and to each key i have a domain object. I would like to find the domain objects in this collection by only knowing a part of the key. I.E. the search string "kov" would for example match the key "stackoverflow".

Currently I am using a Ternary Search Tree (TST), which usually will find the items within 100 milliseconds. This is however too slow for my requirements. The TST implementation could be improved with some minor optimizations and I could try to balance the tree. But i figured that these things would not give me the 5x - 10x speed improvement I am aiming at. I am assuming that the reason for being so slow is that i basically have to visit most nodes in the tree.

Any ideas on how to improve the speed of the algorithm? Are there any other algorithms that I should be looking at?

Thanks in advance, Oskar

我的数据库中有一个存储树结构的表。以下是相关字段：

我想找到所有的叶子节点（即任何id不是另一个记录的记录parentid）

我试过这个：

但这返回了一个空集。奇怪的是，删除“NOT”会返回所有非叶节点的集合。

谁能看到我哪里出错了？

更新：感谢大家的回答，他们都是正确的并且为我工作。我接受了丹尼尔的，因为它也解释了为什么我的查询不起作用（NULL 的事情）。

为什么 C++ STL 不提供任何“树”容器，而最好使用什么？

我想将对象的层次结构存储为树，而不是使用树作为性能增强...

这可能是一个简单的修复 - 但我试图将二叉搜索树上的所有节点（来自 Node 类的 Size 属性）相加。到目前为止，在我的 BST 类下面，我有以下内容，但它返回 0：

在我的 Node 类中，我有 Data ，它将 Size 和 Name 存储在它们的给定属性中。我只是想总结整个大小。有什么建议或想法吗？

想象一下，您每天都会收到一位作者的新书。这本书正在进行中。他没有告诉你他改变或增加了什么。

您的工作是识别更改和添加内容，并仅将它们传递给出版商（他们没有时间每天阅读整本书）

出于这个问题的目的，这本书由 1m 行的 ascii 文本组成，并且还在不断增长（实际上是一个 MySQL 备份文件）。

我目前的想法是对每行（1k 个字符）进行安全哈希（例如 SHA256）并将其存储在 HD 上。由于散列只有 32 字节，因此文件只有 32MB。

然后当我们明天得到下一个文件时，我们逐行检查它，为每一行创建一个新的散列，并将其与前一天的散列进行比较。

当该过程完成后，我们会覆盖为第二天准备的哈希文件。

比较使用字符串比较（ > < 操作数）的二进制搜索方法，这将返回平均四次迭代的结果。

我还没有编写 btree 索引解决方案，但你将如何解决这个问题？

我的 SQL 表如下所示：

并映射到我的 ActiveRecord 模型中的以下类：

我正在使用 ActiveRecord 使用以下代码检索树根：

这为我提供了正确的对象图，但 SQL Profiler 跟踪显示，子页面正在由树中每个非叶节点的单独查询加载。

如何让 ActiveRecord 预先加载全部内容("SELECT * FROM Page")，然后对内存中的对象进行排序以提供所需的父子关系？

这个问题是关于 Java JTree 或 Window .Net 树 (Winforms) 或 Adob​​e Flex 树。

在客户端-服务器应用程序中（对于 Flex，它实际上是 Web），我有一个带有分层数据的树（在 Windows 资源管理器类型的界面中）。现在，当用户从服务器请求更多数据时，我会懒惰地加载树。这很好，最多可以运行大约 750K 个节点（在 .Net Winforms 和 Adob​​e Flex 上进行了经验测试），但之后它变得迟缓。但是数据库增长很快（主要是因为用户可以粘贴大量节点），拥有 2000 万个节点的数据库并非不可能。

当分支折叠时我应该从树中释放数据以便垃圾收集器可以释放内存吗？这很好，但是如果用户没有效率并且不折叠分支怎么办？我应该做一个内存管理模块来关闭一段时间未触及的分支吗？

这一切似乎都需要做很多工作，以免内存不足。

编辑：我应该发布节点崩溃的数据吗？如果有，什么时候？弱对象缓存的想法很好，但我是否应该继续填充 UI 直到它崩溃（也许这不是一个坏主意）？

所以我有一个带有 xmllistcollection 的弹性树组件作为它的数据提供者。我希望能够通过拖放重新排列树中的树叶和树枝。我想将放置区域限制为被拖动项目的当前级别。像

有没有办法做到这一点几乎是开箱即用的？

我可以编写一个大方法，使用收集到的标记来确定哪些叶子应该放在哪些分支中，最后填充一个 TreeNode 对象，但是由于 gppg 已经使用提供的正则表达式处理了所有事情，我想知道是否有更简单的方法吗？即使没有，任何关于如何最好地解决创建 AST 问题的指针都将不胜感激。

抱歉，如果我说了什么愚蠢的话，我才刚刚开始玩编译器游戏。:)

我正在寻找一个 PHP 库，它可以从具有左右 id 的数据库（或值数组）创建树结构。对于获取值时的结果，我只是在寻找一个数组，这样我就可以创建任何类型的视图。对于添加和删除，如果库能做到这一切就好了。即使该库位于另一个库中，我也不介意，因为我可能会将其拉出并与我自己的库集成。

有人知道吗？

我正在使用 PHP 和 MySQL，所以如果它至少使用 PHP 会很有帮助。如果它是一个不同的数据库，我可能可以转换它，尽管如果它不使用太多特定于语言的功能，它可能与 PHP 相同。