Дерево — одна из наиболее широко распространённых структур данных в информатике, эмулирующая древовидную структуру в виде набора связанных узлов. Является связным графом, не содержащим циклы. Большинство источников также добавляют условие на то, что рёбра графа не должны быть ориентированными. В дополнение к этим трём ограничениям, в некоторых источниках указывается, что рёбра графа не должны быть взвешенными.
Содержание
Определения [ править | править код ]
- Корневой узел — самый верхний узел дерева (узел 8 на примере).
- Корень — одна из вершин, по желанию наблюдателя.
- лист, листовой или терминальныйузел — узел, не имеющий дочерних элементов (узлы 1, 4, 7, 13).
- Внутренний узел — любой узел дерева, имеющий потомков, и таким образом, не являющийся листовым узлом (3, 6, 10, 14).
Дерево считается ориентированным, если в корень не заходит ни одно ребро.
- Полный сцепленный ключ — идентификатор записи, который образуется путём конкатенации всех ключей экземпляров родительских записей (групп).
Узлы [ править | править код ]
Узел является экземпляром одного из двух типов элементов графа, соответствующим объекту некоторой фиксированной природы. Узел может содержать значение, состояние или представление отдельной информационной структуры или самого дерева. Каждый узел дерева имеет ноль или более узлов-потомков, которые располагаются ниже по дереву (по соглашению, деревья ‘растут’ вниз, а не вверх, как это происходит с настоящими деревьями). Узел, имеющий потомка, называется узлом-родителем относительно своего потомка (или узлом-предшественником, или старшим). Каждый узел имеет не больше одного предка. Высота узла — это максимальная длина нисходящего пути от этого узла к самому нижнему узлу (краевому узлу), называемому листом. Высота корневого узла равна высоте всего дерева. Глубина вложенности узла равна длине пути до корневого узла.
Корневые узлы [ править | править код ]
Узел, не имеющий предков (самый верхний), называется корневым узлом. Это узел, на котором начинается выполнение большинства операций над деревом (хотя некоторые алгоритмы начинают выполнение с «листов» и выполняются, пока не достигнут корня). Все прочие узлы могут быть достигнуты путём перехода от корневого узла по рёбрам (или ссылкам). (Согласно формальному определению, каждый подобный путь должен быть уникальным). В диаграммах он обычно изображается на самой вершине. В некоторых деревьях, например, кучах, корневой узел обладает особыми свойствами. Каждый узел дерева можно рассматривать как корневой узел поддерева, «растущего» из этого узла.
Поддеревья [ править | править код ]
Поддерево — часть древообразной структуры данных, которая может быть представлена в виде отдельного дерева. Любой узел дерева T вместе со всеми его узлами-потомками является поддеревом дерева T. Для любого узла поддерева либо должен быть путь в корневой узел этого поддерева, либо сам узел должен являться корневым. То есть поддерево связано с корневым узлом целым деревом, а отношения поддерева со всеми прочими узлами определяются через понятие соответствующее поддерево (по аналогии с термином «соответствующее подмножество»).
Упорядочивание деревьев [ править | править код ]
Существует два основных типа деревьев. В рекурсивном дереве или неупорядоченном дереве имеет значение лишь структура самого дерева без учёта порядка потомков для каждого узла. Дерево, в котором задан порядок (например, каждому ребру, ведущему к потомку, присвоены различные натуральные числа) называется деревом с именованными рёбрами или упорядоченным деревом со структурой данных, заданной перед именованием и называемой структурой данных упорядоченного дерева.
Упорядоченные деревья являются наиболее распространёнными среди древовидных структур. Двоичное дерево поиска — одно из разновидностей упорядоченного дерева.
Представление деревьев [ править | править код ]
Существует множество различных способов представления деревьев. Наиболее общий способ представления изображает узлы как записи, расположенные в динамически выделяемой памяти с указателями на своих потомков, предков (или и тех и других), или как элементы массива, связанные между собой отношениями, определёнными их позициями в массиве (например, двоичная куча).
Деревья как графы [ править | править код ]
В теории графов дерево — связный ациклический граф. Корневое дерево — это граф с вершиной, выделенной в качестве корневой. В этом случае любые две вершины, связанные ребром, наследуют отношения «родитель-потомок». Несвязный граф, состоящий исключительно из деревьев, называется лесом.
Методы обхода [ править | править код ]
Пошаговый перебор элементов дерева по связям между узлами-предками и узлами-потомками называется обходом дерева. Зачастую операция может быть выполнена переходом указателя по отдельным узлам. Обход, при котором каждый узел-предок просматривается прежде его потомков, называется предупорядоченным обходом или обходом в прямом порядке (pre-order walk), а когда просматриваются сначала потомки, а потом предки, то обход называется поступорядоченным обходом или обходом в обратном порядке (post-order walk). Существует также симметричный обход, при котором посещается сначала левое поддерево, затем узел, затем — правое поддерево, и обход в ширину, при котором узлы посещаются уровень за уровнем (N-й уровень дерева — множество узлов с высотой N). Каждый уровень обходится слева направо.
Все настройки сгруппированы на вкладках Содержимое , Вид и Персоны окна настройки дерева.
Содержимое дерева
На вкладке Содержимое можно настроить набор родственников, отображаемых в родословном дереве, настроить отображение некровных (по отношению к корню дерева) супругов, установить режим отображения приёмных детей и родителей, а также их кровных родственников: 
Например, в дереве Прямые предки и потомки вы увидите только непосредственных предков и потомков корня дерева. Корень дерева можно менять!
Если поставить галочку Супруги , то в дереве прямых предков и потомков вы увидите ещё и супругов прямых потомков, хотя они не являются прямыми потомками корня дерева, а также увидите супругов предков, которые не являются прямыми предками (при наличии нескольких браков у предка). Аналогично в дереве кровных родственников: с галочкой Супруги в дерево будут добавлены также супруги кровных родственников.
Нет приёмных детей прячет приёмных детей. Если выбрано Приёмные дети как родные , то в дереве кровных родственников корня дерева будут также кровные родственники приемных детей. Аналогично с приёмными родителями: если выбрать Приёмные родители как родные , то в дереве кровных родственников корня дерева будут кровные родственники приёмных родителей.
Для ограничения набора отображаемых в генеалогическом дереве родственников можно использовать фильтры: при включённой опции С учётом фильтров таблицы персон в дереве будут отображены только персоны, удовлетворяющие условиям активных фильтров таблицы персон. Опция Прерывать на персоне, не отвечающей условиям позволяет настроить, будет ли продолжена ветвь дерева, если встретилась персона, которая не удовлетворяет условиям фильтров. При выключенной опции такая персона будет отображена в древе пустым прямоугольником и ветвь будет продолжена.
Можно указать текст заголовка дерева и подписи под деревом , их шрифты настраиваются на вкладке Вид .
Опции Статистика и Статистика по поколениям позволяют отобразить в дереве статистику по родословному дереву в целом и отдельную статистику по каждому поколению дерева.
При включённой опции Каждое дерево в отдельной вкладке при построении родословного дерева предоставляется выбор, построить его в текущей вкладке (если дерево уже было построено) или в новой вкладке. Это может пригодиться, например, для сравнения родословных деревьев разных семей, или для выбора наилучшего вида вашего дерева — вид дерева на каждой вкладке настраивается отдельно.
При включённой опции Обновлять автоматически дерево обновляется автоматически при создании, редактировании и удалении персоны в древе — все изменения на вкладке Дерево отображаются сразу. Если нужно внести несколько изменений именно на вкладке Дерево , а перестроение дерева занимает продолжительное время, то можно отключить автоматическое обновление.
Вид дерева
Вкладка Вид содержит опции для настройки внешнего вида родословного древа. Совокупность настроек вида дерева и вида и содержимого узлов дерева называется стилем дерева. Сохранить текущий стиль и загрузить сохранённый или один из стандартных стилей можно с помощью кнопок Загрузить стиль и Сохранить стиль , которые расположены справа над деревом-примером.
В левом верхнем углу расположен выпадающий список выбора направления ветвей (направления роста) семейного дерева, предки могут располагаться внизу или вверху (вертикальное дерево), слева или справа (горизонтальное дерево): 
При включённой опции Оптимизировать положение супругов супруги, если это возможно, располагаются друг над другом.
При включённой опции Отмечать умерших в левом верхнем углу узлов умерших персон ставится отметка – чёрная ленточка.
В сложных деревьях некоторые ветви не могут быть отображены в месте расположения персоны, от которой они начинаются. В этих случаях персона и соответствующая ветвь переносятся влево или вправо от исходного места. Если опция Выносить ветви в ближайшую сторону включена, то направление выноса определяется по расстоянию: ветвь выносится на тот край дерева, до которого ближе. Если эта опция выключена, то ветви персон, относящихся в поддереву отца корня дерева выносятся влево, а ветви персон, относящихся к поддереву матери корня дерева – вправо.
Расстояния между узлами одной ветви, между ветвями и между поколениями , а также толщина линий указываются в пикселах.
Линии в дереве могут быть одного цвета или разноцветными , в последнем случае программа автоматически устанавливает цвета линий таким образом, чтобы соседние параллельные линии были разных цветов, это улучшает читаемость дерева.
Дерево может быть без фона , с двухцветным фоном (два цвета фона, для чётных и нечётных поколений ) или с фоновым изображением . Для дерева с фоновым изображением опция Сохранять пропорции позволяет растянуть фоновое изображение на всё дерево (опция выключена) или сохранить пропорции фонового изображения (опция включена).
Устанавливается шрифт заголовка дерева и шрифт подписей (подпись под деревом, статистика).
Корень дерева (т.е. узел персоны, чьё дерево построено) выделяется отдельным цветом при включённой опции Выделять корень цветом .
Персоны дерева
На этой вкладке расположены настройки вида и содержимого узлов генеалогического дерева. В левом верхнем углу находится выпадающий список, позволяющий установить, к какому типу узлов относятся настройки: ко всем персонам дерева, к кровным родственникам корня дерева, к прямым родственникам корня дерева, к родителям и детям корня или к самому корню: 
На вкладке Поля данных устанавливается список полей данных, отображаемых в узле дерева. Для каждого поля можно установить перенос по словам, жирный или наклонный шрифт, префикс и суффикс поля (например, круглые скобки для дат жизни), а также для каких персон это поле будет отображаться: мужчины или женщины, живые или умершие: 
Для полей Название отношения родства , Браки и Комментарий доступна опция Сокращать , которая позволяет отображать краткое значение в данном поле.
На вкладке Графика находятся настройки размеров и цвета узла дерева, цвета и толщины рамки узла:
На вкладке Текст можно настроить шрифт, выравнивание, отступ и интервал текста узла, установить обтекание текстом фото, включить выделение фаворитов жирным шрифтом:
На вкладке Фото находятся настройки фотографии, отображаемой в узле дерева. Можно установить выравнивание и размеры фото, включить отображение контура, если фотографии нет:
Со старых, пожелтевших фотоснимков смотрят на нас красивые и умные лица — лица наших предков. Но уже спустя два – три поколения мы забываем, кто эти люди, кем они нам приходятся, что значат в нашей жизни. Чтобы не потерять связь поколений, важно научиться правильно работать со своей родословной.
Небольшое вступление: полезная привычка — записывать
Память рода – это не только фотографии, так можно сказать про любую бережно хранимую фамильную вещицу. Старинный угольный самовар на современном столе смотрится… приятно. Но совсем другое дело, если за историей самовара стоят живые истории предков! Поэтому есть смысл завести привычку: записывать рассказы бабушек и дедушек, мам и пап, прабабушек и прадедушек, дядюшек и тетушек. Правнуки могут и не успеть лично познакомиться с прадедами. Но молодое поколение всё равно сможет узнать их, если сохранились аудио или видеозаписи, на которых родственники остаются живыми и здоровыми, рассказывающими о своей жизни.
Создаём основу родословной
Именно так, в живом общении, записывают информацию профессиональные этнографы. А как создать ту самую основу, на которую можно надеть одежды устных рассказов, семейных преданий? Где взять информацию, узнать точные даты, имена и должности? Ответ прост – в архивах, а помощь можно найти в социальных сетях, где активно работает множество групп любителей генеалогии.
Как нарисовать генеалогическое древо
У начинающих исследователей возможны трудности, связанные с графически правильным оформлением информации. Поэтому сегодня коснёмся именно этой темы.
Прежде всего, определитесь, кто будет «конечным потребителем» информации. С психологической точки зрения, важно начинать знакомить ребенка с вопросами его родословной с самого раннего детства, детсадовского и даже ясельного возраста, постепенно меняя форму подачи информации.
Именно для ребенка дошкольного или младшего школьного возраста больше подойдёт «художественный» вариант родословного древа, когда рисуется настоящее дерево, настоящие листочки на его ветвях. Впрочем, не обязательно рисовать — варианты оформления зависят от индивидуальных вкусов, творческих предпочтений и фантазии, можно скачать из сети и готовый шаблон.
” Но вот тут возникает проблема – большинство схем генеалогических дерев не верны!
Например, посмотрите вот на такую схему, которую мы нашли в Интернете
Внешне она выглядит понятной для ребенка, но даже малыш может задать логичный вопрос: «Почему я – корень, а из меня растут ветви «мама» и «папа»? Ведь на самом деле все наоборот!»
” Действительно, наоборот! Общая закономерность построения родословных дерев состоит в том, что в корнях изображают первых из известных нам предков, самых далеких по времени от нас.
Генеалогическое древо английской королевы Виктории
” Другое правило научной генеалогии — деревья строятся по мужской линии.
К примеру, дети женщин, вышедших замуж, изображаются на дереве их отца, то есть мужа этой женщины, на родословном древе родительской семьи этой женщины они не отмечаются.
Важно: именно по мужской линии в нашей традиции строятся все виды фиксации родословия: и родословные схемы, и поколенные росписи, и уже описанные родословные деревья. Остальное в оформлении родословного древа – дело творчества.
” На родословном древе про каждого человека следует написать фамилию, имя, отчество, дату рождения и смерти, если человека уже нет в живых.
Как построить родословную схему
Принцип построения родословной схемы в общих чертах напоминает работу с генеалогическим древом. Творчества, естественно, меньше, — нет живописности, художественности родословного древа.
” А вот с точки зрения пространственной организации информации есть важные отличия: родословное древо строится обязательно снизу вверх, а схема может быть восходящей (снизу вверх), нисходящей (сверху вниз) и даже боковой (слева направо).
Поколенная роспись
На мой взгляд, для взрослого человека, ведущего родословные изыскания, наиболее удобная форма фиксации новой информации — поколенная роспись. Для подростков умение составлять поколенные росписи может стать ещё и ярким дополнением к курсу истории России.
Итак, поколенная роспись привлекательна именно тем, что позволяет совершенно безболезненно вносить дополнения про любого человека, не нарушая структуры и оформления. Другое её преимущество в том, что именно поколенная роспись позволяет записывать абсолютно любую имеющуюся информацию о человеке. Стандартизация в ней касается лишь структуры расположения родственников.
Поясню это на примере – фрагменте поколенной росписи Захаровых.
Аппетит приходит во время еды. Вполне возможно, занявшись этим летом вместе с ребёнком составлением генеалогического дерева или поколенной росписи, вы захотите задать свои вопросы. В Новосибирске с 1994 года существует общественная организация – Новосибирское историко-родословное общество, объединяющее единомышленников и оказывающее методическую помощь при составлении родословной. Общество представлено группой в социальной сети ВКонтакте >>>>
Интересно? Оставьте ссылку на эту статью в социальных сетях!