请求参考 - 这个树算法叫什么？

Question

我在开发一些代码的过程中设计了一个算法。我想知道它是否有名称，或者它是否是更普通类别的实例。

的算法概述如下：

简言之，该算法需要其可以被合并任意元素。

1. 从摘要列表开始。列表中的元素将是树中的叶子。为简单起见，假设列表中有2^n个元素。
2. 将抽象表中的元素配对，以便获得2 ^（n-1）对。配对很简单：第（2n-1）个元素与第（2n）个元素匹配。您可以从合并这些对的结果中获取新的摘要列表。现在，您可以构造与每个合并元素相对应的节点，该合并元素具有作为子节点的合并元素从其派生的元素。
3. 迭代步骤2，直到只剩下1个元素。
4. 您现在有一个二进制树，它跟踪每个元素的“祖先”。

现在，我最好的猜测是，这是某种树形折叠（请参阅https://en.wikipedia.org/wiki/Catamorphism#List_fold）。但它跟踪折叠过程所创建的数据结构，并允许折叠过程并行进行。

在实践中，元素是对象列表，只有其中一些是兼容的。因此，并非每个合并步骤都是成功的，因此有时需要遍历子节点并找到要输入的新对象列表。

Answer 1

这个算法很可能被其他名字所了解，但有一点是mergesort算法，只是将“合并2个线性时间的排序列表以产生第3个排序列表”作为剩下“打开”的步骤：一个占位符。