algorithm - 如何根据深度优先索引计算完美二叉树中节点的级别？

Question

我有一个完美的二叉树，即树中的每个节点要么是叶节点，要么有两个子节点，并且所有叶节点都在同一层。每个节点都有一个深度优先的索引。

(例如，在具有 3 层的树中，根节点的索引为 0，第一个 child 的索引为 1，第一个 child 的第一个 child 的索引为 2，第一个 child 的第二个 child 的索引为 3，第二个 child 的索引为 4，第二个 child 的第一个 child 有5，第二个 child 的第二个 child 有索引6。

      0
    /   \
  1      4
 / \    / \
2   3  5   6

)

我知道树的大小(节点数/最大级别)，但只知道特定节点的索引，我需要计算它的级别(即它到根节点的距离)。我如何最有效地做到这一点？

Answer 1

这是另一个可以更容易解决这个问题的建议:

如果按广度优先顺序用索引标记节点，则无需任何遍历即可在 O(1) 时间内计算级别。因此，如果您要执行多个查询，则可以执行 O(N) BFT 并在 O(1) 时间内回答每个查询。

水平的公式是:

level = floor(log(index + 1))

log以2为底

在这棵树上试试:

       0
     /    \
    /      \
   1        2
  / \      / \
 /   \    /   \
3     4  5     6

干杯。