左右の値の無限分類を解析するための実装アルゴリズム_PHP チュートリアル-PHPチュートリアル-php.cn

1. はじめに
製品分類、マルチレベルのツリー構造のフォーラム、メーリングリスト、その他多くの場所で、次のような問題に遭遇します。マルチレベル構造のデータを保存するにはどうすればよいですか? PHP アプリケーションでは、バックエンドデータストレージは通常、大量のデータを保存し、効率的なデータ取得と更新サービスを提供できるリレーショナルデータベースです。ただし、リレーショナルデータの基本的な形式はフラットな構造である十字テーブルです。リレーショナルデータベースに複数レベルのツリー構造を格納したい場合は、適切な変換作業を実行する必要があります。次に、私が見聞きしたこと、および実際の経験について説明します。
フラットデータベースに階層データを格納するには、基本的に 2 つの一般的な設計方法があります:
* 隣接ディレクトリモード (隣接リストモデル)
* * 修正されたプレオーダーツリートラバーサルアルゴリズム
私はコンピューターの専門家ではなく、データ構造について何も学んだことがないので、これら 2 つの名前を文字通りに翻訳しました。はい、間違っている場合はお知らせください。この 2 つは怖く聞こえるかもしれませんが、実際には非常に簡単に理解できます。

2. モデル
ここでは、サンプルデータとして単純な食品カタログを使用します。
データ構造は次のようになります。コードは次のとおりです:

コードをコピーしますコードは次のとおりです:

Food

|---Fruit

|---Red

 | |-- チェリー

| +---黄色

| +--バナナ

+---肉
 |--牛肉
 +-豚肉

英語の混乱

コードをコピーコードは次のとおりです:

Food : 食べ物 
Fruit : Fruit 
Red : 赤 
Cherry : チェリー 
Yellow : Yellow 
Banana : Banana 
Meat : Meat 
牛肉 : Beef 
Pork : Pork 

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

コードをコピーしますコードは次のとおりです:

+------ ---------- --------+
| 親の名前 |
+---------------------- |
| 食べ物 |
| 緑 |
| 果物 |
|食べ物 |
| 牛肉 | 豚肉 |
+---------------------+

 Green の子ノード、Green は Fruit の子ノードです。ルート ノード「Food」には親ノードがありません。 この問題を簡単に説明するために、この例では名前のみを使用してレコードを表します。 実際のデータベースでは、各ノードを識別するために数値 ID を使用する必要があります。データベース テーブルの構造は、id、parent_id、name、description のようになります。 
このようなテーブルを使用すると、データベースを通じてマルチレベルのツリー構造全体を保存できます。 
複数レベルのツリーを表示する このような複数レベルの構造を表示する必要がある場合は、再帰関数が必要です。 
コードは次のとおりです:

コードをコピーします

コードは次のとおりです:

// $parent は見たい子の親です
// $level はツリーの奥深くに行くと増加します
// きれいにインデントされたツリーを表示するために使用されます
function display_children( $parent, $level) {
 // 親ノードのすべての子ノードを取得 $parent $result = mysql_query("
 SELECT name
 FROM Tree
 WHEREparent = '" . $parent . "'
 ; ;"
 ) ;
 // 各子ノードを表示します
 while ($row = mysql_fetch_array($result)) {
 // ノード名をインデントします
 echo str_repeat(' ', $level) "n . "; /// この関数を再度呼び出して、子ノードのサブノードを表示します 
 Display_children ($ row ['name'], $ level+1); 
}}} 
? & Gt; 


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

以下のコードをコピーします。

FoodFRUITRedCherryYELLOW

BANANA

Meat
Beef
PORK

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

コードをコピーします

コードは次のとおりです:

// $node は最も深いノードです function get_path($node ; $row = mysql_fetch_array($result ); // 配列を使用してパスを保存します $path = array();

// ルートノードでない場合は、上方向に検索を続けます

