Модифицированный прямой обход дерева.
Рассмотрим один из методов хранения деревьев. Как правило деревья приходится доставать рекурсивно, что может быть медленно, поэтому рассматривать этот метод не будем. Очень хотелось бы свести к миниму количество запросов к БД, а в идеале к одному запросу:)
Пройдем по нашему дереву горизонтально. Начнем с корня ('Food') и допишем 1
слева. Следующий узел 'Fruit', напишем рядом 2. Таким образом, мы будем ходить вдоль краев дерева и дописывать числа слева и справа каждого узла. Последним, будет номер,
справа узла 'Food'. Ниже можно посмотреть на наше пронумерованное дерево со стрелками, указывающими направление обхода.
Мы назовем эти цифры
левой и
правой (например,
левое значение 'Food' — 1,
правое — 18). Как видите, эти цифры определяют связь между узлами дерева. Посколькоу 'Red' имеет цифры 3 и 6, он является потомком вершины 1-18 'Food'. В то же время, мы можем сказать, что все вершины у которых левые значения больше 2, а правые меньше 11 являются потомками 2-11 'Fruit'. Таким образом, структура дерева хранится в в
левом и
правом значениях вершины. Этот метод кругового обхода дерева и подсчета вершин называется '
модифицированный прямой обход дерева'.
Прежде чем продолжить, давайте посмотрим, как это будет храниться у нас в БД:
Слова 'left' и 'right' являются зарезервированными в MySql, поэтому для обозначения столбцов в таблице стоит выбрать другие имена, например, 'lft' и 'rgt' или брать в обратные кавычки. Так же, стоит обратить внимание на то, что нам больше не нужен столбец 'parent'. У нас имеются
lft и
rgt значения для хранения древовидной структуры.
Получение дерева
Если нам необходимо получить дерево, использующее таблицу с
левыми и
правыми значениями, то нам для начала нужно будет определиться с узлами, которые нам необходимы. Например, если нам нужен узел 'Fruit' со всеми своими детьми, нам будет достаточно выбрать записи с
левыми значениями от 2 до 11.
В таком случае SQL запрос может выглядеть так:
SELECT * FROM tree WHERE lft BETWEEN 2 AND 11;
В результате мы получим:
Все дерево одним запросом. Для того что бы отобразить дерево упорядоченным, как делала это рекурсивная функция добавим в запрос ORDER BY. Если добавлять и удалять записи в таблице, то их порядок нарушится. Поэтому зададим сортировку по
левым значениям.
SELECT * FROM tree WHERE lft BETWEEN 2 AND 11 ORDER BY lft ASC;
Единственной проблемой остаются отступы узлов для красивого отображения дерева, т.е. дети должны иметь отступ по отношению к родителю.
Для этого мы будем использовать
правые значения наших вершин. Каждый раз, когда мы будем начинать узел с детьми,
правое значение это узла мы будем писать в
стэк.
You know that all children of that node have a right value that is less than the right value of the parent, so by comparing the right value of the current node with the last right node in the stack, you can see if you're still displaying the children of that parent. Вы знаете, что все дети, что узел имеет право ценность, которая является меньше, чем стоимость права родителей, так что, сравнив права значение текущего узла с последним право узла в стек, можно увидеть, если вы все еще выводить детей этого родителя.
Мы знаем, что все дети имеют
правое значение, которое меньше, чем у их родителя, так, сравнивая
правое значение текущего узла с последним значением в
стэке, можно определять выводить ли детей этого родителя. По окончании отображения узла, удаляем его
правое значение из стека. Если же посчитать количество элементов в
стэке, то плоучим уровень вложенности текущего узла.
<?php
function display_tree($root) {
// retrieve the left and right value of the $root node
$result = mysql_query('SELECT lft, rgt FROM tree '.
'WHERE title="'.$root.'";');
$row = mysql_fetch_array($result);
// start with an empty $right stack
$right = array();
// now, retrieve all descendants of the $root node
$result = mysql_query('SELECT title, lft, rgt FROM tree '.
'WHERE lft BETWEEN '.$row['lft'].' AND '.
$row['rgt'].' ORDER BY lft ASC;');
// display each row
while ($row = mysql_fetch_array($result)) {
// only check stack if there is one
if (count($right)>0) {
// check if we should remove a node from the stack
while ($right[count($right)-1]<$row['rgt']) {
array_pop($right);
}
}
// display indented node title
echo str_repeat(' ',count($right)).$row['title']."\n";
// add this node to the stack
$right[] = $row['rgt'];
}
}
?>
Если запустить этот код, то получим дерево, которое мы получали раньше при помощи рекурсии. Функция получилась на много проще, как если бы писалась рекурсивно и использует только 2 запроса для построения дерева.
Путь к узлу
С этим новым алгоритмом, мы также должны найти новые пути, чтобы получить путь к определенному узлу. Чтобы получить этот путь, нам понадобится список всех предков этого узла. С нашей новой структурой таблицы работы будет не так и много. Если посмотреть, например, на узел 4-5 'Cherry', можно увидеть, что все
левые значения предков меньше 4, а все
правые — больше 5.
Чтобы получить всех предков, построим следующий запрос:
SELECT title FROM tree WHERE lft < 4 AND rgt > 5 ORDER BY lft ASC;
Как и в предыдущем запросе, мы должны использовать ORDER BY для сортировки узлов.
Запрос вернет:
+-------+
| title |
+-------+
| Food |
| Fruit |
| Red |
+-------+
Сейчас мы только объединили записи для получения пути к 'Cherry'.
Подсчет потомков
Если вы дадите мне
правое и
левое значемя узла, то я скажу вам, сколько он имеет потомков, используя немного математики.
Каждый потомок инкрементирует
правое значение узла начиная с 2, тогда количество потомков расчитывается по формуле:
$descendants = ($right – $left - 1) / 2;
Исходя из этой простой формулы можно сказать, что 2-11 'Fruit' имеет 4 потомка и что 8-9 'Banana' просто чаилд и не родитель.
Добрый день, уважаемые читатели.