参考请求 - 这个树算法叫什么？
Request for Reference - What is this tree algorithm called?
我在开发一些代码的过程中设计了一个算法。我想知道它是否有名称，或者它是否是更一般类别的实例。
算法概述如下：
简而言之，该算法采用可以合并的任意元素。
- 从抽象列表开始。列表的元素将是树中的叶子。为简单起见，假设列表中有 2^n 个元素。
- 将抽象列表中的元素配对，得到 2^(n-1) 对。配对很简单：第 (2n-1) 个元素与第 (2n) 个元素匹配。您从合并这些对的结果中获得一个新的摘要列表。现在您可以构造一个对应于每个合并元素的节点，该节点具有作为合并元素派生自的元素的子节点。
- 重复第 2 步，直到只剩下 1 个元素。
- 您现在有一个二叉树，它跟踪每个元素的 "ancestry"。
现在，我最好的猜测是这是某种折叠树（参见 https://en.wikipedia.org/wiki/Catamorphism#List_fold）。但它会跟踪折叠过程创建的数据结构，并允许并行进行折叠过程。
实际上，元素是对象列表，其中只有一些是兼容的。因此并非每个合并步骤都是成功的，因此有时需要遍历子节点并找到要输入的新对象列表。
这个算法可能以其他名称而广为人知，但它是合并排序算法的一件事，只是 "merge 2 sorted lists in linear time to produce a 3rd sorted list" 步骤离开 "open" 作为占位符。
我在开发一些代码的过程中设计了一个算法。我想知道它是否有名称，或者它是否是更一般类别的实例。
算法概述如下：
简而言之，该算法采用可以合并的任意元素。
- 从抽象列表开始。列表的元素将是树中的叶子。为简单起见，假设列表中有 2^n 个元素。
- 将抽象列表中的元素配对，得到 2^(n-1) 对。配对很简单：第 (2n-1) 个元素与第 (2n) 个元素匹配。您从合并这些对的结果中获得一个新的摘要列表。现在您可以构造一个对应于每个合并元素的节点，该节点具有作为合并元素派生自的元素的子节点。
- 重复第 2 步，直到只剩下 1 个元素。
- 您现在有一个二叉树，它跟踪每个元素的 "ancestry"。
现在，我最好的猜测是这是某种折叠树（参见 https://en.wikipedia.org/wiki/Catamorphism#List_fold）。但它会跟踪折叠过程创建的数据结构，并允许并行进行折叠过程。
实际上，元素是对象列表，其中只有一些是兼容的。因此并非每个合并步骤都是成功的，因此有时需要遍历子节点并找到要输入的新对象列表。
这个算法可能以其他名称而广为人知，但它是合并排序算法的一件事，只是 "merge 2 sorted lists in linear time to produce a 3rd sorted list" 步骤离开 "open" 作为占位符。