Урок 18. Деревья.
С человеком происходит то же, что и с деревом.
Чем больше
стремится он вверх, к свету, тем глубже
уходят корни его в землю, вниз, в
мрак и глубину - ко злу.
Фридрих Ницше
Сегодняшний урок будет посвящен построению так называемых деревьев данных.
Этот элемент часто используется в вебпрограммировании и просто необходим для
таких приложений, как каталоги сайтов, многоуровневых форумов и других скриптов,
в которых данные хранятся таким образом, что каждый элемент вложен в другой.
Все, кто имел дело с компьютером, имеют представление о деревьях. Например,
это файловая система операционной системы.
Графически дерево можно представить следующим образом: элемент 1
|
+ - элемент 2
| |
| + - элемент 3
| + - элемент 4
|
+ - элемент 5
Уровень вложенности и длина дерева не ограничены.
Создание деревьев.
Существует несколько алгоритмов построения деревьев. Начнем с наиболее
распространенного метода, который эффективен при создании деревьев с небольшой
глубиной вложенности.
Метод заключается в том, что в каждом дочернем элементе сохраняются данные о
его непосредственном родителе, то есть, рассматривая схему выше, элементы 2 и 5
содержат ссылку на элемент 1, а 3 и 4 - на элемент 2.
Запрос на создание таблицы, в которой будут храниться данные по
вышеуказанному алгоритму, может выглядеть следующим образом:
CREATE TABLE catalogs (
cat_id int(11) NOT NULL auto_increment,
parent_id int(11) NOT NULL default '0',
cat_name varchar(200) NOT NULL default '',
PRIMARY KEY (cat_id)
) |
Вставим в полученную таблицу несколько записей:
// функция для вставки записей в 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) or
die(mysql_error());
return mysql_insert_id(); //
возвращаем 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");
|
Теперь выведем полученное дерево:
function get_tree($parent_id = 0, $prefix = "") {
global $out;
$query = "SELECT * FROM catalogs WHERE parent_id = '$parent_id'";
$result = mysql_query($query);
while ($row = mysql_fetch_array($result)) {
$out .= $prefix.$row['cat_name']."<br>";
get_tree($row['cat_id'], $prefix." ");
}
return $out;
}
echo get_tree(); |
Так как мы имеем многоуровневое дерево, функцию get_tree() нам
приходся вызывать рекурсивно, для одноуровневых деревьев (не больше одного
уровня вложенности) этого не требуется.
Как видите, алгоритм построения такого рода деревьев очень прост.
К достоинствам данного метода построения деревьев можно отнести то, что
каждый элемент дерева обладает достаточной степенью обособленности, так как с
родителем его связывает значение только одного поля, которое мы без проблем
можем изменить и элементарно поменять тем самым родителя. К недостаткам же -
крайне неудобную работу при высоких уровнях вложенности. Так что этот алгоритм
оптимально подходит для одноуровневых деревьев и деревьев с невысоким уровем
вложенности (2 - 3 уровня).
Алгоритм Nested Sets.
Алгоритм Nested Sets - более мощный инструмент работы с деревьями. Класс для
работы с ним вы можете скачать здесь.
Архив состоит из двух файлов: dbtree.php - собственно, класс для работы с
деревьями, и database.php - класс для работы с базой данных. Во второй файл вы
можете добавить свои функции работы с MySQL и всячески подстраивать для себя,
только не изменяйте функции, используемые классом в файле dbtree.php.
Алгоритм Nested Sets с первого взгляда может показаться сложным, но на самом
деле он предельно прост. Суть его заключается в том, что он не сохраняет id
родительского элемента, а использует три дополнительных поля: cat_left,
cat_right и cat_level (имена полей вы можете изменить). Использует он их
следующим образом.
Представьте, что по нашему дереву данных шагает человечек с флажками в руках,
причем надписями на них служат подряд идущие цифры. Проходя элемент дерева,
человечек ставит на него флажок с номером, начиная с первого, доходит до самой
глубины ветки и возвращается обратно, чтобы перейти к другой ветке, но при этом
продолжает ставить флажки на уже пройденных элементах.
Посмотрим, как поставит флажки наш человечек в схеме дерева из начала урока
(синим отмечены флажки, поставленные при первом проходе элемента, зеленым - при
возвращении из ветки). элемент 1 [1] [10]
|
+ - элемент 2 [2] [7]
| |
| + - элемент 3 [3] [4]
| + - элемент 4 [5] [6]
|
+ - элемент 5 [8] [9]
Значения синих флажков в таблице MySQL запоминаются в поле cat_left, а
зеленых - в поле cat_right, уровень вложенности - в поле cat_level.
Создадим таблицу с деревом, подобному указанному выше.
include("dbtree.php");
include("database.php");
$db = new CDatabase("your_database_name", "localhost", "root", "12345");
$tree = new CDBTree ($db, "catalogs2", "cat_id");
// создаем таблицу
$query="CREATE TABLE catalogs2(
cat_id int not null auto_increment primary key,
cat_left int not null,
cat_right int not null,
cat_level int not null,
cat_name varchar(200) not null)";
$db->query($query);
// заполняем таблицу
// создаем корневой элемент
$level[0][0]=$tree->clear();
// записываем основную часть дерева
$level[1][0] = $tree->insert($level[0][0], array("cat_name"=>"Программирование"));
$level[1][1] = $tree->insert($level[0][0], array("cat_name"=>"Базы данных"));
$level[2][0] = $tree->insert($level[1][0],
array("cat_name"=>"Веб программирование"));
$level[2][1] = $tree->insert($level[1][0],
array("cat_name"=>"Системное программирование"));
$level[2][2] = $tree->insert($level[1][1], array("cat_name"=>"MySQL"));
$level[2][3] = $tree->insert($level[1][1], array("cat_name"=>"Oracle"));
$level[2][4] = $tree->insert($level[1][1], array("cat_name"=>"MS Access"));
$level[3][0] = $tree->insert($level[2][0], array("cat_name"=>"PHP"));
$level[3][1] = $tree->insert($level[2][0], array("cat_name"=>"Perl"));
$level[3][2] = $tree->insert($level[2][1], array("cat_name"=>"C++"));
$level[3][3] = $tree->insert($level[2][1], array("cat_name"=>"Delphi"));
$level[4][0] = $tree->insert($level[3][2], array("cat_name"=>"Visual C++"));
// Выводим дерево
$query = "SELECT * FROM catalogs2 ORDER BY cat_left";
$result = $db->query($query);
while ($row = $db->fetch_array($result)){
echo str_repeat(" ", $row['cat_level']).$row['cat_name'].
" <font color='#0033FF'>[".$row['cat_left']."]</font>".
" <font color='#009900'>[".$row['cat_right']."]</font><br>";
} |
Использование полей cat_left и cat_right позволяет манипулировать деревом
практически во всех направлениях. Например, заметьте, что у элементов, не
имеющих потомков, значения этих полей отличаются на единицу. А у потомков
какого-либо данного элемента значения cat_left больше значения у выбранного
родителя, а cat_right - меньше, причем, чем больше ветвь потомков, тем больше
разность между значениями cat_right и cat_left у данного родителя (сравните "Веб
программирование" и "Базы данных"). Основываясь на этих данных, сделаем выборку
всех элементов, не имеющих родителей, а также всех потомков элемента "Системное
программирование":
$query = "SELECT cat_left, cat_right FROM catalogs2 ".
"WHERE cat_name = 'Системное программирование'";
$result = $db->query($query);
$val = $db->fetch_array($result);
$query = "SELECT * FROM catalogs2 WHERE cat_left > '".$val['cat_left'].
"' AND cat_right < '".$val['cat_right']."' ORDER BY cat_left";
$result = $db->query($query);
echo "<b>Ветка 'Системное программирование'</b><br>";
while ($row = $db->fetch_array($result)) {
echo str_repeat(" ", $row['cat_level']).
$row['cat_name']."<br>";
}
echo "<b>Все элементы, не имеющие потомков</b><br>";
$query = "SELECT * FROM catalogs2 WHERE cat_right - cat_left = 1";
$result = $db->query($query);
while ($row = $db->fetch_array($result)) {
echo $row['cat_name']." ( ".$row['cat_id']." )<br>";
} |
Возможности этого класса вышеуказанным не ограничиваются. Можно логически
домыслить, как найти всех родителей данного элемента, заканчивая корневым (что
удобно при создании навигации по разделам), а также множество других
возможностей. Настоятельно рекомендую перед использованием данного класса
просмотреть в файле dbtree.php все комментарии перед методами класса, так как
вышеприведенными методами этот класс не ограничивается.
На этом и заканчиваем наш урок. До встречи на следующем!
|
