4

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

           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还有（？？？）

4

1 回答 1

2

嗯，我想通了。节点 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 i可以在 O(1) 中实现，以合理i使用位移；log2(x)可以使用 256 字节的查找表在 O(1) 中实现。所以整体算法是O(1)。

于 2012-07-16T18:54:36.093 回答