找到树数据结构中所有叶节点的最高性能方法

Question

我有一个树数据结构，其中每个节点可以有任意数量的子节点，树可以是任何高度。获得树中所有叶节点的最佳方式是什么？在遍历树中的每条路径之前，是否可以做得更好，直到我击中叶节点？

实际上，树的最大深度通常为5左右，树中的每个节点都会有大约10个孩子。

我接受其他类型的数据结构或特殊树，这些树会使叶节点特别优化。

我使用的是JavaScript，但实际上只是在寻找一般建议，任何语言等

谢谢！

Answer 1

内存布局对于最优检索是必不可少的，所以子列表应该是连续的而不是链表，节点应该按照检索顺序依次放置。

您的树越静态，可以完成更好的布局。

全部在一个布局

• 所有在一个阵列中的全序

• 临

  • 存储器可以为最大的吞吐量被流传输（硬件预取）
  • 没有不需要的页面查找
  • 正常查找可以制造
  • 没有额外的内存来建立链表。
  • 内部节点使用偏移上寻找与自己孩子

• 精读

  • 插入/删除可能会很麻烦
  • 插入/删除O（N）
  • 插入可能导致调整阵列的尺寸导致成本高昂的复制

两个阵列布局为内部节点

• 一个阵列
• 一个阵列用于叶子

• 内部节点指向叶子

• 临

  • 叶节点可以是以最大吞吐量进行流式传输（如果大多数情况下只有intereste，则可能是最佳布局d在叶子中）。
  • 没有不必要的页查找
  • 间接查找可制成

• 精读

  • 如果所有的叶子是有序的插入/删除可能会很麻烦
  • 如果叶子是无序的插入是易于，最后加上。
  • 删除无序叶子也是一个问题，如果没有允许任何墓碑，因为最后一片叶子将不得不被移回并且内部节点需要修复。 （通过进一步的间接方向，这也可以固定参见插槽图）
  • 调整大小可能会导致大的副本，但小于All-in-one，因为它们可以独立完成。使用连续的阵列用于参照每个节点
  • 临
    • 通过每个子运行的子阵列的

  阵列（矢量的动态尺寸，C++矢量）

  • 列表很快
  • 每个子数组可以独立调整大小
• 精读
  • 同时去除大部分的个人名单分散所有其他数据进行查找采取额外的时间中链表孩子的额外工作。
  • 插入可能会导致调整大小和数组的副本。

Answer 2

查找树的叶子是O(n)，这对于树是最佳的，因为您必须查看O(n)地点以检索所有n事物，以及沿途的分支节点。常量开销是分支节点。

如果我们增加分支因子，例如让每个分支有32个孩子而不是2个，我们大大减少了开销节点的数量，这可能使得遍历速度更快。

如果我们跳过一个分支，我们不包括该分支中的值，所以我们必须查看所有分支。