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 を照会できない問題の解決方法

推薦する

Navicat を使用してリモート Linux MySQL データベースに接続するときに発生する 10061 不明エラーの詳細な説明

Navicat を使用してリモート Linux MySQL データベースに接続すると、不明なエラー ...

VMware Workstation 14 Pro インストール Ubuntu 16.04 チュートリアル

この記事では、VMware Workstation14 ProにUbuntu 16.04をインストー...

HTML CSS3は画像表示効果を引き伸ばさない

1. transform 属性を使用して、画像を拡大せずに表示します (パスの問題は必要に応じて修正...

MySQL DEFINER の使用方法の詳細な説明

目次序文: 1.DEFINERの簡単な紹介2. いくつかの注意点要約:序文: MySQL データベー...

フロントエンド例外 502 不正なゲートウェイの原因と解決策

目次502 不正なゲートウェイ エラーの発生1. 502 不正なゲートウェイ エラーとは何ですか? ...

JS配列インデックス検出におけるデータ型の問題の詳細な説明

WeChat アプレット プロジェクトを書いていたとき、その中に「都市選択」機能がありました。作者は...

レスポンシブウェブデザインを実現するためにIEでCSS3メディアクエリをサポートする

今日の画面解像度は、320 ピクセル (iPhone) ほど小さいものから、2560 ピクセル以上 ...

js で継承を実装する 5 つの方法

コンストラクタの借用この手法の基本的な考え方は単純です。サブタイプ コンストラクター内からスーパータ...

Dockerイメージサイズを最適化する一般的な方法

通常、私たちが構築する Docker イメージはサイズが大きく、多くのディスク領域を占有します。コン...

VUEトークンの無効化プロセスの詳細な説明

目次ターゲット思考分析コード着陸要約するターゲットトークンの有効期限切れシナリオの処理トークンは、ユ...

GIFアニメーション効果を模倣した自動ビデオ再生を実現するWeChatアプレットの例

需要背景:ミニプログラムページに GIF ダイナミック画像を挿入しますが、GIF 画像は通常サイズが...

Docker Swarmの概念と使用法の詳細な説明

Docker Swarm は、Docker によって開発されたコンテナ クラスター管理サービスです。...

MySql5.x を MySql8.x にアップグレードする方法と手順

MySQL 5.x と MySQL 8.0.X のいくつかの違いapplication.proper...

MySQL の null (IFNULL、COALESCE、NULLIF) に関する知識ポイントのまとめ

この記事では、MySQL の null (IFNULL、COALESCE、NULLIF) に関連する...

MySQL最適化ツール(推奨)

序文今日 GitHub を閲覧していたところ、SQL を最適化および書き換えるための sora とい...