MyPHP - уроци по PHP
Урок 18
С човека се случва същото, както с дървото. Колкото повече се стреми нагоре, към светлината, толкова по-дълбоко корените му отиват в земята, надолу, в тъмнината и дълбочината - към злото. Фридрих Ницше
Днешният урок ще бъде посветен на изграждането на така наречените дървета с данни. Този елемент често се използва в уеб програмирането и е от съществено значение за приложения като директории на сайтове, многостепенни форуми и други скриптове, които съхраняват данни по такъв начин, че всеки елемент е вложен в друг.
Всеки, който се е занимавал с компютър знае за дърветата. Например, това е файловата система на операционната система.
Графично дървото може да бъде представено по следния начин:
Нивото на гнездене и дължината на дървото не са ограничени.
Създаване на дървета.
Има няколко алгоритъма за конструиране на дървета. Нека започнем с най-често срещания метод, който е ефективен при създаване на дървета с малка дълбочина на гнездене.
Методът е, че всеки дъщерен елемент съхранява данни за своя непосредствен родител, тоест, като се има предвид схемата по-горе, елементи 2 и 5 съдържат препратка към елемент 1, а 3 и 4 съдържат препратка към елемент 2.
Заявка за създаване на таблица, която ще съхранява данни според горния алгоритъм, може да изглежда така:
Нека вмъкнем няколко записа в получената таблица:
| // функция за вмъкване на записи в MySQL function sql_insert($parent_id, $cat_name) $query = "INSERT INTO catalogs(parent_id, cat_name) VALUES('".(int)$parent_id."', '$cat_name')"; mysql_query($query) или die(mysql_error()); върни mysql_insert_id(); // връща идентификатора на въведения запис > // изборът на връзка и база данни няма да се разглежда $level[1][0] = sql_insert("0","Програмиране"); $level[2][0] = sql_insert($level[1][0], "Уеб разработка"); $level[2][1] = sql_insert($level[1][0], "Системно програмиране"); $level[3][0] = sql_insert($level[2][0], "PHP"); $level[3][1] = sql_insert($level[2][0], "Perl"); $level[3][2] = sql_insert($level[2][1], "C++"); $level[4][0] = sql_insert($level[3][2], "Visual C++"); $level[3][3] = sql_insert($level[2][1], "Delphi"); |
// Второ разклонение $level[1][1] = sql_insert("0", "Бази данни"); $level[2][2] = sql_insert($level[1][1], "MySQL"); $level[2][3] = sql_insert($level[1][1], "Oracle"); $level[2][4] = sql_insert($level[1][1], "MS Access");
Сега нека покажем полученото дърво:
Тъй като имаме дърво на много нива, трябва да извикаме функцията get_tree () рекурсивно, за дървета на едно ниво (не повече от едно ниво на влагане) това не е необходимо.
Както можете да видите, алгоритъмът за изграждане на такива дървета е много прост.
Предимствата на този метод за изграждане на дървета включват факта, че всеки елемент от дървото има достатъчна степен на изолация, тъй като е свързан с родителя чрез стойността само на едно поле, което можем лесно да променим и по този начин елементарно да променим родителя. Недостатъците са изключително неудобната работа при високи нива на гнездене. Така че този алгоритъм е най-подходящ за дървета с едно ниво и дървета с ниско ниво на влагане (2 - 3 нива).
Алгоритъм Вложени набори.
Алгоритъмът за вложени набори е по-мощен инструмент за работа с дървета. Можете да изтеглите класа за работа с него от тук. Архивът се състои от два файла: dbtree.php - всъщност клас за работа с дървета и database.php - клас за работа с база данни. Във втория файл можете да добавитевашите функции за работа с MySQL и го персонализирайте за себе си по всеки възможен начин, просто не променяйте функциите, използвани от класа във файла dbtree.php.
Алгоритъмът на Nested Sets може да изглежда сложен на пръв поглед, но всъщност е изключително прост. Същността му се състои в това, че той не съхранява идентификатора на родителския елемент, а използва три допълнителни полета: cat_left, cat_right и cat_level (можете да промените имената на полетата). Той ги използва по следния начин.
Представете си, че малко човече върви по нашето дърво с данни със знамена в ръце, а надписите върху тях са последователни числа. Преминавайки през елемент от дървото, човечецът поставя флагче с цифра върху него, започвайки от първия, стига до самата дълбочина на клона и се връща обратно, за да отиде на друг клон, но в същото време продължава да поставя флагчета върху вече преминатите елементи.
Нека видим как нашият малък човек поставя флаговете в дървовидната диаграма от началото на урока (сините флагове са маркирани при първото преминаване на елемента, зелените - при връщане от клона).
Стойностите на сините флагове в таблицата MySQL се съхраняват в полето cat_left, а зелените - в полето cat_right, нивото на влагане - в полето cat_level.
Нека създадем таблица с дърво, подобно на това по-горе.
Използването на полетата cat_left и cat_right ви позволява да манипулирате дървото в почти всички посоки. Например, забележете, че елементите, които нямат деца, имат стойности за тези полета, които се различават с единица. И потомците на всеки даден елемент имат стойности cat_left по-големи от стойността на избрания родител, а cat_right - по-малко, и колкото по-голям е клонът на потомците, толкова по-голяма е разликата между стойностите на cat_right и cat_left за този родител (сравнете "Уеб програмиране" и "Бази данни"). Въз основа на тези данни ще направим селекция на всички елементи, неимащи родители, както и всички наследници на елемента "Системно програмиране":
Това приключва нашия урок. До следващия път!