php:ツリー構造アルゴリズム 1

ジョイ・ムラカミからの転載 私は以前この記事を読んだことがありますが、それは非常に明確です。

製品カテゴリ、マルチレベルのツリー構造のフォーラム、メーリング リスト、その他多くの場所で、次の問題に遭遇します。マルチレベル構造のデータをどのように保存するか?

PHP アプリケーションでは、バックエンド データ ストレージは通常、大量のデータを保存し、効率的なデータ取得と更新サービスを提供できるリレーショナル データベースです。ただし、リレーショナル データの基本的な形式はフラットな構造である十字テーブルです。リレーショナル データベースに複数レベルのツリー構造を格納したい場合は、適切な変換作業を実行する必要があります。次に、私が見聞きしたことと実際の経験についてお話します。

フラット データベースに階層データを格納するには、基本的に 2 つの一般的な設計方法があります。

隣接リスト モデル (隣接リスト モデル)
プレオーダー トラバーサル ツリー アルゴリズム (修正されたプレオーダー ツリー トラバーサル アルゴリズム)
私はコンピューターを専攻していませんし、データ構造について何も学んでいないので、これら 2 つの名前を文字通りに翻訳しました。間違っている場合はアドバイスをお願いします。

この 2 つは怖く聞こえるかもしれませんが、実際は非常に簡単に理解できます。ここでは、サンプル データとして単純な食品ディレクトリを使用します。 データ構造は次のとおりです。


|---果物
| |--チェリー
| |--黄色
|--肉
|赤: 赤
チェリー: チェリー
黄: 黄色
バナナ: バナナ
肉: 肉
牛肉: 牛肉
豚肉: 豚肉

隣接ディレクトリ モード (隣接list モデル)

このモデルはよく使われており、多くのチュートリアルや書籍でも紹介されています。各ノードに親ノードを追加して、このノードの親ノードを表すことにより、フラット テーブルを通じてツリー構造全体を記述します。この原則に従って、例のデータは次のテーブルに変換できます:

+-----------------------+
| 名前 |
+-----------+
| |
| 緑 |
| 黄色 | > | 肉 | 肉
|
Pear が Green の子ノードであり、Green が Fruit の子ノードであることがわかります。ルート ノード「Food」には親ノードがありません。 この問題を簡単に説明するために、この例では名前のみを使用してレコードを表します。 実際のデータベースでは、各ノードを識別するために数値 ID を使用する必要があります。データベースのテーブル構造は、id、parent_id、name、description のようになります。このようなテーブルを使用すると、マルチレベル ツリー構造全体をデータベースに保存できます。

多レベルツリーの表示
このような多レベル構造を表示する必要がある場合は、再帰関数が必要です。

// $parent は確認したい子の親です
// $level はツリーの奥深くに進むと増加します。
// 使用されますきれいにインデントされたツリーを表示するには

function display_children($parent, $level)
{
// 親ノードのすべての子ノードを取得 $parent
$result = mysql_query('SELECT name FROM ツリー '.
'WHEREparent="'.$parent.'";');

// 各子ノードを表示します
while ($row = mysql_fetch_array($result))
{
// ノード名をインデントします
echo str_repeat(' ',$level).$row['name']."n";

// これをもう一度呼び出します関数は子ノードの子ノードを表示します。構造全体のルート ノード (Food) でこの関数を使用すると、マルチレベル ツリー構造全体を出力できます。Food はルート ノードであり、その親ノードは空であるため、次のように呼び出されます。display_children('',0)。 ）。ツリー全体の内容が表示されます:


食べ物
果物
赤
チェリー
黄
バナナ
肉
牛肉
Pork
フルーツの部分など、構造全体の一部だけを表示したい場合は、次のように呼び出すことができます:

display_children('Fruit',0); 🎜> ほぼ同じ方法を使用して、ルートノードから任意のノードまでのパスを知ることができます。たとえば、チェリーのパスは「食べ物 > 果物 > 赤」です。 このようなパスを取得するには、最も深いレベル「Cherry」から開始し、クエリを実行してその親ノード「Red」を取得してパスに追加し、次に Red の親ノードをクエリしてパスに追加する必要があります。など、最高レベルの「Food」まで続きます。

// $node は最も深いノードです
function get_path($node)
{
/ /このノードの親ノードをクエリします
$result = mysql_query('SELECT 親 FROM ツリー '.
'WHERE name="'.$node.'";');
$row = mysql_fetch_array($) result);

// 配列を使用してパスを保存します
$path = array();

// ルート ノードでない場合は、上方向にクエリを続行します
// (ルートノード 親ノードなし)
if ($row['parent']!='')
{
// $node へのパスの最後の部分は名前です
// $node の親
$path[] = $row['parent'];

// このノードの親にパスを追加する必要があります
//パスへ
$path = array_merge(get_path($row['parent']), $path);
}

// パスを返します
return $path; > }
? >
「Cherry」にこの関数を使用すると、次のような配列が得られます:


Array
(
[0] => 食べ物
[1] => 果物
[2] => 赤
)
希望の形式で印刷する方法は、あなたのビジネス。
欠点: この方法は非常にシンプルで、理解しやすく、使いやすいです。しかし、いくつかの欠点もあります。主な理由は、実行速度が非常に遅いこと、各ノードでデータベース クエリが必要であること、データ量が多い場合にはツリーを完成させるために多くのクエリが必要になることです。さらに、再帰的な操作が必要なため、再帰の各レベルである程度のメモリを占有する必要があるため、スペースの利用効率は比較的低くなります。

次に、再帰計算を使用しない別の高速な方法を見てみましょう。これは、修正された事前順序ツリー走査アルゴリズムです。初めての方は、それほど簡単ではないかもしれません。上記の方法と同様に理解できますが、この方法は再帰的なクエリアルゴリズムを使用しないため、クエリ効率が高くなります。

まず、次のように多層データを紙に描きます。ルート ノード Food の左側に 1 を書き込み、次にツリーを下に進み、Fruit の左側に 2 を書き込み、先に進みます。 . 、ツリー全体の端に沿って、各ノードに番号のラベルを付けます。最後の数字は Food の右側にマークされた 18 です。 下の図では、番号が付けられたマルチレベル構造全体が表示されます。 （わかりませんか？指で数字を指して、1から18まで数えてみるとわかります。それでもわからない場合は、指の動きに注意してもう一度数えてください。）
これらの番号は各ノード間の関係を示しています。「赤」の番号は 3 と 6 であり、「食べ物」1 ～ 18 の子孫ノードです。 同様に、左側の値が 2 より大きく、右側の値が 11 未満であるすべてのノードは、「Fruit」2-11


の子孫ノードであることがわかります。