algorithm - 在树数据结构中查找所有叶节点的最高效方法

标签 algorithm performance optimization tree

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

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

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

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

谢谢!

最佳答案

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

你的树越静态,布局就越好。

全在一个布局中

  • All in one array 完全有序

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

    • 插入/删除可能很麻烦
    • 插入/删除O(N)
    • 插入可能会导致数组大小的调整,从而导致代价高昂的复制

两个数组布局

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

  • 专业人士

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

    • 如果所有叶子都是有序的,插入/删除会很麻烦
    • 如果叶子是无序的插入很容易,只需在末尾添加即可。
    • 如果不允许墓碑,则删除无序叶子也是一个问题,因为最后一个叶子必须移回并且内部节点需要修复。 (通过进一步的间接寻址,这也可以被修复,参见 slot-map)
    • 调整其中任何一个的大小可能会导致副本变大,但比一体机要小,因为它们可以独立完成。

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

  • 使用连续数组来引用每个节点的子节点
    • 快速遍历每个子列表
    • 每个子数组都可以独立调整大小
  • 反对
    • 虽然删除了子链表的大部分额外工作,但单个列表分散在所有其他数据中,使得查找需要额外的时间。
    • 插入可能会导致调整大小和复制数组。

关于algorithm - 在树数据结构中查找所有叶节点的最高效方法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/46623477/

相关文章:

algorithm - 如何选择列表中乱序的所有元素?

c++ - 为什么编译器对原始/标准数组而不是 vector 使用 XMM 寄存器?

performance - 如何对以下用例执行负载测试

添加和或子句时MySql Left Join速度慢

python - 如果我的目标函数是非线性(也是指数解释)函数,我应该使用什么求解器? python 壁虎

python - 列表索引越界(街机游戏)

python - 当用户输入相同的输入两次(预期)时,如何将输入组合到输出?

debugging - gcc LTO 似乎剥离调试符号

java - 如何在压缩后扩展霍夫曼节点

MySQL WHERE 子句中整数的第一个数字