4

一部の二分木構造（ヒープなど）は、インデックスを左から右、上から下に設定することにより、配列を使用して実装できます。

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

インデックスのノードの子と親は、xO（1）で簡単に見つけることができます。

child-left（x）= 2x + 1
child-right（x）= 2x + 2
親（x）=（x-1）/ 2

しかし、O（1）でxの最も低い子孫 （つまり、インデックスが最も高い子孫）を見つける方法はありますか？たとえば、上のツリーでは、の最下位の子孫はx=014になりますが、の場合は。x=1になります10。x=1の場合、ツリーに要素が10個しかない場合は、代わりに戻る必要があることに注意してください9。

配列に232個を超える要素が存在することはないと想定できるため、ビットシフトを使用して2 nをO（1）に実装できます。おそらくlog_2同様に（???）

4

1 に答える 1

2

さて、私はそれを理解しました。ノードxの深さは

深さ（x）= log2（x + 1）

同様に、ノードのi番目の左の子とi番目の右の子はx簡単に見つけることができます。

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

現在、3つのケースがあります。

  • n < leftmostChild。その場合、サブツリーにはその深さの要素がないため、最高のインデックスはである必要がありますparent(rightmostChild)。
  • leftmostChild <= n <= rightmostChild。その場合、最高のインデックスは必然的にnです。
  • rightmostChild < n。次にrightmostChild、私たちの最高のインデックスでなければなりません。

2 iiは、ビットシフトを合理的に使用するためにO（1）に実装できます。256バイトのルックアップテーブルを使用してlog2(x)O（1）に実装できます。したがって、全体的なアルゴリズムはO（1）です。

于 2012-07-16T18:54:36.093 に答える