paperbot · PL 论文追踪

全部论文 待读 收藏

P2 On constructing 2-3 trees

论 2-3 树的构造
JFP vol.282018匹配度 0/10 · 该论文讨论2-3树的线性时间构造方法,属于基础数据结构与函数式编程话题,与用户关注的PL→AI静态分析、AI→PL、浮点程序分析、贝叶斯程序分析及LLM交叉方向均无直接关联。引用 34 inbox
RALF HINZE
crossref: 2026-09-10

AI 速览

一句话:讨论自顶向下、自底向上和增量式三种线性时间构造 2-3 树的方法,其中增量式可与其他操作交错。

给定一个元素序列,论文研究如何在线性时间内构造一棵按对称序存储这些元素的 2-3 树。作者讨论并比较了三种构造策略:自顶向下、自底向上以及增量式构造。前两种方法以整体方式完成树的构建,而增量式方法更具灵活性,允许将构造工作与查询等其他操作交错进行。文章重点分析了这些方法在构造 2-3 树时的组织方式、操作顺序与线性时间特性,并指出增量式构造在需要边构造边访问的场景中的优势。摘要未提及具体实验评估,因此贡献主要体现在算法设计、比较与概念性讨论上。

问题
如何从给定的元素序列出发,在线性时间内构造一棵按对称序包含这些元素的 2-3 树。
方法
讨论并比较自顶向下、自底向上和增量式三种构造 2-3 树的方法,其中增量式方法允许将构造与其他操作交错。
评估
摘要未提及实证评估;论文应通过对三种构造方法的算法讨论与比较,说明其构造特性及线性时间目标。
原文摘要(Abstract)

We consider the task of constructing 2-3 trees. Given a sequence of elements we seek to build a 2-3 tree–in linear time–that contains the elements in symmetric order. We discuss three approaches: top-down, bottom-up, and incremental. The incremental approach is more flexible than the other two in that it allows us to interleave the construction work with other operations, for example, queries.

链接与引用

DOI 原文 · PDF(开放获取) ·

BibTeX
@article{paperbot340,
  title = {On constructing 2-3 trees},
  author = {RALF HINZE},
  journal = {Journal of Functional Programming},
  volume = {28},
  year = {2018},
  doi = {10.1017/s0956796818000187}
}