Деревья. Основные определения. Применение деревьев. - EcsFlash/DataTypes GitHub Wiki

Дерево - это абстрактная структура данных, представляющая собой набор элементов, называемых узлами, связанных между собой направленными рёбрами.

Пример дерева:

Двоичное дерево состоит из вершин и связей между ними. Конкретнее, у дерева есть выделенная вершина-корень и у каждой вершины может быть левый и правый сыновья.

У этого дерева корнем будет вершина A. Видно, что у вершины D отсутствует левый сын, у вершины B — правый, а у вершин G, H, F и I — оба. Вершины без сыновей принято называть листьями.

Каждой вершине X можно сопоставить свое дерево, состоящее из вершины, ее сыновей, сыновей ее сыновей, и т.д. Такое дерево называют поддеревом с корнем X. Левым и правым поддеревьями X называют поддеревья с корнями соответственно в левом и правом сыновьях X. Заметим, что такие поддеревья могут оказаться пустыми, если у X нет соответствующего сына.

Основные компоненты дерева:

Узел (Node): Каждый элемент дерева, который может содержать данные и иметь ноль или более дочерних узлов.

Ребро (Edges): Линии, соединяющие узлы.

Корень (Root): Узел, который не имеет родителя, и является начальной точкой в дереве.

Родитель (Parent): Узел, от которого исходит ребро.

Потомок (Child): Узел, который связан ребром с родителем.

Лист (Leaf): Узел, не имеющий дочерних узлов.

Уровень (Level): Уровень корня равен 0, уровень его дочерних узлов - 1, и так далее.

Высота (Height): Максимальный уровень в дереве.

Поддерево (Subtree): Узел и все его потомки, а также рёбра между ними.

Применение деревьев:

Иерархические структуры: Деревья применяются для представления иерархических структур, таких как файловые системы, организационные структуры и др.

Структура данных в информатике: Деревья используются для реализации различных структур данных, таких как бинарные деревья поиска, кучи, AVL-деревья и др.

Анализ и обработка данных: Деревья используются для анализа и обработки данных, например, в алгоритмах обхода графов, поиска путей, оптимизации запросов в базах данных и т.д.

Вся полезная инфа про деревья

Все виды деревьев будут рассмотрены в следующих статьях.