树的分治算法

Question

我正在尝试为树木编写一个分而治之的算法.对于除法步骤,我需要一种算法,通过移除节点将给定的无向图G =(V,E)与n个节点和m个边分割成子树.所有子图应具有不包含超过n/2个节点的属性(树应尽可能分割).首先,我尝试以递归方式从树中删除所有叶子以找到最后剩余的节点,然后我尝试在G中找到最长的路径并删除它的中间节点.下面给出的图表显示两种方法都不起作用:

是否有一些工作算法可以满足我的需要(在上述情况下返回节点H).

Answer 1

我认为你可以用这样的算法来做到这一点：

\n\n

从根开始（如果树没有根，则选择任何节点）。
\n在每一步中，尝试下降到具有最大子树的子节点（\xe2\x80\x9c下面\xe2\x80\x9d的节点数是最大的）。
\n如果这样做会使节点数 \xe2\x80\x9cabove\xe2\x80\x9d 大于 n/2，则停止，否则继续该子节点。

\n\n

如果树是合理平衡的并且我们为每个节点预先计算了子树的大小，则该算法应该是 O(log n)。如果其中一个条件不适用，则复杂度为 O(n)。

\n