データ構造、PHP

この投稿は翻訳であり、初心者向けです。 まあ、または大学の基礎コースからの講義を忘れた人のために。 ほとんどの場合、この資料は既に何らかの形でハブに出会っていますが、PHPとその機能に重点が置かれています。

データ構造または抽象データ型（ ADT ）は、それ自体に適用できる一連の操作として定義されるモデルであり、これらの操作が生成する結果によって制限されます。
私たちのほとんどは、日常生活の中でスタックとキューに直面していますが、スーパーマーケットのキューとデータ構造の間で一般的なことは何ですか？ この記事では、ツリーについても説明するこの記事を理解しようとします。




UPD ： s01e02

1. スタック
2. キュー
3. 樹木

スタック

スタックは通常、グループ化されたオブジェクトの特定のセットとして記述され、一般セットの各要素は次々に移動します-スタックされた本またはトレイのスタック。 コンピュータサイエンスでは、スタックは一般的な形成ルールを持つオブジェクトのコレクションです。スタックに配置された最後のオブジェクトが一般リストから最初に取得されます。 このルールは、「最後に入力、最初に入力」またはLIFOとも呼ばれます。 逆のルールがあります-最初に出てきて、最初に出てきました（ FIFO ）が、それについては後で詳しく説明します。
このルールLIFOは、たとえば、タバコやお菓子の自動販売機で使用されます。そこにロードされた最後のオブジェクトが最初に発行されます。

スタックの抽象的な定義はリストであり、すべての操作は一方の端に関連して定義されています。 スタックのトップ。
スタックを定義する基本操作：

• init-スタックを作成します。
• push-スタックの先頭（上部）に要素を追加し、残りを1ポジション下に移動します。
• pop-スタックから（上から）要素を抽出（および削除）します。
• top-（削除せずに）スタックの最初の要素の値を取得します。
• isEmpty-スタックの空を確認します。

可能な最大要素数でスタックを定義することもできますが、これらは些細なことです。 ただし、スタックが要素を受け入れられなくなると、スタックはいっぱいになり、スタックに関するメッセージを返します（スタックオーバーフロー）。 さて、反対の状況-空のスタックから要素を削除する（スタックアンダーフロー）。

スタックがLIFOとその基本操作として定義されていることを知っていると、特にこのための基本的なプッシュおよびポップ操作があるため、配列を介してスタックを書き込むことができます。 例は次のとおりです。

