当前位置: 首页 > 知识库问答 >
问题:

查找树数据结构中所有叶节点的最佳方法

曹鸿风
2023-03-14

我有一个树数据结构,其中每个节点可以有任意数量的子节点,树可以是任何高度的。获取树中所有叶节点的最佳方法是什么?有没有可能比遍历树中的每个路径更好,直到我到达叶节点?

在实践中,树的最大深度通常为 5 左右,树中的每个节点将有大约 10 个子节点。

我对其他类型的数据结构或特殊树持开放态度,这将使获取叶节点特别理想。

我正在使用javascript,但实际上只是在寻找一般建议,任何语言等。

谢啦!

共有2个答案

乜明朗
2023-03-14

查找树的叶子是O(n),这对于树来说是最佳的,因为您必须查看O(n)位置才能检索所有n事物,加上沿途的分支节点。不变的开销是分支节点。

如果我们增加分支因子,例如让每个分支有32个子节点而不是2个子节点,我们可以显著减少开销节点的数量,这可能会使遍历更快。

如果我们跳过一个分支,我们不会包含该分支中的值,因此我们必须查看所有分支。

邵星光
2023-03-14

内存布局对于优化检索至关重要,因此子列表应该是连续的,而不是链表,节点应该按照检索顺序一个接一个地放置。

树的静态程度越高,布局就越好。

全部在一个布局中

> < li>

全在一个阵列中完全有序

赞成

  • 可以对内存进行流式处理,以获得最大吞吐量(硬件预取)。
  • 没有不需要的页面查找
  • 可以进行正常查找。
  • 没有额外的内存来创建链接列表
  • 内部节点使用偏移量查找相对于自身的子节点

骗局

  • 插入/删除可能很麻烦。
  • 插入/删除O(N)
  • 插入可能会导致阵列的大小调整,从而导致成本高昂的复制

两个阵列布局

>

  • 内部节点的一个数组
  • 一个用于叶子的数组
  • 内部节点指向叶子

    • 叶节点可以以最大吞吐量进行流式处理(如果您最只对叶感兴趣,则可能是最佳布局)。
    • 没有不需要的页面查找
    • 可以进行间接查找

    骗局

    • 如果所有叶子都已订购,则插入/删除可能会很麻烦
    • 如果叶子是无序插入很容易,只需在最后添加即可。
    • 如果不允许使用逻辑删除,则删除无序的叶子也是一个问题,因为必须将最后一个叶子移回并且内部节点需要修复。(通过进一步的间接寻址,这也可以修复,见插槽映射)
    • 调整其中任何一个的大小都可能导致一个大的副本,尽管比多合一要少,因为它们可以独立完成。

    数组数组(动态大小,矢量的 C 向量)

      < li >使用连续数组引用每个节点的子节点 < li >专业 < ul > < li >快速浏览每个子列表 < li >每个子数组可以单独调整大小
    • 当删除链表子级的大量额外工作时,单个列表分散在所有其他数据中,使得查找需要额外的时间。
    • 插入可能会导致数组的大小调整和复制。

  •  类似资料:
    • 如何计算二叉树中最小级别所有叶节点的总和。如果不存在树,则应返回-1。 例子: 对于上述二叉树,返回100(40 60) (图片来源:Geeksforgeks)

    • 问题内容: 我正在使用nltk的Tree数据结构来处理parsetree字符串。 但是,数据结构似乎受到限制。是否可以通过其字符串值获取节点,然后导航至顶部或底部? 例如,假设您要获取字符串值为 ‘nice’ 的节点,然后查看其父级,子级等是什么?可以通过nltk的Tree实现该节点吗? 问题答案: 对于NLTK 3.0,您想使用ParentedTree子类。 http://www.nltk.or

    • 期望结果: 补充 结合边城用户的文章,最后得出的方法:

    • 问题内容: 表-用户 列-(userId,name,managerId) 行- 如果我提供用户ID,则应列出所有向他报告的人。如果我给userId = 2,则应返回3,4。 这个查询正确吗 有什么有效的方法来管理DB中的树结构吗?左右叶方式怎么样? 问题答案: 在我看来,邻接列表模型的问题在于,在SQL中很难处理它,尤其是当您不知道树结构的嵌套深度时。 您提到的“左右叶方式”可能是嵌套集合模型,它

    • 问题查找具有n个节点的完整二叉树中的叶节点数。 我为上述问题编写了一个递归程序,每当我到达一个没有子节点的节点时,遍历树并增加叶节点的数量。但由于这棵树是一棵完整的二叉树,我认为这会使问题变得更容易,但我不知道如何解决。它是否可以简化为紧凑形式(类似于公式)。

    • 假设我在一棵树中有一个节点,我如何获得所有的叶节点,它们的祖先是这个节点?我这样定义了TreeNode: