2

AVL tree各ノードは次のもので構成されています。

  • 鍵
  • 価値

はキーAVL treeで並べ替えられます。

したがって、2つのキーを取得し、それら2つのキー間の最大値を見つけたい場合。左側のサブツリーの最大値や右側のサブツリーの最大値など、各ノードに追加情報を追加しようとしましたが、間にいくつかのノードを「失う」ことなく正しいアルゴリズムを取得することはできません。

複雑さの時間： O（log n）最悪の場合。

4

1 に答える 1

1

この複合ツリーで他にどのような操作が必要ですか。また、それらにどのような複雑さの限界が必要ですか。

キーの範囲の最大値のルックアップ（j、k）操作に唯一の制限がある場合、これらすべてのn^2最大値を任意に事前計算するというばかげた解決策があります。時間; ツリーのノードkの配列に固定kのすべての値を格納します。次に、操作はルックアップに縮小されます。ただし、挿入または削除をサポートする場合、複雑さはO（n ^ 2）のようになります。

より現実的なオプションは、各サブツリーの最大値を格納することです。任意の2つのノード間に最大でO（log（n））サブツリーがあり、ルートから2つのキーjおよびkに向かう途中、またはツリー内でそれらのすぐ下にあるすべてのサブツリーに遭遇するため、O（ log（n））。この方法でもO（log（n））を挿入できますが、エントリを削除したサブツリーの最大数を復元するのは複雑なので、削除はO（n）になる可能性があると思います。

于 2011-05-17T19:35:22.280 に答える