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

Question

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

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

Answer 1

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

首先，你为你拥有的每个数据点创建 N 个节点 - 然后你就开始按照自己的方式进行备份 - 将每两个叶子与一个节点连接在一起，然后将这些父节点中的每 2 个连接在一起，依此类推，直到达到 1节点。

或者您可以继续往下看——在任何 N 级，您都会得到 2^N 个 child 。

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 循环时，根包含树的顶部。