1. 序章

データ構造は、効率的なアクセスと変更のためにデータの編成、管理、および保存を定義するコンピュータサイエンスの主要な分野の1つです。 ストレージ、アクセス、および使用タイプに基づいて利用可能な多数のデータ構造があります。

このチュートリアルでは、いくつかの高度なデータ構造を調べます。

2. 線形データ構造

その要素が線形シーケンスを形成する場合、データ構造を線形と呼びます。 いくつかのタイプの線形データ構造について説明しましょう。

2.1. 自己組織化リスト

自己組織化リストを使用すると、特定のアルゴリズムに基づいて要素を並べ替え、平均要素アクセス時間を向上させることができます。 再編成機能を除いて、リンクリストに似ています。

リンクリストでは、検索プロセスでは、アイテムが見つかるか、リストの最後に到達するまで、リストの各要素をアイテムと比較する必要があります。 したがって、最悪のシナリオでは、要素を検索する必要があります。ここで、はリストのサイズです。 自己組織化リストは、アクセスされた要素をリストの先頭に移動することにより、平均検索時間を改善しようとします。

再編成プロセスを決定するいくつかのアルゴリズムについて説明しましょう。 フロント方式への移行から始めることができます。

この手法では、要素にアクセスすると、その要素がリストの先頭に移動します。 この方法には、長所と短所の両方があります。 アクセスすると要素が移動するだけなので、簡単に実装できます。 一方、アクセス頻度の低い要素に優先順位を付けることができます。 たとえば、珍しい要素が一度でもアクセスされると、リストの先頭に移動され、将来再びアクセスされなくても、最大の優先順位が与えられます。 したがって、リストの最適な構造を壊す可能性があります。

次に、カウントメソッドがあります。 countメソッドでは、各メソッドは検索された回数を追跡します。 ノードは、カウント値に基づいて降順で並べ替えられます。

2.2. 循環バッファ

循環バッファまたはリングバッファは、がエンドツーエンドで接続されているかのように単一の固定サイズのバッファを使用するデータ構造です。 名前は、バッファの開始と終了が接続されており、円のように見えるためです。

非循環データバッファ（ Stack など）に対する循環バッファの有用な特性の1つは、消費時に要素をシャッフルする必要がないことです。  非循環バッファが使用された場合、1つが消費されたときにすべての要素をシフトする必要があります。

最初、循環バッファは空で始まり、定義された長さを持っています。 次の図では、バッファのサイズは5です。

値1が循環バッファの中央に書き込まれていると仮定しましょう。 循環バッファでは、正確な開始位置は重要ではありません。

その後、さらに2つの要素（2つと3つ）が循環バッファーに追加され、1つの後に配置されると想像してください。

2つの要素が削除されると、循環バッファ内の最も古い2つの値が削除されます。 循環バッファはFIFO（先入れ先出し）ロジックを使用します。 この例では、1つと2つが最初に循環バッファに入りました。 それらは最初に削除され、バッファ内に3つ残っています。

バッファに5つの要素がある場合、次のようになります。

循環バッファのもう1つの興味深い特性は、バッファがいっぱいになり、後続の書き込みが実行されると、最も古いデータの上書きを開始することです。 現在の例では、さらに2つの要素（AとB）が追加され、3つと4つが上書きされます。

循環バッファリングは、最大サイズが固定されているキューに最適です。 キューに最大サイズを採用する必要がある場合は、すべてのキュー操作が一定時間で実行されるため、循環バッファは完全に理想的な実装です。 ただし、循環バッファを拡張するにはメモリをシフトする必要があり、これはコストのかかる操作です。 このようなシナリオでは、リンクリストアプローチの方が適している可能性があります。

2.3. ギャップバッファ

ギャップバッファは、が同じ場所の近くにクラスター化された効率的な挿入および削除操作を実行できるようにするデータ構造です。 これは、テキストエディタで一般的なデータ構造であり、ほとんどのテキスト変更はカーソルの現在の場所またはその近くで発生します。 テキストは、新しいテキストを挿入するためにそれらの間にギャップを置いて、2つの連続したセグメントの大きなバッファに格納されます。

The quick brown fox [ ] over the lazy dog

カーソルを移動するには、ギャップの一方の側からもう一方の側にテキストをコピーする必要があります。 挿入操作では最初のセグメントの最後に新しいテキストが追加されますが、削除すると削除されます。

これを例を挙げて説明しましょう。 初期状態を以下に示します。

The quick [ ] over the dog

ユーザーが新しいテキストを挿入します。

The quick <em>brown fox</em> <em>jumps</em> [ ] over the dog

ユーザーは、theという単語の後にカーソルを移動します。

The quick brown fox jumps over the [] dog

ユーザーがlazy、という名前の新しい単語を追加すると、システムは新しいギャップを作成します。

The quick brown fox jumps over the lazy [] dog

