Автоматизация работы с базами данных

Сбалансированное дерево – дерево, в котором число вершин в левых и правых поддеревьях отличается не более чем на 1.

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

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

Бинарное (двоичное) дерево – это динамическая структура данных, состоящая из узлов, каждый из которых содержит, кроме данных, не более двух ссылок на различные бинарные деревья, то есть степень бинарного дерева равна 2 (деревья степени больше двух называют сильно ветвящимися деревьями – multiway tree).

Для деревьев определены следующие операции:

1) включение (добавление) узла в дерево;

2) обход дерева;

3) удаление (исключение) узла;

4) поиск по дереву.

Приведем словесные алгоритмы данных операций на примере используемой в задаче динамической структуры – двоичном дереве поиска.

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

1) Поиск по дереву с включением узла

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

3) Обход дерева

Обход дерева подразумевает посещение всех узлов дерева в определенном порядке. Существует 3 порядка:

а) Сверху-вниз (preorder) – корень посещается ранее, чем поддеревья;

б) Слева-направо (inorder) – с самого левого узла;

в) Снизу-вверх (postorder) – корень посещается после поддеревьев.

В частности, понятно, что вывод в порядке обхода слева-направо выведет упорядоченную по ключу последовательность.

4) Исключение из дерева

Исключение узла из дерева процедура достаточно неоднозначная. Существуют различные приемы удаления узла. Для дерева поиска можно использовать следующий прием:

а) если узел – лист, то исключение очевидно, для предка удаляем ссылку на данный узел;

б) если узел имеет не более одного потомка, то для предка узла устанавливаем ссылку на потомка узла;

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

Алгоритмы, реализующие данные операции, в контексте задачи приведены в разделе «5. Описание программы».

5. Описание программы

Язык программирования Turbo Pascal является процедурным языком программирования. Поэтому при разработке программы активно использовались приемы процедурного программирования.

Процедурное программирования – способ программирование с широким использованием подпрограмм (процедур). Основой метода является использование принципа модульности построения сложных программ, причем каждый программный модуль должен иметь ограниченный объем, выполнять одну специфическую функцию по обработке данных и использовать композиции только трех базовых элементов – линейной, ветвящейся и циклической структур, для описания которых разработаны специальные языковые конструкции. Основная цель структурного программирования – создать программу с минимальными взаимосвязями между ее модулями. Выделяют следующие достоинства процедурного программирования:

- упрощается процесс создания сложных программ;

- уменьшается вероятность появления ошибок;

- использование модулей небольших размеров позволяет упростить и ускорить процесс отладки;

- при использовании процедурного программирования значительно сокращается трудоемкость разработки технической документации.

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

Проектирование «сверху-вниз» описывает процесс решения задачи от более сложного к более простому – декомпозиция задачи, то есть разбиение задачи на подзадачи и так далее. Это стандартный и очевидный подход, который наиболее часто используется при решении многих задач.

Проектированием «снизу-вверх» обратно выше указанному подходу – заведомо известно, что понадобится решать конкретные элементарные задачи в рамках всей задачи, для которых можно уже на начальном этапе разработать алгоритмы. Использование подходы «снизу-вверх» объясняется тем, что явно понадобятся подпрограммы реализующие операции работы с двоичным деревом поиска. То есть необходимо разработать алгоритмы для выполнения стандартных операций (в нашем случае, включение и удаление узла) и затем в ходе разработки программы, может быть, скорректировать ее содержание или выполнение.

5.1 Описание логической структуры программы

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

Рис. 2. Схема взаимодействия подпрограмм

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

Объекты, используемые в программе, могут быть:

1) глобальные (внешние): объявленные во внешней подпрограмме или программе и не переопределенные в данной;

2) локальные (внутренние): определенные в данной подпрограмме и доступные и используемые только в ней и во всех вложенных в нее блоках или подпрограммах, в которых они не переобъявлены;

Глобальные объекты доступны в программе, в которой они объявлены, и во всех вложенных в нее подпрограммах, в которых они не переобъявлены. К глобальным объектам относят все объекты (из интерфейсной части) из подключаемой библиотеки. Так как библиотека подключается в начале программы, то можно считать, что ее объекты уже описаны как бы в начале текста программы.

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

Если рассматривать область действия подпрограмм, то можно представить следующую схему уровней вложенности подпрограмм.

Рис. 3. Вложенность подпрограмм

 Скачать реферат