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 },
]、
},
]、
};