ギャップバッファ内のテキストは、余分なスペースをほとんど必要としない2つの別個の文字列として表されます。 したがって、リンクリストなどのより高度なデータ構造と比較して、非常に迅速に検索および表示できます。 ただし、テキスト内のさまざまな場所とギャップを埋める操作（つまり、新しいギャップを作成する必要がある）での操作では、ほとんどのテキストをコピーする必要がある場合があります。これは、大きなファイルの場合は特に非効率的です。

ギャップバッファの実装では、テキストの再コピーが十分に行われることはめったにないため、より一般的な安価な操作でコストを償却できると想定しています。 これにより、ギャップバッファは、テキストエディタで使用するためのRopeデータ構造のより簡単な代替手段になります。

2.4. ハッシュ化された配列ツリー

ハッシュ配列ツリーは、データ要素を格納する個別のメモリフラグメントまたはリーフの配列を維持するデータ構造です。このデータ構造の主な利点は、要素を伝染性メモリに格納する動的配列とは異なります。領域では、自動サイズ変更のために必要な要素コピーの量が削減されます。

ハッシュ化された配列ツリーの最上位ディレクトリには、2つの数のリーフ配列の累乗が含まれており、最上位ディレクトリと同じサイズです。 サイズを2の累乗として使用する理由は、商と剰余の算術演算を使用する代わりに、ビット演算による物理アドレス指定を高速化するためです。

ハッシュ化された配列ツリーの構造は、その名前の基礎となるリンクリスト衝突チェーンを持つハッシュテーブルに似ています。 さらに、完全にハッシュ化された配列ツリーは、最大数の要素を保持できます。ここで、mは最上位ディレクトリのサイズです。  上の図では、最上位のディレクトリサイズは4です。 したがって、最大16個の要素をツリーに収容できます。

3. 非線形データ構造

非線形データ構造は、要素が線形または連続的に編成されていない線形データ構造の反対です。 ツリーまたはヒープは、非線形データ構造の例です。 このセクションでは、他のいくつかの非線形データ構造について説明します。

3.1. ロープ

ロープは、長い文字列を格納および操作するために使用される小さな文字列で構成されるツリーデータ構造です。 ロープは、コードがこの目的に効果的であることも知っています。 たとえば、テキスト編集プログラムは、ロープを使用してテキストを表すことができるため、挿入、削除、および更新の操作を効果的に管理できます。

ロープは二分木の一種で、各リードノードが文字列と長さを保持します。 ツリーのさらに上の各ノードは、左側のサブツリー内のすべての葉の長さの合計を保持します。 たとえば、重みが9のノードは、左側のサブツリーの長さが（Hello_）6と（my_）3の合計であるため、その値を取得します。

2つの子を持つノードは、文字列を2つの部分に分割します。 左側のサブツリーは文字列の最初の部分を格納し、右側のサブツリーは文字列の2番目の部分を格納し、ノードの重みは最初の部分の長さです。

3.2. スプレーツリー

スプレーツリーは、二分探索木であり、は、最近アクセスした要素をすばやく再度検索するための追加のプロパティです。 二分探索木と同様に、スプレー木は時間内に挿入、検索、削除を実行します。 非ランダム操作の多くのシーケンスでは、スプレーツリーは他の検索ツリーよりもパフォーマンスが優れています。

スプレーツリーの通常の操作はすべて、splayingと呼ばれる基本的な操作に基づいています。 要素のツリーを広げると、操作中の要素がツリーのルートに表示されるようにツリーが再配置されます。 これを実現する方法はいくつかあります。 たとえば、基本的な二分探索を実行してツリー内で動作中の要素を見つけ、ツリー回転手法を使用して要素をツリーの最上部に移動できます。 検索と木の回転を単一のフェーズで組み合わせることができる他のトップダウンアルゴリズムがあります。

上の図では、リーフノードにある要素20を検索しています。 回転の終わりに、要素20がツリーのルートに移動され、ツリーのバランスも調整されます。

3.3. バイナリヒープ

バイナリヒープは、バイナリツリーの形式をとるヒープデータ構造であり、優先キューの実装に一般的に使用されます。 バイナリヒープは、2つの追加の制約があるバイナリツリーです。

  • バイナリヒープは完全なバイナリツリーである必要があります。これにより、ツリーのすべてのレベルが、場合によっては最後のレベルを除いていっぱいになる必要があります。 さらに、最後のレベルが完了していない場合は、すべての要素を左から右に入力する必要があることも義務付けられています
  • 各ノードに格納されているキーは、ノードの子のキー以上または以下のいずれかです。

親キーが子キー以上であるヒープは、max-heapsと呼ばれます。 一方、親キーが子キー以下の場合、それは最小ヒープと呼ばれます。

4. 結論

この記事では、いくつかの高度なデータ構造について説明しました。

最初に、線形データ構造について説明し、自己組織化リスト、循環バッファー、ギャップバッファー、ハッシュ配列ツリーデータ構造などのいくつかの候補を調べました。

最後に、ツリー、ヒープ、グラフを含む非線形データ構造について学びました。 このカテゴリでは、ロープ、スプレーツリー、およびバイナリヒープのデータ構造について説明しました。