PHP/MySQLを使用してツリートラバーサル階層をゼロから作成する

Question

私は現在カテゴリ階層を開発しています。しかし、私はこの階層に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関数を使用して、このツリーに新しいノードを追加するにはどうすればよいですか？

Answer 1

これはセルコの木です。 Simpelstアプローチは、ツリーの深さ優先探索であり、左の値だけを更新し、再帰的な方法で正しい値を更新します。挿入ははるかに高価です。

Answer 2

"left"と "right"フィールドではなく、 "parent 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 

Answer 3

与えられた文書の文字の出現をカウントするために同じ木がハフマン圧縮によって使用されます。私は、文字列をエンコードすると思っています。そしてアルゴリズムは、深さ優先のトラバーサルを使用して、最も出現頻度の高い文字が可能な限り少ないビットでエンコードされるようにします。ここでは有用かどうかわかりませんが、テキストの最低エントロピーはshannon theorm -log（x）+ log（2）を使って求められます。ここで、xは文字、log（2） 2.

Answer 4

私の以前の回答は不完全です。要約ですが、全体のコードはフォーラムのポストに入れることが長いです。手続き型PHP、またはオブジェクト指向PHPを忘れましたか？

のMySQL： 表t_categories（NULL UNSIGNED NOT NULL UNSIGNED NOT keyid INTEGER、 title VARCHAR（45）NOT NULL、 parentid INTEGER UNSIGNED NULL NOT、 sortorder INTEGER、 PRIMARY KEY（id） ）を作成します。

PHP関数ヘッダー：

//グローバーのVaRは、タイプ /*のtypedef */treeNodeType =配列（ "鍵ID" => 0、 "タイトル" => ""、 」のように作用しますParentID "=> 0、 "ソート順ルート "=> nilを、 " 何でも"=> 0、 ）

//グローバーのVaRは、タイプ /*のtypedef */treeType =配列（ のように働きます" "=>" "、 ）

/* treeNodeType /機能insertNode（/ treeType /ATree、AParentId、ATitle）{...} /ボイド/機能deleteNode（/ treeType */ATree、AKeyId）{...}

// - > MAIN main（）;

/* void */function main（）{ // treeType myTree; myTree = treeType;

// insert root = 0 rootNode = insertNode（myTree、0、 '[PC]'）;

... }