Шрифт:
Мы подробно разберем каждый из типов узлов чуть позже, а пока отметим, что дерево в XSLT и XPath является чисто концептуальной моделью. Процессоры не обязаны внутренне представлять документы именно в этой структуре, концептуальная модель означает лишь то, что все операции преобразования над документами будут определяться в терминах деревьев. Для программиста же это означает, что вовсе необязательно вникать в тонкости реализации преобразований в том или ином процессоре. Все равно они должны работать, так, как будто они работают непосредственно с деревьями.
Отметим также и то, что на практике некоторые из процессоров вообще не воссоздают внутреннюю модель документа, экономя, таким образом, ресурсы. Документы могут быть слишком объемными, и это препятствует загрузке их в память в виде древовидной структуры.
Некоторые из процессоров, напротив, используют DOM-модель документа для внутреннего представления обрабатываемой информации. Несмотря на большие требования к ресурсам памяти, такое решение также может иметь свои плюсы, например, универсальность и легкая интеграция в существующие XML-решения на базе DOM.
Но, так или иначе, с воссозданием древовидной структуры документа в памяти или нет, процессоры все равно оперируют одной и той же концептуальной моделью, которой мы сейчас и займемся.
Деревья
Прежде, чем мы приступим к рассмотрению типов узлов и отношений между ними, необходимо определиться с самой структурой дерева. Древовидная структура задает для своих элементов отношение ветвления, очень похожее на строение обычного дерева — есть корневой узел (ствол), от которого происходят другие узлы (ветки).
Формально [Кнут 2000] дерево определяется, как конечное множество T, состоящее из одного или нескольких элементов (узлов), обладающих следующими свойствами:
□ во множестве T выделяется единственный узел, называемый корневым узлом или корнем;
□ все остальные узлы разделены на m≥0 непересекающихся множеств T1, …, Tm, каждое из которых в свою очередь также является деревом.
Деревья T1, …, Tm называются поддеревьями корня дерева T.
Это определение является рекурсивным, то есть в нем дерево определяется само через себя. Конечно, существуют нерекурсивные определения, но, пожалуй, следует согласиться с тем, что рекурсивное определение лучше всего отражает суть древовидной структуры: ветки дерева также являются деревьями.
В XSLT и XPath деревья являются упорядоченными, то есть для множеств T1, …, Tm задается порядок следования, который называется порядком просмотра документа. В XSLT деревья упорядочиваются в порядке появления текстового представления их узлов в документах.
Существует множество способов графического изображения деревьев. Мы будем рисовать их так, что корень дерева будет находиться наверху, а поддеревья будут упорядочены слева направо. Такой способ является довольно стандартным для XML, хотя и здесь существует множество вариантов. Примером изображения дерева может быть следующий рисунок (рис. 3.2):
Рис. 3.2. Изображение дерева
Мы часто будем говорить о дочерних узлах, родительских узлах, братских узлах, узлах-предках и узлах-потомках. Дадим определения этим понятиям.
□ Дочерним узлом текущего узла называется любой из корней его поддеревьев. Например, в дереве на рис. 3.2 дочерними узлами узла
□ Каждый узел называется родительским узлом корней своих поддеревьев. На рис. 3.2 узел
□ Корни поддеревьев называются братскими узлами или узлами-братьями. На рис. 3.2 братьями являются узлы
□ Предками текущего узла являются его родитель, а также родители его родителей и так далее. На рис. 3.2 предками узла
□ Потомками текущего узла являются его дочерние узлы, а также дочерние узлы его дочерних узлов и так далее. На рис. 3.2 потомками узла