Файл: Динамические структуры данных. Бинарные деревья.pdf

ВВЕДЕНИЕ

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

Очень часто при разработке приложений, работающих с большим объемом входных данных, возникает вопрос об их хранении во время выполнения программы. Несомненно, тип данных – массив решает вопрос хранения данных, однако очевидно, что он не лишен недостатков. Главный из них – это, несомненно, фиксированный размер. Это свойство нельзя изменить даже для динамически создаваемых массивов, поэтому вы должны выделять для них память «с запасом». Однако даже «резерв» ограничен, и никто не может гарантировать, что его будет достаточно, в противном случае этого «резерва» может хватить, так что большая часть выделенной программе памяти будет потрачена впустую.

Эта проблема решается с помощью динамических структур данных.

Динамические переменные создаются в динамической памяти во время выполнения программы. Доступ к ним осуществляется через указатели. Используя эти переменные, вы можете обрабатывать данные, объем которых не известен до запуска программы. Память для таких данных выделяется блоками, которые связываются друг с другом. Такой способ хранения данных называется динамическими структурами.

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

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

Объект исследования – структуры данных.

Предмет исследования – динамические структуры данных, бинарные деревья.

Цель исследования заключается в изучении динамических структур данных, а именно – бинарных деревьев.

Задачи исследования формируются исходя из его цели и заключаются в следующем:

• раскрыть понятие динамических структур данных;
• провести классификацию динамических структур данных;
• рассмотреть общую концепцию организации динамических структур данных;
• изучить вид динамических структур данных – бинарные деревья;
• создать программный модуль, содержащий описание динамической библиотеки для работы с бинарными деревьями;
• написать программу, иллюстрирующую работу с организованной динамической библиотекой.

1 Динамические структуры данных

1.1 Введение в динамические структуры данных

Объект данных имеет динамическую структуру, если его размер изменяется во время выполнения программы или он безразмерен^[1].

Все переменные, которые указаны в программе, размещаются в одной непрерывной области оперативной памяти – сегмент данных. Длина сегмента данных представляет собой область, которая определена архитектурой микропроцессора^[2].

Однако, если заранее неизвестны размеры значений переменных, или сам факт существования значения той или иной переменной, то для результата переменной приходится отводить память в расчете на самое большое значение, что приводит к ненадлежащему использованию памяти. Это особенно трудно при обработке больших наборов данных.

Предположим, например, что у вас есть массив из 400 строк по 100 символов. Этот массив требует приблизительно 50K, что меньше максимального значения в 64K. Если остальные переменные помещаются в оставшиеся 14 килобайт, то массив такого размера не представляет проблемы. А если нужны два таких массива, то для этого потребуется 1000K и выделенного сегмента данных в 64 К недостаточно.

Рассмотрим пример сортировки – когда сортируется большой объем данных, то создается копия массива, сортируется и затем отсортированные данные записываются в исходный массив. Это сохраняет целостность данных, но требует наличия двух копий данных во время выполнения программы.

С другой стороны, объем памяти компьютера ограничен, чтобы успешно решать проблемы с большой размерностью данных. Выход – использование так называемой динамической памяти^[3].

Динамическая память – это оперативная память компьютера, которая предоставляется программе в процессе ее работы, минус сегмент данных (64К), стек (16К) и сам модуль программы. Размер динамической памяти может варьироваться. По умолчанию динамическая память – это вся доступная память компьютера^[4].

Динамическая память фактически является единственным способом обработки широкомасштабных массивов данных. Многие практические проблемы трудно или невозможно решить без использования ДП. Например, при разработке САПР статическое распределение памяти невозможно, поскольку размерность математических моделей в разных проектах может значительно различаться.

По своим адресам вызываются как статические, так и динамические переменные. Без адреса нельзя получить доступ к правильной ячейке памяти, но, если используются статические переменные, адрес напрямую не указывается. Обращение к переменной происходит по имени. Компилятор помещает переменные в память и подставляет нужные адреса в коды команд^[5].

Адресация динамических переменных осуществляется с помощью указателей. Их значения определяют адрес объекта.

Для работы с динамическими переменными в программе необходимо выполнить следующие действия:

• выделение памяти динамической переменной;
• инициализация указателя;
• освобождение памяти после использования динамической переменной.

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

1.2 Классификация динамических структур данных. Бинарные деревья

Данные динамической структуры, внутреннее строение которых приведено в виде некоторого закона, но количество элементов, их взаимное расположение и отношения могут динамически изменяться во время выполнения программы, согласно закону формирования (рисунок 1.1)^[6].

