次のデータ構造に名前はありますか? 利用可能な論文と引用はありますか？
効率的なset 抽象データ型を実装する1 つの方法は、並べ替えられた配列のコレクションを作成することです。各配列は、2 のべき乗の一意のサイズを持ちます。
たとえば、13 個の要素 {1, 2, ..., 13} のセットは、次の並べ替えられた配列のコレクションで表すことができます: {[5], [2, 3, 9, 13], [1, 4, 6] 、7、8、10、11、12]}。
一般に、コレクション内の配列のサイズは、セットのサイズのバイナリ表現の 1 ビットに対応します。挿入は償却されたO (1) 時間で実行でき、検索はO ((log n ) 2 ) 時間 (線形検索よりも優れています) で実行できるため、データ構造は効率的です。また、O ( n ) 余分なスペースをポインターに使用する平衡二分木や B ツリーとは異なり、ポインターにO (log n ) スペースのオーバーヘッドのみを使用します。したがって、ほとんどすべてのスペースがペイロード データに使用されます。
ウィキペディアのデータ構造のリストを見てきましたが、一致するものは見つかりませんでした。アルゴリズムの紹介 ("CLRS") という本では、このデータ構造を "Amortized Analysis" セクションの宿題として説明しているのは事実ですが、これは例ではなく質問であるため、この本ではあまり説明されていません。