algorithm - 将平衡树映射到平面上的点

Question

我们得到一棵大小为 N 的平衡树，对于树中的每个节点，如果以该节点为根的子树的大小为 n 并且k 个子树，则其 k 个子树的大小为 Omega(n/k)。我们还在平面上给定了 N 个点，没有三个点共线。我们正在尝试找到这棵树中的节点与平面上的点之间的双射，以便在平面上绘制树不会导致任何边缘交叉。 k 是 Theta(1)，每个节点可以不同。

我试图找到解决此问题的递归解决方案，但无济于事，因为我不确定我们如何才能保证不交叉的要求。目标运行时间是 O(n log^2 n)，因此 T(n)=k*T(n/k) + O(n log n)< 形式的重复 会导致那样，所以我试图沿着这些思路思考。我要按 x 坐标对点进行排序，找到中位数，然后将其余点划分为 block 并递归求解。但我已经制定了让该解决方案失败的测试用例。有帮助吗？

Answer 1

你应该能够为你的根选择一个任意的点，然后把它周围的平面像饼一样切开，这样每个区域都包含其对应子树中的点数，以及从根到该区域中的任何点都完全位于该区域内。

然后，您应该能够对每个子区域递归地执行相同的操作。对于每棵子树，您都需要围绕子树根按角度顺序对该子区域中的剩余点进行重新排序，这应该会给您 T(n) = k*T(n/k) + O(n log n) 递归。

---

编辑:进一步思考，您可能无法任意选择一个点；你想在你的点的凸包上选择一个点，这样传入的线就不会与凸包相交——否则，你的子树可能会穿过传入线。这很容易做到，例如，在当前角度排序中选择子集中的第一个元素。