JavaScript でツリー構造を構築するための効率的なアルゴリズムについての簡単な説明

JavaScript でツリー構造を構築するための効率的なアルゴリズムについての簡単な説明

導入

組織階層、州、市、郡、動物や植物の分類など、ツリー状のデータ構造によく遭遇します。以下はツリー構造の例です。

実際のアプリケーションでは、特に 1 対多の親/子ノード関係がある場合、この情報を次の構造として保存するのが一般的です。

定数データ = [
  { id: 56, 親ID: 62 },
  { id: 81, 親ID: 80 },
  { id: 74, 親ID: null },
  { id: 76, 親ID: 80 },
  { id: 63, 親ID: 62 },
  { id: 80, 親ID: 86 },
  { id: 87, 親ID: 86 },
  { id: 62, 親ID: 74 },
  { id: 86, 親ID: 74 },
];

では、このオブジェクト配列形式を階層ツリー形式に変換するにはどうすればよいでしょうか?実際、JavaScript オブジェクト参照の特性を利用すると、実装は非常に簡単です。再帰なしで O(n) 時間で実行できます。

用語

便宜上、まずいくつかの用語を定義しましょう。配列内の各要素 (つまり、ツリー図内の各円) を「ノード」と呼びます。ノードは、複数のノードの「親ノード」になることも、特定のノードの「子ノード」になることもできます。上図では、ノード 86 はノード 80 とノード 87 の「親ノード」であり、ノード 86 はノード 74 の子ノードです。ツリーの最上位ノードは「ルートノード」と呼ばれます。

アイデア

ツリー構造を構築するには、次のものが必要です。

  • データ配列を走査する
  • 現在の要素の親要素を見つける
  • 親要素オブジェクトに子要素への参照を追加する
  • 要素に親がない場合、その要素はツリーのルート ノードであるとみなされます。

参照はオブジェクト ツリーに格納されていることがわかります。そのため、このタスクは O(n) 時間で完了できます。

ID配列インデックスのマッピング関係を確立する

必須ではありませんが、このマッピング関係により、要素の場所をすばやく見つけ、親要素への参照を見つけやすくなります。

const idMapping = data.reduce((acc, el, i) => {
  acc[el.id] = i;
  acc を返します。
}, {});

マッピングの結果は次のようになります。後でその有用性がわかります。

{

56: 0,

62: 7,

63: 4,

74: 2,

76: 3,

80: 5,

81: 1,

86: 8,

87: 6,

};

ツリー構造の構築

ここで、このツリー構造の構築を開始します。オブジェクトの配列を反復処理し、各要素の親オブジェクトを見つけて、要素への参照を追加します。これで、この idMapping が要素の検索にどれほど便利であるかがわかるはずです (一定時間)。

根付かせる;
データ.forEach(el => {
  // ルートノードを決定する if (el.parentId === null) {
    ルート = el;
    戻る;
  }
  // マッピング テーブルを使用して親要素を見つけます const parentEl = data[idMapping[el.parentId]];
  // 現在の要素を親要素の `children` 配列に追加します。parentEl.children = [...(parentEl.children || []), el];
});

終わり! console.log を使用してルートを出力し、次を確認します。

コンソールログ(ルート);

{

id: 74,

親ID: null、

子供たち: [

{

id: 62,

親ID: 74,

子: [{ id: 56, 親ID: 62 }, { id: 63, 親ID: 62 }],

},

{

id: 86,

親ID: 74,

子供たち: [

{

id: 80,

親ID: 86,

子: [{ id: 81, 親ID: 80 }, { id: 76, 親ID: 80 }],

},

{ id: 87, 親ID: 86 },

]、

},

]、

};

原理

なぜこれが可能なのでしょうか?これは、データ配列内の各要素がメモリ内のオブジェクトへの参照であり、forEach ループ内の el 変数が実際にはメモリ内のオブジェクトを指し、parentEl もオブジェクトを参照するためです。

メモリ内のオブジェクトが子配列を参照する場合、これらの子要素も自身の子要素配列を参照できます。これらの関連付けはすべて参照を通じて完了します。

