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

Question

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

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

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

左孩子(x) = 2x+1
儿童权利(x) = 2x+2
父级(x) = (x-1)/2

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

我可以假设我的数组中的元素永远不会超过 2 ^{32 个}，因此可以使用位移位在 O(1) 中实现2 ^{n 。}也有可能log_2（？？？）

Answer 1

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

深度(x) = log2(x+1)

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

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

最左边子节点在深度处的索引d是ithLeftChild(x, d - depth(x))，右边子节点的索引也是如此。

我们将最后一个元素的索引称为n。所以，现在我们可以找到 的深度，并且我们还可以找到该深度处的和 的n索引（它可能大于最后一个元素，这意味着它们实际上不存在）。leftmostChildrightmostChild

现在我们只有三种情况：

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

2 ⁱ可以在 O(1) 中实现，以便合理i使用位移位；可以使用 256 字节的查找表log2(x)在 O(1) 中实现。所以整体算法是O(1)。