arrays - 在 O(1) 中确定基于数组的二叉树中的最低子节点(具有最大索引的后代)？

Question

一些二叉树结构(例如堆)可以通过设置从左到右、从上到下的索引来使用数组来实现

           0
      /        \
     1          2
   /   \      /   \
  3     4    5     6
 / \   / \  / \   / \
7   8 9 10 11 12 13 14
       ... etc.

可以在 O(1) 中轻松找到索引为 x 的节点的子节点和父节点:

child-left(x) = 2x+1
child-right(x) = 2x+2
parent(x) = (x-1)/2

但是有没有办法在 O(1) 中找到 x 的最低后代 (即索引最高的后代)？例如，在上面的树中，x=0 的最低后代为 14，而对于 x=1 则为 10。请注意，对于 x=1，如果树中只有 10 个元素，它应该返回 9。

我可以假设我的数组中的元素永远不会超过 2³²，因此 2ⁿ 可以使用位移在 O(1) 中实现。也可能 log_2 (???)

Answer 1

嗯，我想通了。节点x的深度为

depth(x) = log2(x+1)

类似地，节点x的第i个左子节点和第i个右子节点很容易找到:

ithLeftChild(x, i) = 2i(x+1) - 1
ithRightChild(x, i) = 2i(x+2) - 2

深度最左边 child 的索引 d是ithLeftChild(x, d - depth(x)) , 右 child 也是如此。

我们称最后一个元素的索引为n .所以，现在我们可以找到 n 的深度, 我们还可以找到 leftmostChild 的指标和 rightmostChild在那个深度(可能比最后一个元素大，这意味着它们实际上并不存在)。

现在我们只有三种情况:

• n < leftmostChild .然后我们的子树在该深度没有元素，所以最高索引必须是 parent(rightmostChild) .
• leftmostChild <= n <= rightmostChild .那么索引最高的必然是n .
• rightmostChild < n .那么rightmostChild必须是我们的最高指数。

---

2ⁱ 可以在 O(1) 中实现合理的 i使用移位； log2(x)可以在 O(1) 中实现 using a 256-byte lookup table .所以整个算法是O(1)。