/ /（ルートノードには親ノードがありません）if（$ row ['parent']！= ''）{
$ノードへのパスの最後の部分は、このノードの親へのパスです
/ / / パスへ
$ PATH = Array_Merge (Get_path ($ Row ['Parent']), $ PATH);
?>;

「Cherry」にこの関数を使用する場合: print_r(get_path(' Cherry'))、次のような配列が得られます:

コードをコピーします

コードは次のとおりです:

Array (
[0] => Food
[1] => Fruit
[2] =>レッド
)

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

2. プレオーダーツリートラバーサルアルゴリズム
次に、再帰計算を使用しない別の高速な方法を見てみましょう。これは、修正されたプレオーダーツリートラバーサルアルゴリズムです。この方法は、あまり使われていないかもしれません。初めて使用する場合は、上記の方法ほど理解しにくいですが、この方法は再帰的なクエリアルゴリズムを使用しないため、クエリ効率が高くなります。

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

コードをコピーしますコード

1 食品 18. ----------++--------------+

3 赤 6 7 黄 10 13 牛肉 14 15 豚肉 16

4 チェリー 5 8 バナナ 9

 これ ツリー構造全体を左右の値とともにデータベースに保存できます。続行する前に、以下の編集されたデータ表を見てみましょう。 
コードは次のとおりです: 

コードをコピーします

コードは次のとおりです:

+----------+------------+ -----+ -----+

| 親の名前 |+----------+----------+-- ---+-----+| 食品 2 | 6 | |果物 | 7 | 10 | | 肉 12 | 肉 | ----------+------------+-----+-----+

注:

「左」と「右」が使用されているため、 SQL では特別な意味があるため、「lft」と「rgt」を使用して左右のフィールドを表す必要があります。さらに、この構造ではツリー構造を表すために「親」フィールドは必要なくなりました。つまり、次のようなテーブル構造であれば十分です。
コードは次のとおりです:

コードをコピーします

コードは次のとおりです:

+-----+-----+-----+
| 名前 |
+------ ---- +-----+-----+
| 1 | 11 |
| | 黄色 | 7 | 
| 12 | 16 | 
| ---+ -----+-----+


 さて、これでデータベースからデータを取得できるようになりました。たとえば、「Fruit」項目の下にあるすべてのノードを取得する必要がある場合は、次のようになります。次のようにクエリ ステートメントを記述します: 


 
コードをコピー

コードは次のとおりです:

SELECT * FROM Tree WHERE lft BETWEEN 2 AND 11;このクエリは次の結果を取得しました。コードは次のとおりです:

コードをコピーします

コードは次のとおりです:

+------------+-----+----- +| 名前 |+-----+-----+|レッド | 3 | 6 || 4 | 8 |

| +-----+

 ほら、たった 1 つのクエリでこれらすべてのノードを取得できます。上記の再帰関数のようにツリー構造全体を表示できるようにするには、そのようなクエリを並べ替える必要もあります。ノードの左辺値で並べ替えます: 

 コードをコピーします 

 コードは次のとおりです:

SELECT * FROM Tree WHERE lft BETWEEN 2 AND 11 ORDER BY lft ASC;

残りの質問は、次の方法です。レベルのインデントを表示します。以下はコードです:

コードをコピーします

コードは次のとおりです:

function display_tree($root) {
// の左と右の値を取得します。ルートノード

$result = mysql_query(" SELECT lft , rgt FROM ツリー WHERE name = '" . $root . "' ) ; // ルートポイントのすべての子孫ノードを取得します

$result = mysql_query( 「lft、from from where "" 'lft' ['rgt']。 ($ right) & gt; 0) {

// ノードをスタックから移動する必要があるかどうかを確認します
($ right [count ($ right) - 1] & lt; $ row ['rgt']) {
array_pop
上記の関数を実行すると、再帰関数と同じ結果が得られます。ただ、データベースクエリが 2 つしかないため、新しい関数の方が高速になる可能性があります。
Cherry のパスを知りたい場合は、その左右の値 4 と 5 を使用してクエリを作成する方が簡単です。

コードをコピーしますコードは次のとおりです:

SELECT name FROM Tree WHERE lft < 4 AND rgt > 5 ORDER BY lft ASC;

これにより、次の結果が得られます。以下はコードです:

コードをコピーしますコードは次のとおりです:

+---------------------+

| 
+----------------+
| 食べ物 |
| 赤 |
+----------+

特定のノードにはいくつの子孫ノードがありますか?非常に単純で、子孫の総数 = (右の値 - 左の値 - 1) / 2

コードをコピーします

コードは次のとおりです:descendants = (右 - 左の値 - 1) / 2

信じられないですか？自分で計算してください。

この簡単な式を使用すると、「フルーツ 2-11」ノードには 4 つの子孫ノードがある一方、「バナナ 8-9」ノードには子孫ノードがない、つまり親ノードではないことがすぐに計算できます。
すごいですよね？私はこの方法を何度も使ってきましたが、それでもやるたびに素晴らしい気分になります。これは確かに良い方法ですが、左と右の値を持つこのようなデータテーブルを作成するのに役立つ方法はありますか?もう 1 つの関数を紹介します。この関数は、名前と親構造を持つテーブルを、左と右の値を持つデータテーブルに自動的に変換します。
次はコードです:

コードをコピーします

コードは次のとおりです:function再構築_tree($parent, $left) {

// このノードの正しい値は左の値 + 1

 $right = $left+1;
 // このノードのすべての子を取得します
 $result = mysql_query("
 SELECT name
 FROM Tree
 WHEREparent = '" . $parent . "'
 ; "
 ); 
 while ($row = mysql_fetch_array($result)) {
を使用する 使用する ' d ' ' ' ' ' を通して を通して を通して を通して を通して を通して を通してを通して を通してを通して を通してを通してright out right out'' through out through out through over'''' ‐to'‐'''-''-'-‐ s $right =再構築_tree($row['name'], $right);
 } 
 // 左の値が得られ、処理が完了しました
 // このノードの子も右の値を知っています
 mysql_query("
 UPDATE Tree
 SET
 lft = '" . $left . "',
 rgt= '" . $right . "'
 WHERE name = '" . $parent . "'
 ; "
 ) ;
 // このノードの正しい値を返します
 return $right + 1 ;
}
?>


もちろん、この関数は再帰関数です。バンドを再構築するにはルート ノードからこの関数を実行する必要があります。左と右の値を持つツリー



コードをコピーします

コードは次のとおりです:

rebuild_tree('Food',1);

この関数は少し複雑に見えますが、その機能はテーブルに手動で番号を付けるのと同じで、3 次元の多層構造を左右の値を持つデータテーブルに変換することです。
では、このような構造のノードを追加、更新、削除するにはどうすればよいでしょうか?
通常、ノードを追加するには 2 つの方法があります:
1 つ目の方法は、元の名前と親構造を保持し、古い方法を使用してデータをデータに追加し、rebuild_tree 関数を使用してノードを更新します。各データが追加された後、データ全体の番号が付け直されます。
2 番目のより効率的な方法は、新しいノードの右側にあるすべての値を変更することです。たとえば、「Red」ノードの最後の子ノードとなる新しいフルーツ「Strawberry」を追加したいとします。まず、そのためのスペースを作る必要があります。「赤」の右側の値を6から8に、「黄7～10」の左右の値を9～12に変更します。類推して、新しい値のための余地を作りたい場合は、左右の値が 5 より大きいすべてのノードに 2 を追加する必要があることがわかります (5 は「Red」の最後の子ノードの正しい値です) ）。したがって、次のようなデータベース操作を実行します:

コードをコピーコードは次のとおりです:

UPDATE ツリー SET rgt = rgt + 2 WHERE rgt > 5;
UPDATE ツリー SET lft = lft + 2 WHERE lft; > 5; 

これにより、新しく挿入された値のためのスペースが解放され、その左と右の値はそれぞれ 6 と 7 になります

。コードは次のとおりです:

INSERT INTO Tree SET lft=6, rgt=7, name='Strawberry';

 別のクエリを実行して見てみましょう!どうでしょうか？すぐ。 

4. 結論
さて、マルチレベルのデータベース構造を設計するために 2 つの異なる方法を使用できますが、どちらの方法を使用するかは完全に個人的な判断に依存しますが、多くのレベルと大量の構造の場合は、 2番目のアプローチ。クエリの量は少ないが、データを頻繁に追加および更新する必要がある場合は、最初の方法の方が簡単です。さらに、データベースがサポートしている場合は、データベース側でトリガー関数としてrebuild_tree()と領域解放操作を記述し、挿入および更新時に自動的に実行することもでき、より高い操作効率を実現できます。新しいノードを追加できるようになり、SQL ステートメントがより簡単になります。

http://www.bkjia.com/PHPjc/327714.html