Рисунок 1.1 – Обобщенная классификация данных динамической структуры

Данные динамической структуры включают файлы, несвязанные и связанные динамические данные.

Рассмотрим подробнее такую структуру, как дерево^[7].

Дерево – это конечное множество узлов, такое что:

A) Существует один специальный узел, который называется корнем этого дерева.

B) Другие узлы (кроме корня) содержатся в m≥0 попарно непересекающихся подмножествах , каждое из которых, в свою очередь, является деревом. Деревья называются поддеревьями этого дерева.

Это определение рекурсивное^[8]. Дерево – это множество, которое состоит из корня и присоединенных поддеревьев, которые также являются деревьями. Дерево определяется через себя. Однако это определение имеет смысл, поскольку рекурсия конечна. В каждом поддереве меньше узлов, чем в дереве. В конце поддеревья содержат только один узел.

На рисунке 1.2 показано дерево с семью узлами.

Рисунок 1.2 – Дерево

Узлы, которые не содержат поддеревьев, называются концевыми узлами или листьями. Множество непересекающихся деревьев называется лесом. Например, лес формируется из поддеревьев, которые исходят из одного узла.

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

Бинарное дерево – это конечное множество элементов, которое либо пусто, либо содержит один элемент, называемый корнем дерева, а остальные элементы множества делятся на два непересекающихся подмножества, каждое из которых само является бинарным деревом. Эти подмножества называются левым и правым поддеревьями исходного дерева. Каждый элемент бинарного дерева называется узлом дерева^[9].

На рисунке 1.3 показан способ изображения бинарного дерева.

Рисунок 1.3 – Бинарное дерево

Это дерево состоит из шести узлов, 22-корень дерева. Его левое поддерево имеет корень 19, а правое- корень 37. Это изображается двумя ветвями, исходящими из 22: левой – к 19 и правой – к 37. Отсутствие ветви обозначает пустое поддерево. Например, левое поддерево бинарного дерева с корнем 19 пустое. Бинарное дерево с корнем 37 имеет пустые левое и правое поддеревья.

Если А – корень бинарного дерева и В – корень его левого или правого поддерева, то говорят, что А-отец В, а В-левый или правый сын А. Узел, не имеющий сыновей (такие как узлы 8, 24, и 44), называется листом.

Например, в дереве на рисунке 1.3: 22 – предок 19 и 8-потомок 19, но 8 не является ни предком, ни потомком 22.

Два узла являются братьями, если они сыновья одного и того же отца. Если каждый узел бинарного дерева, не являющийся листом, имеет непустые правые и левые поддеревья, то дерево называется строго бинарным деревом. Строго бинарное дерево с n листами всегда содержит 2n-1 узлов. В данном случае не строго бинарное дерево.

Упорядоченные бинарные деревья – это деревья, в которых для каждого узла Х выполняется правило: в левом поддереве – ключи, меньшие Х, в правом поддереве – большие или равные Х. Структура бинарного дерева построена из узлов. Узел дерева содержит поле данных и два поля с указателями^[10].

При добавлении элемента нужно сохранить свойство упорядоченности, поэтому у добавляемого элемента существует единственное место в дереве (конечно, если такой элемент еще не присутствует в дереве). Проверка наличия элемента в дереве осуществляется тем же способом – переход от узла к узлу происходит по принципу максимального приближения к искомому значению. Если на том месте, где должен находиться искомый элемент, отсутствует поддерево, значит можно утверждать, что такого элемента нет во множестве^[11].

1.3 Операции над бинарным деревом

Над бинарным деревом есть операция – его прохождение, т.е. нужно обойти все дерево, отметив каждый узел один раз ^[12].

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

В двоичном (бинарном) дереве каждый узел может быть связан не более чем двумя другими узлами.

Операции над двоичными деревьями поиска^[13]:

• добавление элемента в дерево;
• удаление элемента из дерева;
• обход дерева (для печати элементов и т.д.);
• поиск в дереве.

Прохождение (или обход) бинарного дерева означает систематическое перечисление всех узлов для выполнения необходимой функциональной обработки. Наиболее известны и практически важны 3 способа прохождения, которые отличаются порядком и направлением обхода бинарного дерева [6]:

• в прямом порядке;
• в симметричном порядке;
• в обратном порядке.

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

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

Направление обхода однозначно определяет последовательность выполнения указанных процедур. Последовательность их рекурсивного вызова для каждого способа прохождения перечислена в следующей таблице.

Таблица 1.1 – Рекурсивные алгоритмы прохождения бинарного дерева.