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

では、このような構造でノードを追加、更新、削除するにはどうすればよいでしょうか? 一般に、ノードを追加するには 2 つの方法があります:

元の名前と親構造を保持し、古い方法を使用してデータにデータを追加し、rebuild_tree 関数を使用して各データの後で構造全体の番号を再設定します。が追加されます。
より効率的な方法は、新しいノードの右側にあるすべての値を変更することです。たとえば、「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; これは新しいものです。 insert 値によりスペースが解放されました。解放されたスペースに新しいデータ ノードを作成できます。その左と右の値はそれぞれ 6 と 7 です。

INSERT INTO ツリー SET lft=6、rgt=7。 , name='Strawberry';

別のクエリを実行して見てみましょう。どうでしょうか？すぐ。
さて、マルチレベルのデータベース構造を設計するために 2 つの異なる方法を使用できます。どちらの方法を使用するかは完全に個人の判断に依存しますが、多くのレベルと大量の構造の場合は 2 番目の方法を好みます。クエリの量は少ないが、データを頻繁に追加および更新する必要がある場合は、最初の方法の方が簡単です。

また、データベースがサポートしている場合は、データベース側でトリガー関数としてrebuild_tree()と領域解放操作を記述し、挿入および更新時に自動的に実行することもできます。また、新しいノードを追加するための SQL ステートメントも簡素化されます。
準再帰メソッド
ゲストによる投稿: 2004 年 5 月 31 日 - 午前 9 時 18 分
私は準再帰メソッドを使用してプログラムを書きました。これは記事の再帰とはまったく同じではありません。 > xoops に移植する準備をしています:
http://dev.xoops.org/modules/xfmod/project/?ulink

メモリ オーバーフローが発生しました
ただし、再帰的手法を使い続ける必要がありますが、改善し続ける必要があります

cms について話し合う機会があれば幸いです
» このコメントに返信
または 2 つの手法の比較
ゲストによる投稿、2004 年 3 月 17 日 - 午後 8 時 30 分
よく勉強してください この記事を読んだ後、私は多くの恩恵を受けたと感じましたが、もう一度よく考えてみると、問題があると感じました。記憶のために、隣接ディレクトリ モードを再帰的メソッドと呼び、事前にソートされたツリー トラバーサル アルゴリズムを事前ソート ツリー メソッドと呼びます)):

1. 2 つのメソッドの最大の違いは次のとおりです。その再帰ではクエリ時にスタックの使用が必要ですが、事前ソート ツリーではノードの半分を更新するときに再帰の半分 (挿入されたノードの最後の部分を参照) が必要です。ノードが多くて更新が頻繁な場合、事前にソートされたツリーの効率が低下し、ノードレベルが多い場合は再帰の方が良いとも述べていますが、まず第一に、再帰はスタックオーバーフローを引き起こします。さらに、再帰自体はあまり効率的ではなく、再帰の各レベルでデータベースの操作が必要になるため、全体的な効果は理想的ではありません。私の現在のアプローチは、すべてのデータを一度に取り出してから、配列に対して再帰的な操作を実行することです。これをさらに改善できれば、ROOT ルート ノードをレコードの各行に追加できます (現時点では、隣接する親ノードも記録される）ので、枝木を探索する際の効率が良くなり、木を更新する際にも非常に便利になるので、より良い方法となるはずです。

2. 再帰的方法を改善します。記事では、事前にソートされたツリー ノードの左右の値を計算するときに、実際にスタックを配列に置き換えます。 、スタックは手動でプッシュおよびポップされます。このメソッドは再帰アルゴリズムで参照され、再帰を実行するときにスタックの代わりに配列が使用される場合、再帰の効率も向上します。

3. 同時実行性。特にツリーを更新する場合、同時実行性を考慮する場合、大規模な領域でノード情報を更新するためにツリーを事前にソートする方法では、ロックとトランザクションのメカニズムの使用に特に注意を払う必要があります。データの一貫性。

4. 複数のルート ノードまたは複数の親ノードの場合、この場合、明らかに標準のバイナリ ツリーまたはマルチツリーではないため、事前にソートされたツリー アルゴリズムを大幅に改善する必要があります。再帰的方法は簡単に適用できるため、この場合は再帰の方が適応性が高くなります。これは、再帰的手法がリンク リストの形式であるため、当然、適応性が高くなります。

5. 直感的です。プログラムを操作せずにデータベースに保存されたデータを直接観察すると、再帰モードで保存されたデータの方が直感的であることがわかりますが、事前にソートされたツリー内のデータは (階層構造の場合) 直接読み取るのが困難です。これはデータ交換において重要です。影響はありますか?

一般的に、私は個人的に再帰的手法を使用することを好みますが、幸いなことに、大規模な分類レベルにさらされたことがないため、再帰が効率に与える影響について常に心配していました。再帰にはスタックの代わりに配列を使用するのが良い方法です。事前にソートされたツリーは、単純なツリーを解決するための効率的な方法であり、慣れてしまえば非常に優れています。特に、葉ノードからルート ノードへの逆探索が非常に便利です。

Fwolf
www.fwolf.com
» このコメントに返信
返信を見てとても嬉しいです
Posted by shuke on 2004, March 18 - 5:47am この記事を注意深く読んでいただけてとてもうれしいです。この記事はもともと sitepoint.com で公開されたもので、これから始めたいと考えている友人にいくつかの方法を紹介したいと考えて翻訳しました。あなたの方法もとても良いので、機会があれば試してみたいと思います。 (興味があれば、上記の例に基づいてチュートリアルとしてメソッドと具体的な実装コードを作成してみてはいかがでしょうか。そうすれば、より実践的な例で誰もが真似できるようになります) データベースへのマルチレベル構造の保存について質問がある場合研究に興味がある方は、参考として使用できる 2 つのリンクを紹介します。
4 つの一般的なメソッドの紹介
1 つのクエリ、配列ソート スクリプト あなたのスクリプトはこれより優れているはずです。
さらに、drupal には分散ユーザー認証システムという高度な機能もあります。どの drupal サイトでも登録していれば、ログインして他の Drupal サイトにアクセスできます。なかなか興味深いですね。
頑張ってください！
» このコメントに返信
ループを使用してツリーを構築することが実現しました
投稿者: 2004 年 3 月 25 日 - 午後 10 時 10 分
前回提供していただいた情報はすべて読みました。正直に言うと、最初の記事はあまり新しい内容がありませんでした。2 番目の記事はプログラムの構造をよく見ていなかったため、関数を使いすぎたのかもしれません。交差点。
システム内で階層的なユーザー ロールを使用する必要があるため、配列のアイデアに従って走査を書き留めました。整理する時間がないので、ここに記載します。データベースは ADODB を使用しており、プログラムはシステムから直接取り出したもので、主に PHP の強力な配列操作を使用し、再帰を実行するためにループを使用します。コメントも同様の方法ですが、結果を処理するタイミングが異なります。