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

В настоящее время я разрабатываю иерархию категорий, и я думаю, что у меня есть смысл создать обход дерева. Но мне нужно добавить новый узел в эту иерархию, используя функцию PHP.

Проблема в том, что функция reboot_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, которая эффективна с большими деревьями?


mysql php rebuild tree traversal
person beytarovski    schedule 07.03.2011    source источник
comment
если вы ищете эффективный способ управления большими деревьями, вам лучше переключиться с вложенных наборов на список смежности — explainextended.com/2009/09/24/   -  person Jon Black    schedule 08.03.2011
comment
@foo: хорошая мысль, но по крайней мере 90 могут закрыть дело и выбрать ответ.   -  person Gigamegs    schedule 16.03.2011

Ответы (4)


arrow_upward
2
arrow_downward

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

person Gigamegs    schedule 07.03.2011
comment
Вот как celko делает вставки: ibase.ru/devinfo/DBMSTrees/sqltrees.html - person Jonas Bötel; 07.03.2011

arrow_upward
2
arrow_downward

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

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

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
person umlcat    schedule 07.03.2011
comment
спасибо за ваш ответ, но этот метод, который вы упомянули, мне не нужен - для меня он не лучше и не быстрее - person beytarovski; 07.03.2011
comment
как вы хотите перебирать дерево, которое уже сохранено в таблице? - person umlcat; 08.03.2011
comment
чтобы проверить, как перебирать дерево, проверьте другой ответ, позже в этом же посте - person umlcat; 16.03.2011

arrow_upward
0
arrow_downward

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

person Gigamegs    schedule 07.03.2011

arrow_upward
0
arrow_downward

Мой предыдущий ответ неполный. Это резюме, весь код слишком длинный, чтобы быть в сообщении на форуме. Забыли спросить, процедурный 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, PRIMARY KEY (id));

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

// globar var, действует как тип /* 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; моедерево = тип дерева;

// вставляем root = 0 rootNode = insertNode(myTree, 0, '[PC]');

... }

person umlcat    schedule 08.03.2011