Данная статья — четвертая в серии. Ссылки на предыдущие статьи: первая, вторая, третья
Структуры данных «деревья»
Для этой структуры дополнительные визуализации не к чему тут все понятно из названия, так же как и живого дерева в структуре есть листья, ветви, корень, но есть нюанс, в отличие от настоящих деревьев в нашей структуре рост происходит сверху вниз: корень обычно рисуется сверху, а листья — внизу, почему так? Потому что программисты так решили)))).
Что нам нужно понять в начале что «деревья» являют нелинейной структурой и данные не хранятся последовательно в отличие от массивов, стеков и очередей, а в виде многоуровневой системы и упорядочивание данных тут происходит иерархически.
Для примера можно вспомнить генеалогическое древо, или вспомним ваш «диск С» в котором есть папки, в которых есть еще папки, аналогично устроена эта структура.
Давайте разбирается в терминах:
Справочник терминов
Узел — это объект, в котором есть значение и указатели на дочерние узлы.
Узлы, у которых есть хотя бы один дочерний узел, называются внутренними.
Корень или Корневой узел – самый верхний узел дерева.
Листы – узлы, у которых нет дочерних узлов.
Внутренний узел – имеет хотя бы один дочерний узел (проще говоря если узел не является листом и корнем значит является внутренним)
Ребро(ветвь) – условная связь между двумя узлами, проще говоря это маршрут, соединяющий одни данные с другими.
Потомок(дочерний) и родитель – узлы, один из которых имеет родительский узел, а второй связан ребром с узлом-потомком.
Фуух.... Непросто
Но продолжим,
· структура данных дерева начинается с корневого узла.
· Каждый узел может разветвляться на дочерние узлы.
· Если дочерних элементов в структуре нет, то мы достигли листа
· Когда деревьев несколько, это называется лесом (что логично).
Есть две важные характеристики дерева, которые нужно знать при работе с ним:
· Высота дерева - максимальное число узлов дерева в цепочке
· Глубина узла - длина самого длинного пути от корня до узла.
Одним из первых возникает вопрос: сколько каждый узел может иметь дочерних элементов?
В большей мере (но не все) деревья имеют не больше двух потомков именно поэтому их называются двоичными деревьями, а потомков - левым и правым дочерними узлами.
Левый или правый дочерние узлы при наличии у них своих потомков мы можем выделить в виде отдельного дерева и получить еще один термин – поддерево.
Для справки: Поддерево приводит нас к умозаключению, что рассматриваемая нами структура является рекурсивной (тесть структура повторяет саму себя в своих частях)
рассмотрим ТИПЫ деревьев(в каждом оставлю ссылочку для более детального изучения:
В чём преимущество деревьев?
А вот преимущество деревьев перед ранее рассмотренными линейными структурами в том, что, несмотря на относительную сложность их формирования, все операции, проводимые с ними, являются очень простыми. Операции вставки, поиска и удаления элементов в дереве выполняются в тысячи раз быстрее чем аналогичные операции с массивом. Во многих случаях именно благодаря использованию древовидных структур при работе с данными удаётся достаточно заметно ускорить работу.
Это простые, фундаментальные и очень полезные структуры данных. За несколько секунд в поисковике вы можете найти тысячи реализаций деревьев.