<?php class ReadingList { protected $stack; protected $limit; public function __construct($limit = 10) { //   $this->stack = array(); //        $this->limit = $limit; } public function push($item) { // ,      if (count($this->stack) < $this->limit) { //       array_unshift($this->stack, $item); } else { throw new RunTimeException(' !'); } } public function pop() { if ($this->isEmpty()) { //     throw new RunTimeException(' !'); } else { //     return array_shift($this->stack); } } public function top() { return current($this->stack); } public function isEmpty() { return empty($this->stack); } } 

この例では、array_push（）およびarray_pop（）の代わりにPHP関数array_unshift（）およびarray_shift（）を使用したため、最初のスタック要素が常に一番上にあります。そうでない場合、頂点はスタックのn番目の要素になります。 大きな違いはありません。 次に、スタックにいくつかの要素を追加します。

 <?php $myBooks = new ReadingList(); $myBooks->push('A Dream of Spring'); $myBooks->push('The Winds of Winter'); $myBooks->push('A Dance with Dragons'); $myBooks->push('A Feast for Crows'); $myBooks->push('A Storm of Swords'); $myBooks->push('A Clash of Kings'); $myBooks->push('A Game of Thrones'); 

それから、いくつかの要素を抽出しましょう：

 <?php echo $myBooks->pop(); //    'A Game of Thrones' echo $myBooks->pop(); //    'A Clash of Kings' echo $myBooks->pop(); //    'A Storm of Swords' 

私たちが今持っているのはスタックのトップですか？

 <?php echo $myBooks->top(); //  'A Feast for Crows' 

pop（）メソッドを再度呼び出すと、「カラスのeast宴」がスタックから削除されます。 プッシュしてすぐにポップしても、スタックは「最後にログインし、最初にログアウトした」ことに基づいて機能するため、スタックは変更されません。 スタックからアイテムをプルし続けると、遅かれ早かれ、スタックが空であるというメッセージとともに例外を受け取ります。

SPLStack

PHP（SPL拡張）は、バージョン5.3以降のSplStackを含むさまざまなデータ構造の実装を提供します。 ReadingListを継承するだけで作成できます。

 <?php class ReadingList extends SplStack { } 

SplStackには、反復を実装する能力（スタック内の要素の数）を持つ二重リンクリストが実装されているため、以前に定義したよりも少し多くのメソッドが提供されます。

本質的に異なる抽象構造であるリンクリストは、ノードのリストであり、各ノードには次のオブジェクトへのポインターがあります。 この構造は、単方向の列挙を使用してこのように表すことができます。



二重リンクリストでは、各ノードに2つのポインターがあります-リスト内の前のノードと次のノードへ。 この構造により、次の2つの方向に検索できます。



要素を調べて、リスト全体がどこで終わるかを知る必要があります。このために、内部で取り消し線を引いた要素を使用します。

キュー

それで、「最初に来た、最初に出た」またはFIFOに行きました。 本当のラインナップに立った人は誰でも、最初の場所を取った人が最初に去ることを知っています。 例外は、あなたがただ署名、尋ねるなどのオブジェクトです。

キューの基本操作は次のとおりです。

• init-キューを作成します。
• enqueue-要素をキューの最後（末尾）に追加します。
• デキュー-キューの先頭（要素）から要素を削除します。
• isEmpty-空のキューをチェックします。

PSプロローグに精通している人のために-この場合、尾は頭を除いて、リストのすべての要素を含んでいません。

PHPはSplQueueクラス（二重リンクリスト）も提供します。この場合のみ、リストの先頭が最後の要素になります。 ReadingListをキューとして定義します。

 <?php class ReadingList extends SplQueue { } $myBooks = new ReadingList(); //       $myBooks->enqueue('A Game of Thrones'); $myBooks->enqueue('A Clash of Kings'); $myBooks->enqueue('A Storm of Swords'); 

SplQueueはSplDoublyLinkedListを継承し、アクセスインターフェイスを配列として実装するため、配列を介してキューおよびスタックにアクセスできます。

 <?php $myBooks[] = 'A Feast of Crows'; $myBooks[] = 'A Dance with Dragons'; 

キューからいくつかの要素を削除します。

 <?php echo $myBooks->dequeue() . "\n"; //    'A Game of Thrones' echo $myBooks->dequeue() . "\n"; //    'A Clash of Kings' 

enqueue（）はpush（）のエイリアスですが、 dequeue（）はpop（）のエイリアスではありません ！ pop（）はキューのコンテキストで異なる動作をします。pop（）を使用すると、キューの末尾から要素が削除されるため（A Dance with Dragons）、キューの主なものはFIFOルールであるためです。

bottom（）メソッドを使用して、リストの先頭にある要素を（削除せずに）確認できます。

 <?php echo $myBooks->bottom() . "\n"; //  'A Storm of Swords' 

木々

通常、ADTコントロールは、構造への要素の挿入、構造からの要素値の削除と取得の3つの操作になります。 スタックとキューの場合、これらの操作は位置依存（xIFO）です。 しかし、値で情報を取得する必要がある場合はどうでしょうか？

このようなプレートがあると想像してください（要素の順序は関係ありません）：



明らかに、この場合、スタックまたはキューは役に立たないでしょう。なぜなら、必要な場合はすべての値をバイパスする必要があるからです。 必要なアイテムがリストにあるとします。 次に、検索のために、平均でn / 2個の要素（nはリスト全体の長さ）を検索する必要があります。 より多くのリスト-バイパスにかかる時間が長くなります。 この検索の問題を解決するには、構造による検索が簡素化されるように、何らかの方法でデータを配置する必要があります。 そして、ここに木が現れます。

この構造の抽象的な例は、次の操作を持つテーブルです。

• create-空のテーブルを作成します。
• 挿入-テーブルに要素を追加します。
• delete-テーブルからアイテムを削除します。
• 検索-テーブル内の要素を検索します。

はい、これは、ツリーとデータベースが密接に関連しているため、データベースのよく知られているCRUD （読み取り、更新、削除の作成）に似ています。

テーブルを表す1つの方法は線形です。 行ごとに説明します。 このようなレコードは、ソート、シーケンシャル（つまり、制限された長さまたは異なる長さ、区切り文字付きのレコード）、または関連（データへのポインターを使用）できます。 これは、初期のデータベースとファイルシステム（FATなど）の場合でした。 ただし、シーケンシャル記録にはマイナスがあります。データの挿入と削除には不向きですが、リンクされた記録では新しいデータにスペースを動的に割り当てることができます。 また、固定長のシーケンシャル録画は、リンク録画よりも効率的ではありません。 したがって、バイナリ検索ツリーの場合は、関連レコードを選択することをお勧めします。

ツリーはまさに非線形検索の実装であり、シーケンシャルと接続の2つのタイプのより効果的な機能を提供し、すべてのテーブル操作をサポートします。 そのため、最新のデータベースの多くは正確にツリーを使用しています（MyISAMはインデックスにツリーを使用しています）。



この図からわかるように、ツリーはノード間に親→子の関係がある階層構造です。 子孫のないノードは終了ノード（リーフ）、親のない子孫はツリーのルート、ノード間の接続はエッジです。 2つの子孫を持つノードは最も単純なツリーであり、これに基づいて、そのようなノードの再帰リストとしてツリーを表すことができます。 構造内のツリーは二重にリンクされたリストに似ていることに注意してください。

したがって、ツリーは次のように説明できます。

 <?php class BinaryNode { public $value; //   public $left; //    BinaryNode public $right; //    BinaryNode public function __construct($item) { $this->value = $item; //   -  $this->left = null; $this->right = null; } } class BinaryTree { protected $root; //   public function __construct() { $this->root = null; } public function isEmpty() { return $this->root === null; } } 

新しい値を挿入

新しい値を挿入することは、すでにはるかに興味深いトピックです。 ツリーの回転とバランスに基づいて、この問題にはいくつかの解決策があり、さまざまなタスクに対して、ツリーの挿入、削除、およびトラバースの操作でパフォーマンスインジケーターが異なる赤黒、AVLまたはBツリーなど、さまざまなツリー実装を使用できます。

簡単にするために、最も単純な実装のいくつかのルールを示します。現在の値よりも小さいものはすべて左に、より多くは右に移動します。
繰り返しは除外されます：

1. ツリーが空の場合、ツリーのルートとして[new_node]を挿入します（明らかに！）
2. さようなら（ツリーは空ではありません）：
   
   • 2a。 （[現在のノード]が空の場合）-ここに貼り付けて停止します。
   • 2b。 If（[new_node]> [current node]）-[new_node]を右側に挿入して、ステップ2を繰り返します
   • 2c。 If（[new_node] <[current node]）-左側に[new_node]を挿入して、ステップ2を繰り返します
   • 2d。 それ以外の場合、値はすでにツリーにあります
   
   

 <?php class BinaryTree { ... public function insert($item) { $node = new BinaryNode($item); if ($this->isEmpty()) { //  1 $this->root = $node; } else { //  1 $this->insertNode($node, $this->root); } } protected function insertNode($node, &$subtree) { if ($subtree === null) { //  2 $subtree = $node; } else { if ($node->value > $subtree->value) { //  2b $this->insertNode($node, $subtree->right); } else if ($node->value < $subtree->value) { //  2c $this->insertNode($node, $subtree->left); } else { //  ,  2d } } } } 

ノードの削除はまったく別の話であり、影響を受けません。 たぶん他の時間。

木の散歩

ルートから開始し、ツリーを1つずつ検索して空のノードを見つける方法を思い出してください。 4つの主要なツリートラバーサル戦略があります。

• 事前注文（直接注文）-現在のノードを処理してから、左右に移動します。
• 順序（対称）-最初に左側を通過し、現在のノードを処理して右側をバイパスします。
• post-order-左右を逆にしてから、現在の値を処理します。
• level-order（wide）-現在の値を処理してから、子孫を処理して次のレベルに移動します。

最初の3つの戦略は、ツリーのルート（ウェル、またはノードとして指定されたノード）から始まり、可能な限り深くツリーを通過して戻る前のディープウォークと呼ばれます。 これらの戦略はそれぞれ異なる目的に使用されます。 たとえば、新しいノードを挿入するとき（私たちの場合）またはサブツリーをコピーするとき、逆の場合-逆に、ツリーからノードを削除するとき、直接順序が使用されます。

対称パッセージがどのように機能するかを理解するには、例を少し修正する必要があります。

 <?php class BinaryNode { ... //      public function dump() { if ($this->left !== null) { $this->left->dump(); } var_dump($this->value); if ($this->right !== null) { $this->right->dump(); } } } class BinaryTree { ... public function traverse() { //        $this->root->dump(); } } 

おわりに

結論を読んでくれた皆さん、もう少しテキストと写真に感謝します:)

SplStack 、 SplQueue、および二重リンクリストの実装が完全にカバーされていないことに注意してください。 要素の数をカウントしたり、反復子として構造体を使用したりするなど、多くのメソッドがPHPドキュメントに隠されています。

kpuzucの この記事にも注意を払う価値があります。
これらの構造の可視化、 Tangroからの投稿で見つけることができるリンク

ここからコピーされたこれらの構造の実装のパフォーマンスのベンチマーク

キューに関しては、SPLを優先する選択はかなり明白です。 スタックの実装は実際には配列よりも優れているわけではなく、1秒あたりの操作数によって二重にリンクされたリストが配列に失われます。 正直に言うと、私はテストを掘り下げなかったので、それが何に関連しているのか知りたいのですが、「隣接する」インターフェースから拡張しすぎているという事実があります。

PSいつものように、PMのテキストの誤りとオリジナルの翻訳は受け入れられます。