将树拆分成相等部分

我正在寻找一种算法，通过从中删除一条边来拆分具有N个节点（其中每个节点的最大度数为3）的树，以便作为结果出现的两棵树尽可能接近N/2。我如何找到“最集中”的边缘？将树拆分成相等部分

该树作为来自算法前一阶段的输入，并作为图形输入 - 因此它不平衡，也不清楚哪个节点是根。

我的想法是找到树中最长的路径，然后选择最长路径中间的边。它工作吗？

理想情况下，我正在寻找一种解决方案，可以确保两棵树都不超过2N/3个节点。

感谢您的回答。

来源

2011-11-24 anonymous

如果你没有关于树的布局平衡的数据，你可以从一棵退化的树开始（比如左臂100个，右臂50个），然后以50/100分割结束同一条船。 –

是的，但是选取长度为150的最长路径，并将中间边缘（路径上的第75或第76）分成相等的部分。问题是这样一个最优边缘是否会一直存在（我不这么认为）。 – anonymous

退化树基本上是一个链表。例如具有两个孩子的唯一节点是根节点。所以你会有两条从根节点通过树的路径。左边有100个线性节点，右边是50个，右边是50个。分割最长的路径（100个节点分支）将100分成50/50，再加上右边分支的剩余部分，所以你已经将树从100/50至50/100。 –

我不相信你的初始算法适用于我在评论中提到的原因。不过，我认为你可以使用修改后的DFS在O（n）时间和空间中解决这个问题。

开始步行图来统计有多少个节点;称这个n。现在，选择一个任意节点并将其树根。我们现在将递归探索从根开始的树，并将为每个子树计算每个子树中有多少个节点。这可以用一个简单的递归来完成：

如果当前节点为null，则返回0。
否则：
- 对于每一个孩子，计算节点的数量在该子根的子树。
- 返回1 +在所有子节点的总数子树

在这一点上，我们知道每个边有什么分裂，我们将通过消除边缘得到的，因为如果低于边子树其中有k个节点，溢出将是（k，n - k）。因此，您可以通过遍历所有节点并寻找最平均地平衡（k，n-k）的节点来找到最佳切分。

计算节点需要O（n）个时间，并且运行递归访问每个节点和边最多O（1）次，因此也需要O（n）时间。寻找最佳切割需要额外的O（n）时间，对于O（n）的净运行时间。由于我们需要存储子树节点计数，所以我们也需要O（n）存储器。

希望这会有所帮助！

来源

2011-11-24 20:25:53 templatetypedef

你找不到任何算法来做到这一点。 –

@ SaeedAmiri-对不起，你能详细说明一下吗？ – templatetypedef

我没有看到最大程度的大小3，正确。 –

如果你看到我对Divide-And-Conquer Algorithm for Trees的回答，你可以看到我会找到一个节点把树分成2个几乎相等大小的树（自下而上的算法），现在你只需要选择这个节点的一个边来做你想做的事。

您目前的做法是行不通的假设你有一个完全二叉树，现在加入到叶子（命名为bad叶），您的最长路径将是一个其他的叶子到最后的一个范围内的一个长3*log n的路径的路径与此bad叶相连，并且您的中间边缘将位于此路径内（事实上，在您通过坏叶之后），并且如果您基于此边进行分区，则会有一部分O(log n)，另一部分大小为O(n)。

来源

2011-11-24 20:55:24

将树拆分成相等部分

回答

相关问题