Javascript

有向グラフのトポロジカルソートまたはトポロジカル順序付けは、頂点の線形順序付けであり、頂点uから頂点vまでのすべての有向エッジUVについて、順序付けでuがvの前に来るようにします。これは、有向グラフでのみ意味があります。 トポロジカルソートが非常に理にかなっている場所はたくさんあります。たとえば、レシピに従っているとしましょう。これには、次のステップに進むために必要ないくつかのステップがあります。ただし、これらの一部は並行して実行できます。同様に、大学でコースを選択する際には、より高度なコースの前提条件がいくつかあり、それ自体がさらなるコースの前提条件となる場合があります。例- 例 &nbs

グラフ理論では、最短経路問題は、構成するエッジの重みの合計が最小になるように、グラフ内の2つの頂点（またはノード）間のパスを見つける問題です。ここでは、エッジの追加と有向メソッドの追加を変更して、エッジにも重みを追加できるようにする必要があります。 これを追加する方法を見てみましょう- 例 /**    * Adds 2 edges with the same weight in either direction    *    *             weight

ダイクストラのアルゴリズムは、重み付きグラフ内のノード間の最短経路を見つけるためのアルゴリズムです。新しいaddEdgeメソッドとaddDirectedEdgeメソッドを使用して、グラフを作成するときにエッジに重みを追加します。このアルゴリズムがどのように機能するかを見てみましょう- 距離コレクションを作成し、ソースノードを除くすべての頂点の距離を無限大に設定します。 距離が0であるため、優先度0の最小優先度キューにソースノードをエンキューします。 優先キューが空になるまでループを開始し、ノードからの距離が最小になるようにノードをデキューします。 「現在のノードの距離+エッジの重み<次のノー

Djikstraのアルゴリズムは、1つのノードから他のすべてのノードまでの最短経路の距離/経路を見つけるために使用されます。すべてのノードから他のすべてのノードへの最短パスを見つける必要がある場合があります。ここで、すべてのペアの最短経路アルゴリズムが役立ちます。最も使用されているすべてのペアの最短経路アルゴリズムは、FloydWarshallアルゴリズムです。 フロイドウォーシャルアルゴリズムは次のように機能します- 距離のNxN行列をInfinityに初期化します。 次に、各エッジu、vについて、この行列を更新してこのエッジの重みを表示し、エッジv、vについては、重みを0に更新します。

ツリートラバーサルとは、ツリーデータ構造内の各ノードに1回だけアクセスするプロセスを指します。このようなトラバーサルは、ノードが訪問される順序によって分類されます。

このトラバーサルメソッドでは、最初に左側のサブツリーにアクセスし、次にルートにアクセスし、次に右側のサブツリーにアクセスします。すべてのノードがサブツリー自体を表す場合があることを常に覚えておく必要があります。 二分木が順番にトラバースされる場合 、出力は昇順でソートされたキー値を生成します。 A、から始めます 順番にトラバーサルした後、左側のサブツリーBに移動します。 B また、順番にトラバースされます。このプロセスは、すべてのノードにアクセスするまで続きます。このツリーの順序付けられたトラバーサルの出力は次のようになります- D → B → E &rarr

このトラバーサルメソッドでは、最初にルートノードにアクセスし、次に左側のサブツリーにアクセスし、最後に右側のサブツリーにアクセスします。 A、から始めます 事前注文トラバーサルに続いて、最初に Aにアクセスします それ自体を選択してから、左側のサブツリーBに移動します。 B プレオーダーもトラバースされます。このプロセスは、すべてのノードにアクセスするまで続きます。このツリーのプレオーダートラバーサルの出力は次のようになります- A → B → D → E → C → F → G これは、実装するアルゴリズムです： ノ

このトラバーサルメソッドでは、ルートノードが最後にアクセスされるため、この名前が付けられています。最初に左側のサブツリーをトラバースし、次に右側のサブツリーをトラバースし、最後にルートノードをトラバースします。 A、から始めます 注文後のトラバーサルに続いて、最初に左側のサブツリーBにアクセスします。 B 注文後にトラバースされます。このプロセスは、すべてのノードにアクセスするまで続きます。このツリーのポストオーダートラバーサルの出力は-になります。 D → E → B → F → G → C → A これは、実装するア

ノードを遠くから見ると、ツリーからノードを削除するのは非常に複雑です。ノードを削除する際に考慮すべき3つのケースがあります。これらは、次の関数のコメントで言及されています。以前と同じように、クラス内にメソッドを作成し、再帰的に呼び出すヘルパーを作成します。 クラスメソッド deleteNode(key) {    // If a node is successfully removed, a reference will be received.    return !(deleteNodeHelper(this.root, key) === false

これがBinarySearchTreeクラスの完全な実装です- 例 class BinarySearchTree {    constructor() {       // Initialize a root element to null.       this.root = null;    }    insertIter(data) {       let node = new this.Node(data);    

AVLツリー（発明者のAdelson-VelskyとLandisにちなんで名付けられました）は、自己平衡二分探索木です。自己平衡ツリーは、サブツリー内で回転を実行するツリーであり、左側と右側の両方でバランスをとることができます。 これらの木は、挿入によって片側の木が重くなる場合に特に役立ちます。バランスの取れたツリーは、O（n）側に傾く完全にアンバランスなツリーとは対照的に、ルックアップ時間をO（log（n））に近づけます。

AVLツリーは、左右のサブツリーの高さをチェックし、差が1以下であることを確認します。この差はバランス係数 たとえば、次のツリーでは、最初のツリーはバランスが取れており、次の2つのツリーはバランスが取れていません- 2番目のツリーでは、Cの左側のサブツリーの高さが2で、右側のサブツリーの高さが0であるため、差は2です。3番目のツリーでは、Aの右側のサブツリーの高さが2で、左側が欠落しているため、0になります。 、そして差は再び2です。 AVLツリーでは、差（バランス係数）を1のみにすることができます。 BalanceFactor = height(left-sutree) &min

バランスを取るために、AVLツリーは次の4種類のローテーションを実行できます- 左回転 右回転 左-右回転 左右回転 最初の2回転は1回転で、次の2回転は2回転です。不均衡な木を作るには、少なくとも高さ2の木が必要です。この単純な木で、それらを1つずつ理解しましょう。 左回転 ツリーが不均衡になった場合、ノードが右側のサブツリーの右側のサブツリーに挿入されると、左に1回回転します- この例では、ノード A ノードがAの右側のサブツリーの右側のサブツリーに挿入されると、バランスが崩れます。 Aを作成して左回転を行います Bの左側のサブツリー 。この回転はLL回転とも呼ばれま

AVLツリーにノードを挿入する方法を学ぶことができます。 AVLツリーへの挿入はBSTと同じです。ツリーを下に移動するたびに、挿入中にバランスツリーと呼ばれる追加の手順を1つ実行する必要があります。 これには、以前に見たバランス係数を計算する必要があります。また、構成に応じて、適切な回転メソッドを呼び出す必要があります。これらは、上記の説明の助けを借りて非常に直感的です。 再帰呼び出し用のクラスメソッドとヘルパー関数を再度作成します- 例 insert(data) {    let node = new this.Node(data);    //

結合関数を使用してコンテナを結合し、新しいコンテナを取得する必要がある場合があります。 2つのHashTableを受け取り、すべての値を使用して新しいHashTableを作成する静的結合メソッドを記述します。簡単にするために、両方にキーが存在する場合は、2番目の値が最初の値をオーバーライドするようにします。 例 static join(table1, table2) {    // Check if both args are HashTables    if(!table1 instanceof HashTable || !table2 instan

これがHashTableクラスの完全な実装です。もちろん、これは、より効率的なデータ構造と衝突解決アルゴリズムを使用することで改善できます。 例 class HashTable {    constructor() {       this.container = [];       // Populate the container with empty arrays       // which can be used to add more elements in &nbs

ツリーは、組織階層チャート、ファイルシステムなどの階層構造を表します。より正式に言えば、ツリーはノードのコレクションとして再帰的に（ローカルに）定義できます（ルートノード）。ここで、各ノードは、ノード（「子」）への参照のリストとともに値で構成されるデータ構造であり、参照が重複しないという制約があります（つまり、各子には1つの親があります）。

バイナリツリーは、データストレージの目的で使用される特別なデータ構造です。二分木には、各ノードが最大2つの子を持つことができるという特別な条件があります。バイナリツリーには、検索が並べ替えられた配列と同じくらい高速であり、挿入または削除操作がリンクリストと同じくらい高速であるため、順序付き配列とリンクリストの両方の利点があります。 これは、以下で説明するいくつかの用語を含む二分木の図です- 重要な用語 以下は、ツリーに関する重要な用語です。 パス −パスとは、ツリーのエッジに沿ったノードのシーケンスを指します。 ルート −ツリーの最上部にあるノードはルートと呼ばれます。ツ

二分探索木は特別な動作を示します。ノードの左の子はその親の値よりも小さい値である必要があり、ノードの右の子はその親の値よりも大きい値である必要があります。 このセクションでは、主にそのような木に焦点を当てます。 二分探索木の操作 二分探索木で次の操作を定義します- キーをツリーに挿入する ツリー内の順序どおりの走査 ツリーでトラバーサルを事前注文する ツリー内のポストオーダートラバーサル ツリー内の値の検索 ツリーで最小値を検索する ツリーで最大値を検索する ツリーのリーフノードを削除する

ツリーの各要素はノードです。ツリーはノードで構成されているため、バイナリツリーの定義に進む前に、ノードを定義する必要があります。左、右、データの3つのプロパティを持つ非常に単純なノード定義を作成します。 左 −これは、このノードの左の子への参照を保持します。 正しい −これは、このノードの右の子への参照を保持します。 データ −これは、このノードに保存するデータへの参照を保持します。 そのような構造のコード表現を見てみましょう。 例 class Node {    constructor(data, left = null, right = null