要約する

オブジェクト参照は JavaScript の最も基本的な概念の 1 つであり、より多くの学習と理解が必要です。この概念を本当に理解すると、厄介なバグを回避し、一見複雑に見える問題に対して比較的単純な解決策を見つけることができます。

上記は、JavaScript でツリー構造を構築するための効率的なアルゴリズムの詳細についての簡単な説明です。ツリー構造を構築するための JavaScript アルゴリズムの詳細については、123WORDPRESS.COM の他の関連記事をご覧ください。

以下もご興味があるかもしれません:
  • JS 面接の質問 --- アルゴリズムの手順に関する質問
  • Vue で crypto-js AES 対称暗号化アルゴリズムを使用して暗号化と復号化を実装する
  • Matlab による JavaScript プログラミング、重心アルゴリズムによる位置決め学習
  • JavaScript で実装された 7 つのソート アルゴリズムの概要 (推奨!)
  • JS での多段階ソートアルゴリズムの実装コード
  • JS でシンプルなカレンダー アルゴリズムを実装する方法
  • JavaScript アルゴリズムの面接の質問

<<:  mysql-8.0.11-winx64.zip の詳細なインストール チュートリアル

>>:  Linux CentOS 6.5 ifconfig が IP を照会できない問題の解決方法

推薦する

既存のDockerコンテナの内容を変更する方法

1. Docker psはコンテナをリストします 2. Docker cpはコンテナにファイルをコピ...

LinuxサーバのSSHクラッキング防止方法(推奨)

1. Linuxサーバーは、/etc/hosts.denyを設定して、相手のIPがSSH経由でサー...

DockerToolBox ファイルマウント実装コード

docker を使用すると、ファイルをマウントできない場合があります。これは、仮想マシンの共有フォル...

MySQL の大文字と小文字の区別に関する注意

目次MySQLの大文字と小文字の区別はパラメータによって制御されますMySQLの大文字と小文字の区別...

JS はシンプルなブロック崩しピンボールゲームを実装します

この記事では、ブロック崩しピンボールゲームを実装するためのJSの具体的なコードを参考までに紹介します...

Windows (x86、64 ビット) で MySQL 5.7.17 無料インストール バージョンをアップグレードするための詳細なチュートリアル

Laravel 5.4 のデフォルトの utf8mb64 文字エンコーディングをサポートするには、M...

MySQLでJSONフィールドを操作する方法

MySQL 5.7.8 では json フィールドが導入されました。このタイプのフィールドは使用頻度...

MySQLインジェクションバイパスフィルタリング技術の概要

まず、GIF 操作を見てみましょう。ケース1: スペースがフィルタリングされるスペースの代わりに角括...

Markodwnによるタイトル配置による同期スクロールのアイデアの詳細な説明

序文私が作成中の Markodwn エディターに同期スクロール機能を追加する必要があります。Baid...

JavaScript でイベントのバブリングを防ぐ方法

注意すべき点は、イベントバブリング自体の特性上、メリットだけでなくデメリットも生じるということです。...

KVM 仮想化のインストール、展開、管理のチュートリアル

目次1.kvmの展開1.1 kvmのインストール1.2 kvm Web管理インターフェースのインスト...

ワンクリックで雨や雪のエフェクトを実現する ThingJS パーティクルエフェクト

目次1. パーティクルエフェクト2. シーンを読み込む3. さまざまな粒子効果の実現エンディング: ...

jQueryは居住地を選択するためのドロップダウンボックスを実装します

居住地を選択するためのドロップダウンボックスをjQueryで実装するための具体的なコードは参考までに...

http:// の代わりに // を使用する利点は何ですか (アダプティブ https)

//デフォルトプロトコル/ デフォルト プロトコルの使用は、リソース アクセス プロトコルが現在の...

Linux コマンド sort、uniq、tr ツールの詳細な説明

並べ替えツールLinux の sort コマンドは、テキスト ファイルの内容を並べ替えるために使用さ...