自己調整データ構造とは何ですか？

Question

"自己調整"データ構造の意味は？他のデータ構造との違いは？それらはどこで使用されていますか？

編集：挿入と削除以外の操作を実行すると、データ構造を調整するのはなぜですか？

Answer 1

自己調整データ構造は、操作がコミットされたときに自身を再配置できる構造です。時には彼らは自分自身を幅広くまたは最小限に並べ替えることがあります。

たとえば、ノードが挿入または削除されるたびに、AVL treesは、ツリー全体が均等になるようにバランスをとるため、挿入と削除のコストで高速な検索が保証されます。

非自己調整構造の例は、ツリーが何が起こってもノードが最初に挿入された場所に留まる、素朴なバイナリツリーです。

補足：他の構造は、挿入や削除ではなく、読み取りに基づいて調整されます。これらの構造は、進歩してアクセスに関する大量の統計を集めることができます。また、本質的に発見的になることもあります。これらの構造の目的は、過去に読んだことに基づいて読みをより速くすることです。そのような構造の一般的な例はcacheであり、最近アクセスされたデータはまだアクセスされていないデータよりも速くアクセス可能である。

Answer 2

私はこれらの種類のデータ構造に関する優れた講義ノートを見つけました。これは、MITのEric DemaineのAdvanced Data Structureクラスのものです。 http://courses.csail.mit.edu/6.851/spring07/scribe/lec01_2.pdf

Answer 3

この文脈では、「自己調整」の意味があります。あなたは、入力データのセットを与えられたときに、最小要素のような出力値を提供するデータ構造（例えば、最小ヒープ）を持つかもしれません。入力データに小さな変更を加え、ヒープを更新して新しい最小要素を配信することが一般的です。理想的には、ヒープの合計サイズではなく、変更のサイズに比例して、これを時間内に行いたいと思っています。

自己調整データ構造は、このタイプの「入力を変更し、段階的に出力を再計算する」動作をサポートします。 this recent paper from PLDI '10を参照してください。

これは、効率的な依存性追跡とインクリメンタルな計算の目標を共有する機能的なリアクティブプログラミングに関連しています。