流程树问题的最优解

Question

假设的流程链的流程树以树结构表示。每个进程产生与它的进程号相等的进程数，即进程号 3 有 3 个子进程。进程按级别顺序命名，root 为 1，其子/子进程从 2 命名，依此类推。给定进程的父进程的进程号是多少？

     1
      \
       2
      / \
     3   4
     |   |
 +-+-+   +-+--+-+
 | | |   | |  | | 
 5 6 7   8 9 10 11

因此，对于 6，父进程将为 3。

我在 O(n) 中编写了一个函数，它只是将树构建到 n 并从树中找到父节点，但我相信有更好的方法来解决这个问题。

Answer 1

• 好的，这是可以用一些数学公式解决的。

• 如果您仔细观察，对于任何给定节点，它的最高子值是parent_node * (parent_node + 1) / 2 + 1。

• 所以，假设您想找到 process 的父级9。

• 我们将不得不求解 的方程parent_node * (parent_node + 1) / 2 = 9。这里，parent_node是未知值。

• 因此，我们可以将等式改造成parent_node ² + parent_node - 18 = 0。现在，我们可以借助二次公式找到根。

• 我们发现正根是3.772，只取整数值，它是3。

• 现在，有两种情况：
  • 如果当前节点值（此处9）大于parent_node * (parent_node + 1) / 2 + 1，则答案为公式的正根 + 1，因此3 + 1 = 4。
  • 如果当前节点值（此处9）不大于parent_node * (parent_node + 1) / 2 + 1，则答案是正整数根值本身。