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

Question

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

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

Answer 1

你可以在线性时间内完成。对于每个2个元素，您需要一个父元素。对于其中的每一个，你都需要另一个，依此类推。但再好不过了。

首先，您为每个数据点创建N个节点 - 然后您开始以自己的方式备份 - 将每个两个叶子与一个节点连接在一起，然后将每个2个父节点连接在一起，依此类推，直到您到达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包含树的顶部。