Нелинейные структуры данных

В предыдущих разделах мы рассмотрели линейные структуры динамических списковых данных.

Введение в динамическую переменную двух и более полей-указателей позволяет получить нелинейные структуры данных. Наиболее распространенными являются структуры с иерархическим представлением, кото­рые хорошо изображаются следующим образом:

Такая конструкция данных получила название «дерево».

Дерево состоит из элементов, называемых узлами (вершинами). Узлы соединены между собой направленными дугами. В случае X®Y вершина X называется родителем, а Y – сыном (дочерью).

Дерево имеет единственный узел, не имеющий родителей (ссылок на этот узел), который называется корнем. Любой другой узел имеет ровно одного родителя, т.е. на каждый узел дерева имеется ровно одна ссылка.

Узел, не имеющий сыновей, называется листом.

Внутренний узел – это узел, не являющийся ни листом, ни корнем. Порядок узла равен количеству его узлов-сыновей. Степень дерева – максимальный порядок его узлов. Высота (глубина) узла равна числу его родителей плюс один. Высота дерева – это наибольшая высота его узлов.

Бинарные деревья

Бинарное дерево – это динамическая структура данных, в которой ка­ждый узел-родитель содержит, кроме данных, не более двух сыновей (левый и правый).

На рисунке приведен пример бинарного дерева (корень обычно изображается сверху, хотя изображение можно и перевернуть).

Такая структура данных организуется следующим образом (N – NULL):

Высота дерева, как и раньше, определяется количеством уровней, на которых располага­ются его узлы.

Если дерево организовано таким образом, что для каждого узла все ключи его ле­вого поддерева меньше ключа этого узла, а все ключи его правого поддерева – больше, оно называется деревом поиска. Одинаковые ключи здесь не допускаются.

Представление динамических данных в виде древовидных структур оказывается довольно удобным и эффективным для решения задач быстрого поиска информации.

Сбалансированными, или AVL-деревьями, называются деревья, для каждого узла которых высóты его поддеревьев различаются не более чем на 1. Причем этот критерий обычно называют AVL-сбалансированностью в отличие от идеальной сбалансированности, когда для каждого узла дерева количество узлов в его левом и правом поддеревьях различаются не более чем на единицу [44].

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