 |
|
Деревья в базах данных => Словарь терминов
Словарь терминов
Вершина
В случае с деревьями в базах данных мы можем сказать, что вершина – это один элемент дерева. Например, в дереве каталогов вершиной является один каталог.
Граф
Это множество вершин и множество дуг (стрелок; в таком случае мы говорим о направленном или ориентированном графе) или ребер (ребро, как и дуга, указывает связь между вершинами, но, в отличие от дуги, не имеет направления; в таком случае мы говорим о неориентированном графе). Графы имеют непосредственное отношение к деревьям, поскольку деревья – это частный вид графов.
Дерево
Дерево – это частный случай ориентированного графа, в котором нет циклов (когда идя по стрелкам мы можем перейти из вершины в саму себя через другие вершины) и для каждой вершины которого есть ровно одна входящая дуга, за исключением корневой вершины, для которой нет ни одной входящей стрелки.
В дереве может быть только одна корневая вершина. Если в дереве несколько корневых вершин, то такое явление правильно называется лес, хотя многие предпочитают говорить «несколько деревьев».
Самым распространенным примером дерева является дерево каталогов на диске. В интернет-программировании в качестве примера дерева можно было бы привести 
карту сайта или древообразную структуру разделов новостей.
В случае с представлением деревьев в базах данных принято считать, что дерево выглядит примерно так:
На этом рискунке вершина 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 – Брат