algorithm - 排序列表以简化二叉树的构建

Question

我有一组项目应该用于平衡二叉树。每一项的形式为(data,parent)，data是有用的信息，parent是二叉树中父节点的索引。

树中的节点从左到右逐行编号，如下所示：

           1
       ___/ \___
      /         \
     2           3
   _/\_        _/\_
  4    5      6    7

这些元素存储在一个链表中。我应该如何订购此列表以便我更容易构建树？每个父节点将被恰好两个子节点引用（按索引）；如果我按父索引对它们进行排序，则排序必须稳定。

score 0 · Accepted Answer

我想我不明白你到底想达到什么目的。您必须编写在树中插入项目的函数。例如，红黑树的插入复杂度相同，O(log n)，无论输入数据如何排序。是否有您必须使用的特定实现或插入必须达到的特定速度目标？

PS：对我来说听起来像是家庭作业:)

score 0 · Accepted Answer

您可以根据字段以升序对列表进行任何稳定排序parent。

结果将是这样的列表：

[(d_1,nil), (d_2,1), (d_3,1) , (d_4,2), (d_5,2), ...(d_i,x), (d_i+1,x) ]
     ^ 
   the root has no parent...

请注意，在此列表中，由于我们使用了稳定排序 - 对于(d_i,x), (d_i+1,x)排序列表中的每两对，d_i左叶！

既然是家庭作业-我仍然希望您确保自己了解所有内容。所以我不想“喂答案”。如果您有任何具体问题，请发表评论 - 我将尝试编辑和解释相关部分并提供更多详细信息。

Bonus：这种组织的结果是实现二叉堆结构的非常常见的方式，它是一棵完整的二叉树，但是为了性能，我们通常将它存储为一个数组，这与这种方式生成的输出非常相似。

score 0 · Accepted Answer

听起来你想要一棵二叉树，它允许你使用数组从叶节点到它的祖先。

通常，在将列表放入二叉树之前对其进行排序会导致二叉树不平衡，除非您使用 treap 或其他 O(logn) 数据结构。

在数组中存储（完整）二叉树的常用方法是使节点 i 有两个子节点 2i 和 2i+1。

给定这种组织（不是排序而是组织），您可以通过使用整数运算将数组索引除以 2 从叶节点转到父节点，这将截断分数。

如果您的二叉树并不总是完整的，您可能会更好地忘记使用数组，而是使用带有指针/引用的更传统的树结构。

3 回答 3