1

私は現在、カテゴリ階層を開発しており、ツリー トラバーサルを作成するポイントを得たと思います。しかし、PHP 関数を使用して、この階層に新しいノードを追加する必要があります。

問題は、rebuild_tree 関数で十分である (つまり、大きなツリーで効率的) ことです。

サンプルクエリ:

 CREATE TABLE `t_categories`(
   `id` INTEGER UNSIGNED NOT NULL AUTO_INCREMENT,
   `title` VARCHAR(45) NOT NULL,
   `lft` INTEGER UNSIGNED NOT NULL,
   `rght` INTEGER UNSIGNED NOT NULL,
   PRIMARY KEY (`id`)
 );

 INSERT INTO t_categories (title, lft, rght) VALUES ('Cat 1',1,16);
 INSERT INTO t_categories (title, lft, rght) VALUES ('Cat 2',2,3);
 INSERT INTO t_categories (title, lft, rght) VALUES ('Cat 3',4,7);
 INSERT INTO t_categories (title, lft, rght) VALUES ('Cat 4',5,6);
 INSERT INTO t_categories (title, lft, rght) VALUES ('Cat 5',8,13);
 INSERT INTO t_categories (title, lft, rght) VALUES ('Cat 6',9,12);
 INSERT INTO t_categories (title, lft, rght) VALUES ('Cat 7',10,11);
 INSERT INTO t_categories (title, lft, rght) VALUES ('Cat 8',14,15);

テーブルの結果は次のようになります。

 ID    TITLE   LFT    RGHT
 1     Cat1    1      16
 2     Cat2    2      3
 3     Cat3    4      7
 4     Cat4    5      6
 5     Cat5    8      13
 6     Cat6    9      12
 7     Cat7    10     11
 8     Cat8    14     15

上記でサンプルデータを提供しましたが、まったく新しいノードもゼロから作成する必要があります。

では、大きなツリーを効率的に処理する PHP 関数を使用して、このツリーに新しいノードを追加するにはどうすればよいでしょうか?

4

4 に答える 4

2

セルコの木です。最も単純なアプローチは、ツリーの深さ優先のトラバーサルであり、左の値のみを更新し、次に再帰的に右の値を更新します。挿入ははるかにコストがかかります。

于 2011-03-07T18:31:54.417 に答える
2

「左」および「右」フィールドの代わりに、「親 ID」フィールドをテーブル構造に追加することをお勧めします。子アイテムの注文が重要な場合は、「localorder」int フィールドも使用します。

現在の構造では、アイテムを追加するたびに、最初のアイテムについては前のアイテムがあるかどうかを確認し、最後のアイテムについては最終アイテムがあるかどうかを確認する必要があります。

CREATE TABLE `t_categories`(
   `keyid` INTEGER UNSIGNED NOT NULL,
   `title` VARCHAR(45) NOT NULL,
   `parentid` INTEGER UNSIGNED NOT NULL,
   `sortorder` INTEGER UNSIGNED NOT NULL,
   PRIMARY KEY (`id`)
 );

-- root item, no parent
 INSERT INTO t_categories (keyid, title, parentid, sortorder) VALUES (1, 'Root', 0, 0);

-- first level
 INSERT INTO t_categories (keyid, title, parentid, sortorder) VALUES (2, 'a:', 1, 1);
 INSERT INTO t_categories (keyid, title, parentid, sortorder) VALUES (3, 'b:', 1, 2);
 INSERT INTO t_categories (keyid, title, parentid, sortorder) VALUES (3, 'c:', 1, 3);
 INSERT INTO t_categories (keyid, title, parentid, sortorder) VALUES (4, 'd:', 1, 4);

-- second level

 INSERT INTO t_categories (keyid, title, parentid, sortorder) VALUES (5, 'a:\temp', 2, 1);
 INSERT INTO t_categories (keyid, title, parentid, sortorder) VALUES (6, 'a:\docs'', 2, 2);
 INSERT INTO t_categories (keyid, title, parentid, sortorder) VALUES (7, 'a:\music', 2, 3);

 INSERT INTO t_categories (keyid, title, parentid, sortorder) VALUES (8, 'c:\temp', 4, 1);
 INSERT INTO t_categories (keyid, title, parentid, sortorder) VALUES (9, 'c:\docs'', 4, 2);
 INSERT INTO t_categories (keyid, title, parentid, sortorder) VALUES (10, 'c:\music', 4, 3);

-- and so on
于 2011-03-07T18:34:08.980 に答える
0

私の以前の答えは不完全です。これは要約です。コード全体をフォーラムに投稿するには長すぎます。手続き型 PHP、またはオブジェクト指向 PHP について質問するのを忘れましたか?

MySQL: CREATE TABLE t_categories( keyidINTEGER UNSIGNED NOT NULL, titleVARCHAR(45) NOT NULL, parentidINTEGER UNSIGNED NOT NULL, sortorderINTEGER UNSIGNED NOT NULL, PRIMARY KEY ( id) );

PHP 関数ヘッダー:

// グローバル変数、型のように機能します /* typedef */ treeNodeType = array( "keyid" => 0, "title" => "", "parentid" => 0, "sortorder" => 0, )

// globar var, 型のように振る舞う /* typedef */ treeType = array( "root" => nil, "whatever" => "", )

/* treeNodeType / function insertNode(/ treeType / ATree, AParentId, ATitle) { ... } / void / function deleteNode(/ treeType */ ATree, AKeyId) { ... }

// --> メイン main();

/* void */ function main() { // treeType myTree; myTree = ツリータイプ;

// ルートを挿入 = 0 rootNode = insertNode(myTree, 0, '[PC]');

... }

于 2011-03-08T16:19:48.920 に答える
0

ハフマン圧縮では、同じツリーを使用して、指定されたドキュメント内の文字の出現をカウントします。文字列をエンコードすると、アルゴリズムは深さ優先トラバーサルも使用して、出現回数が最も多い文字が可能な限り最小のビットでエンコードされるようにします。ここで役立つかどうかはわかりませんが、テキストの最小エントロピーは、シャノン定理 -log(x)+log(2) を使用して検出されます。ここで、x は文字で、log(2) は常にビット単位のベースです。 2.

于 2011-03-07T20:23:30.557 に答える