Деревья

В этом руководстве вы узнаете все о деревьях. Вы познакомитесь с частями деревьев и их типами. 

Дерево — это нелинейная иерархическая структура данных. Она состоит из узлов и ребер, которые соединяют узлы.

Вот так выглядят деревья:

Зачем нужны деревья

Другие структуры данных, например, массивы, списки, стеки и очереди, линейные. Это значит, что данные в них хранятся последовательно. Когда мы выполняем любую операцию в линейной структуре данных, временная сложность растет с увеличением размера данных. В современном мире это не очень круто. 

Разные древовидные структуры позволяют быстрее и легче получать доступ к данным, поскольку дерево — структура нелинейная. 

Части дерева

• Узел — это объект, в котором есть ключ или значение и указатели на дочерние узлы. 
  Узлы, у которых нет дочерних узлов, называют листами или терминальными узлами. 
  Узлы, у которых есть хотя бы один дочерний узел, называются внутренними.
• Ребро связывает два узла.
• Корень — это самый верхний узел дерева. Его ещё иногда называют корневым узлом.

Другие понятия

• Высота узла — это максимальная длина пути от этого узла к самому нижнему узлу (листу).
• Глубина вложенности узла — длина пути от корня до этого узла.
• Высота дерева —  это высота корневого узла или глубина самого глубокого узла. 
• Степень узла — это общее количество ребер, которые соединены с этим узлом.

• Лес — множество непересекающихся деревьев. Например, если «срезать» корень, получится лес. 

Виды деревьев

1. Двоичное дерево.

2. Дерево двоичного поиска.

3. АВЛ-дерево.

4. B-дерево.

Обход дерева

Чтобы выполнить какую-либо операцию с деревом, нужно добраться до определенного узла. Для этого и существуют алгоритмы обхода дерева. Они помогают «дойти» до необходимого узла. 

👉 Подробнее об обходе дерева.

Где используются

• Деревья двоичного поиска помогают быстро проверить наличие элемента в наборе.
• Куча — это тоже своеобразное дерево. Кучи используют в алгоритме сортировки кучей.
• Префиксные деревья используются в маршрутизаторах, они хранят информацию о маршруте. 
• Большинство популярных баз данных основаны на B-деревья и T-деревья.
• Компиляторы используют абстрактное синтаксическое дерево, чтобы находить синтаксические ошибки в ваших программах.