Tree/Dic
Материал из PhpWiki.
| Деревья в базах данных => | Словарь терминов
Словарь терминов
Вершина
В случае с деревьями в базах данных мы можем сказать, что вершина - это один элемент дерева. Например, в дереве каталогов вершиной является один каталог.
Граф
Это множество вершин и множество дуг (стрелок; в таком случае мы говорим о направленном или ориентированном графе) или ребер (ребро, как и дуга, указывает связь между вершинами, но, в отличие от дуги, не имеет направления; в таком случае мы говорим о неориентированном графе). Графы имеют непосредственное отношение к деревьям, поскольку деревья - это частный вид графов.
Дерево
Дерево - это частный случай ориентированного графа, в котором нет циклов (когда идя по стрелкам мы можем перейти из вершины в саму себя через другие вершины) и для каждой вершины которого есть ровно одна входящая дуга, за исключением корневой вершины, для которой нет ни одной входящей стрелки.
В дереве может быть только одна корневая вершина. Если в дереве несколько корневых вершин, то такое явление правильно называется лес, хотя многие предпочитают говорить "несколько деревьев".
Самым распространенным примером дерева является дерево каталогов на диске. В интернет-программировании в качестве примера дерева можно было бы привести карту сайта http://popoff.donetsk.ua/map.html карту сайта или древообразную структуру разделов новостей http://popoff.donetsk.ua/news/ разделов новостей.
В случае с представлением деревьев в базах данных принято считать, что дерево выглядит примерно так:
На этом рискунке вершина 1 является корневой. Эта же вершина является родительской для всех вершин дерева, и является непосредственным родителем для вершин 2 и 3. Вершины 2 и 3, в свою очередь, являются непосредственными детьми по отношению к вершине 1. Вершины 4,5,6 и 7 образуют поддерево вершины 2.
Родитель
О том, что вершина является родительской (или дочерней) можно говорить, только сравнивая две вершины: вершина А является родительской по отношению к вершине Б или вершина Б является дочерней по отношению к вершине А. Вершина не может быть родительской или дочерней сама по себе.
Если посмотреть на наш пример дерева, то вершина А является родительской по отношению к вершине Б в случае, если вершина А находится выше вершины Б и, переходя по стрелкам, мы можем попасть из вершины А в вершину Б.
Если есть непосредственная стрелка из вершины А в вершину Б, то вершина А называется "непосредственным родителем" вершины Б, а вершина Б - "непосредственным ребенком" вершины А. Обычно этот термин используют, когда хотят отделить непосредственных родителей (или детей) от всех остальных родителей (детей).
Если вершина А является родителем вершины Б, но не является непосредственным родителем вершины Б, то говорят, что вершина А является косвенным родителем (или пра-родителем) вершины Б, а вершина Б - косвенным ребенком (или пра-ребенком) вершины А.
Смотрите так же: Дерево
Ребенок
Вершина А является ребенком вершины Б (или дочерней вершиной по отноношению к вершине Б) в случае, если вершина Б является родителем вершины А.
Корневая вершина
Вершина, у которой нет родителя.
Смотрите так же: Дерево
Брат, Сестра
Вершина А является братом вершины Б в случае, если вершины А и Б имеют общего непосредственного родителя.
Смотрите так же: Уровень
Поддерево
Поддерево для вершины А - это список всех вершин, которые являются дочерними по отношению к вершине А, включая как непосредственных, так и косвенных детей.
Смотрите так же: Дерево
Путь
В общем случае путь от вершины А к вершине Б - это множество вершин (включая или не включая сами А и Б), которые нужно пройти, что бы попасть из вершины А в вершину Б.
При работе с деревьями в базах данных под словом "путь" обычно понимают путь из корневой вершины в заданную.
Иногда вместо слова "путь" говорят "список всех родителей". Это не совсем правильно, потому что путь - это упорядоченный список вершин, в котором родители всегда записаны раньше детей. Если мы хотим сказать "список всех родителей", то, что бы быть точным, нужно добавить "отсортированный по номеру уровня".
Смотрите так же: Уровень
Уровень
Под уровенем обычно понимают список всех непосредственных детей заданной вершины:
Под номером уровня обычно понимают число, определяющее, сколько родителей у вершин этого уровня. У корневой вершины номер уровня - 0, а у выделенных на рисунке вершин номер уровня - 2. Иногда к номеру уровня прибавляют единицу и говорят, что у корневой вершины номер уровня равен 1, а у выделенных вершин номер уровня равен 3.
Чем больше номер уровня, тем ниже находятся вершины в дереве.
Очень часто, когда говорят, что "вершины принадлежат одному уровню", имеют в виду, что у этих вершин есть общий непосредственный родитель. Если хотят сказать, что у вершин одинаковый номер уровня, то так и говорят, что "у вершин одинаковый номер уровня".
Направление (выше, ниже, правее, левее) Когда говорят, что одна вершина находится выше, ниже, правее или левее другой, то имеют в виду именно такое их расположение, как показано на этом рисунке:
Если вершина А находится выше вершины Б, то вершина А является родительской по отношению к вершине Б.
Если вершина Б находится ниже вершины А, то вершина Б является дочерней по отношению к вершине А.
Направления "правее" - "левее" обычно имеют место быть, когда сравниваются братья, хотя в общем случае могут сравниваться не только братья.
Очень часто, когда дерево выводят на экран, вершины, принадлежащие одному уровню, располагают сверху вниз. В таком случае, сравнивая расположение этих вершин, у многих возникает соблазн сказать, что одна вершина находится выше (или ниже) другой. Это не правильно. Вершины, принадлежащие одному уровню могут быть расположены только левее или правее, а если они расположены "выше" или "ниже", то это означает, что одни вершины являются родителями других вершин. Когда мы говорим о позиции элемента в дереве, всегда используется такое расположение, как показано на рисунке. Обычно самые левые вершины располагаются в начале списке (то есть на экране они покажутся в самом верху), а самые правые - в конце списка (то есть на экране они покажуются в самом низу).
Списки смежности
Такой способ представления графов, в котором граф задается списком дуг. В деревьях использование списков смежности означает, что для каждой вершины мы храним пару(id, parent_id) - это фактически и есть дуга от элемента parent_id к элементу id, которая говорит, что элемент id является дочерним по отношению parent_id.
Смотрите так же: | Представление деревьев в базах данных в виде списков смежности
Вложенные множества
Такой способ представления деревьев, в котором для каждой вершины дерева указывается некоторый диапазон чисел. Вершина А является дочерней по отношению к вершине Б в случае, если диапазон вершины А лежит внутри диапазона вершины Б.
При таком способе представления деревьев значительно упрощается формулировка некоторых запросов. Например, выбрать все поддерево можно, выбрав все вершины, у которых диапазоны лежат внутри диапазона родительской вершины, а выбрать все вершины, которые являются родительскими по отношению к данной можно, выбрав все вершины, диапазон которых покрывает диапазон данной вершины.
Ответ на вопрос, почему множества называются вложенными, можно найти на картинке, на которой изображены вложенные объекты:
Круг А является вершиной верхнего уровня. Квадрат Б и овал Д лежат внутри круга А, значит они являются дочерними по отношению к кругу А. Треугольники В и Г лежат внутри квадрата Б. Все фигуры, квадрат, овал и оба треугольника лежат внутри круга А, то есть являются дочерними вершинами по отношению к кругу А.
Смотрите так же: | Представление деревьев в базах данных в виде вложенных множеств
Вложенные интервалы
Вложенные интервалы - это практически то же самое, что и вложенные множества за тем лишь исключением, что во вложенных интервалах объединение диапазонов всех вершин может содержать в себе не использованные промежутки. Во вложенных множествах такие пропуски не допустимы.
Смотрите так же: | Представление деревьев в базах данных в виде вложенных интервалов
Левосторонний обход дерева
Это когда мы обходим все вершины дерева слева направо (если смотреть на дерево в ширину), начиная с корневой вершины:
Сначала стоим в вершине 1, потом идем 2, 4, возвращаемся - 2, дальше - 5, 7, возвращаемся - 5, возвращаемся - 2, и так далее - 6, 2, 1, 3, 1.
На левостороннем обходе построен метод хранения деревьев со Вложенными множествами: когда мы посещаем вершину первый раз - мы присваиваем ей левую метку, а когда посещаем ее последний раз - правую метку.
Материализованный путь
Такой способ представления деревьев в базах данных, при котором для каждой вершины явно указывается список всех родительских вершин.
В реальной жизни Вы часто сталкиваетесь с представлением деревьев в виде материализованных путей. Например, разделы в книге могут нумеровать так: Раздел 1 Подраздел 1.1 Пункт 1.1.1 Пункт 1.1.2 Пункт 1.1.3 Подраздел 1.2 Пункт 1.2.1 Все знают, что в надписи "пункт 1.1.3" первая единица означает номер раздела, вторая единица - это номер подраздела, а тройка - это номер этого пункта в этом подразделе. Вот он, материализованный путь - для пункта явно указан и номер раздела и номер подраздела.
Если бы дерево хранилось в виде списков смежности, то для пункта следовало бы указать только номер подраздела, а номер раздела тогда можно было бы узнать, посмотрев в соответствующий подраздел.
Смотрите так же: | Представление деревьев в базах данных в виде материализованных путей
Английские эквиваленты
Adjacency List - Списки смежности
Child - Ребенок. Описание смотрите в Родитель
Level - Уровень
Materialized Path - Материализованный путь
Nested Sets - Вложенные множества
Nested Intervals - Вложенные интервалы
Parent - Родитель
Sibling - Брат
