Создание иерархии обхода дерева с нуля с помощью PHP/MySQL

Question

В настоящее время я разрабатываю иерархию категорий, и я понял, как создать дерево treversal, я думаю. Но мне нужно добавить новый узел в эту иерархическую функцию usign 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

Это дерево celko. Подход Simpelst был бы первым пересечением дерева по глубине и обновлением только левого значения, а затем рекурсивным образом правильным значением. Вставка намного дороже.

Answer 2

Я рекомендую вам добавить поле «родительский идентификатор» в структуру таблицы вместо полей «слева» и «справа». Если для вас важны заказы на детские предметы, используйте также поле локатора.

С текущей структурой, каждый раз, когда вы хотите добавить элемент, вам нужно проверить, есть ли предыдущий элемент, для первого элемента, и проверить, есть ли последний элемент, для последнего элемента.

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

Это же дерево используется компрессией huffman для подсчета появления буквы в данном документе. Я думаю, что для кодирования строки алгоритм затем использует также обход глубины, так что буква с наибольшим количеством событий кодируется с наименьшими возможными битами. Я не знаю, полезно ли это здесь, но самая низкая энтропия текста найдена с использованием shannon theorm -log (x) + log (2), где x - буква, а log (2) - база в битах, всегда 2.

Answer 4

Мой предыдущий ответ неполный. Это резюме, весь код должен долго находиться в сообщении форума. Забыл спросить, процедурный PHP или объектно-ориентированный PHP?

MySQL: CREATE TABLE t_categories ( keyid INTEGER UNSIGNED NOT NULL, title VARCHAR (45) NOT NULL, parentid INTEGER UNSIGNED NOT NULL, sortorder INTEGER UNSIGNED NOT NULL, ПЕРВИЧНЫЙ КЛЮЧ (id) );

функции PHP заголовки:

// глобаром вар, действует как тип /* ЬурейеЕ */treeNodeType = массив ( "KeyID" => 0, "название" => "", " ParentId "=> 0, "SortOrder"=> 0, )

// глобаром вар, действует как тип /* ЬурейеЕ */treeType = массив ( "корень"=> ноль, " все "=>" ", )

/* treeNodeType /функция insertNode (/ treeType /ATree, AParentId, ATitle) {...} / пустота /функция deleteNode (/ treeType */ATree, AKeyId) {...}

// -> ОСНОВНЫЕ НАПРАВЛЕНИЯ main();

/* void */function main() { // treeType myTree; myTree = treeType;

// insert root = 0 rootNode = insertNode (myTree, 0, '[PC]');

... }