Наиболее простой и понятной структурой данных является обычный массив. С тем, как устроены массивы, редко возникают вопросы. Чего нельзя сказать о такой структуре данных, как деревья. Предлагаем разобраться с деревьями - нелинейной структурой, где данные упорядочиваются иерархически.
Немного об иерархии
Пожалуй, один из примеров иерархий, с которым многие сталкиваются каждый день, являются каталоги в операционной системе. В вашем компьютере всегда есть корневой каталог, будь то корневой каталог на Linux или, например, локальный диск на Windows. В каждом из этих корневых каталогов находятся папки, внутри которых так же есть папки, внутри которых тоже могут быть папки, таким образом, это может продолжаться практически до бесконечности. Хотя так было не всегда, и длина пути в Windows по умолчанию ограничена 260 символами. Пример каталога можно увидеть на картинке ниже.
Приложив чуточку воображения в этой картинке действительно можно увидеть перевёрнутое дерево.
Пример каталога
Как же устроены деревья?
Рассмотрим основные элементы дерева на примере картинки выше.
Дерево представляет собой набор объектов, называемых узлами. Каждый узел содержит значение или данные, и он может иметь или не иметь дочерний узел. Узлы, у которых нет дочерних узлов называются листьями.
На картинке узлами являются все представленные папки, при этом листьями являются только те, внутри которых нет папок, например «lib», «disc», «mail», «X11» и т. п.
Все узлы деревьев соединены рёбрами, рёбра показывают связи между узлами.
На примере с картинки, с помощью рёбер мы можем ходить по каталогам и понимать, что находится внутри каждой папки. Также от каждой папки по рёбрам можно вернуться к корню.
На вершине дерева находится корень — такой узел, у которого нет родительских узлов, но при этом есть один или более дочерних узлов.
В нашем случае корнем является каталог «/».
Основные элементы дерева
Может возникнуть вопрос, почему же корень находится на вершине? Ответ прост: мы – программисты, мы так видим 🙂
Характеристики дерева
Есть две важные характеристики дерева, которые нужно знать при работе с ним:
- Высота дерева.
- Глубина узла.
Высота дерева – это длина самого длинного пути к листу. Глубина узла – это расстояние от узла до его корня.
Для дерева, представленного выше, высота дерева будет равняться трём. Глубина узла, например «local» будет равняться двум.
В чём преимущество деревьев?
Преимущество деревьев в том, что, несмотря на относительную сложность их формирования, все операции с ними являются очень простыми. Так, например, операции вставки, удаления и поиска элементов в дереве выполняются в тысячи, а то и десятки тысяч раз быстрее чем аналогичные операции с неупорядоченным массивом. Более точными цифрами по каждому виду деревьев поделимся в следующих материалах.
А что вообще делать с деревьями?
Области применения деревьев очень широки и разнообразны причем не только в программировании. В большинстве случаев именно благодаря использованию древовидных структур удаётся значительно ускорить работу с данными, и во многих базах данных решения, основанные на их применении успешно используются.
Ещё больше полезностей о деревьях мы расскажем в наших следующих статьях!
