algorithm - 有哪些算法可以增量构建没有顺序约束的平衡二叉树？

Question

我有兴趣获取元素列表并将它们变成平衡的二叉树，每个元素都位于树的叶子上。此外，我想使用一种算法构建树，该算法一次只能看到一个元素，而不是一次看到整个列表。最后，这棵树没有排序约束——也就是说，它不是搜索树，因此节点可以按任意顺序排列。

我的问题是：有很多用于增量构建二叉搜索树的算法，但是在没有任何排序约束的情况下构建平衡二叉树的算法有哪些？它们应该更有效率，因为它们不必担心保留节点之间的任何顺序关系。

Answer 1

您可以在线性时间内完成。对于每 2 个元素，您需要一个父级。对于其中的每两个，您需要另一个，依此类推。虽然不能做得更好。

首先，您为拥有的每个数据点创建 N 个节点 - 然后您只需开始向后工作 - 将每两个叶子与一个节点连接在一起，然后将这些父节点中的每两个连接在一起，等等，直到您到达 1 个节点。

或者你也可以往下走——在任何 N 级，你都会得到 2^N 个孩子。

nodes = [...data...]

root = data.first; <== returns first element without removing it from nodes
while data.size > 1
  a=data.pop_front
  b=data.pop_front

  root = new node(a,b) <== create new node with a and b as children
  data.push_back(root) 

当您离开 while 循环时，root 包含树的顶部。