Дерево поиска — это двоичное дерево, в котором выполняются следующие условия (см. рис.
11): а) l (u) < l (v) для всех вершин u, v, если вершина u находится в поддереве, корень которого — левый преемник v; б) l (u) > l (v) для всех вершин u, v, если вершина u находится в поддереве, корень которого — правый преемник v; в) для всякого значения aS существует единственная вершина v, для которой l (v) = a (S — множество значений, допускающих сравнения).S TM ZNAXDРис.11Дерево поиска
Определение структуры дерева, данное выше, является рекурсивным и отражает рекурсивную природу самой структуры. Структуру данных — дерево можно представить как в статической, так и в динамической памяти. В динамической памяти дерево представляется иерархическим списком. Задать элемент двоичного дерева можно как элемент списка с тремя полями: два ссылочных поля, содержащие указатели на его левое (L) и правое (R) поддеревья, и информационное поле (E):Определение типа элемента бинарного динамического дерева: TypeU =btreebtree = Recordelem: btype; left, right: Uend;Здесь btype — тип информационного поля (если информационное поле имеет сложную структуру, то type может быть типом — указатель на объект, содержащий значение элемента дерева).Чтобы определить дерево как единую структуру, надо задать указатель на корень дерева: D: U;На рис.
12 представлено двоичное динамическое дерево d в cсоответствии с определением типа элемента, сделанным выше. Элементы дерева со степенью 0 и 1 имеют два или одно ссылочное поле со значением равным пустому указателю (NIL). dРис.12 Динамическое бинарное дерево
Обрабатывая дерево, приходится просматривать его элементы — эта операция называется обход дерева (или прохождение дерева).Обход дерева — это способ методичного исследования его узлов, при котором каждый узел проходится точно один раз. Полное прохождение динамического дерева дает линейную расстановку его узлов. Возможны два способа прохождения бинарного дерева (если дерево не пусто): а) в глубину:
прямой (префиксный) порядок: корень, левое поддерево в прямом порядке, правое поддерево в прямом порядке (линейная расстановка узлов дерева, представленного на рис.
10.б: ABDCEGFHJ); - обратный (инфиксный) порядок: левое поддерево в обратном порядке, корень, правое поддерево в обратном порядке (линейная расстановка узлов дерева, представленного на рис.
10.б: DBAEGCHFJ);концевой (постфиксный) порядок: левое поддерево в концевом порядке, правое поддерево в концевом порядке, корень (линейная расстановка узлов дерева, представленного на рис.
10.б: DBGEHJFCA);б) в ширину: узлы дерева посещаются слева направо, уровень за уровнем вниз от корня (линейная расстановка узлов дерева, представленного на рис.
10.б: ABCDEFGHJ).Основные операции при работе с деревьями:
а) поиск элемента в дереве. Операция заключается в прохождении узлов дерева в одном из рассмотренных выше порядке. При прохождении дерева поиска достаточно пройти только то поддерево, которое возможно содержит искомый элемент;
б) включение элемента в дерево. Операция заключается в добавлении листа (исключая сбалансированное дерево — включение элемента в сбалансированное дерево приводит, как правило, к его перестройке) в какое-то поддерево, если такого элемента нет в исходном дереве. При включении нового элемента в дерево поиска лист добавляется в то поддерево, в котором не нарушается отношение порядка;
в) удаление элемента из дерева. Операция заключается в изменении связей между дочерними и родительскими, по отношению к удаляемому, элементами (исключая сбалансированное дерево — удаление элемента из сбалансированного дерева приводит, как правило, к его перестройке); здесь необходимо рассматривать три случая: удаление листа (см. рис.
13.а), удаление элемента с одним потомком (см. рис.
13.б), удаление элемента с двумя потомками (см. рис.
13.в). При удалении элемента степени 2 из дерева поиска изменять связи необходимо так, чтобы не нарушалось установленное в дереве отношение порядка. Лучшим вариантом в этом случае будет перемещение на место удаляемого элемента либо самого правого листа из левого поддерева удаляемого элемента, либо самого левого листа из правого поддерева удаляемого элемента;xx x, а б вРис.
13. Операции с леревомг) сравнение деревьев (проверка деревьев на равенство). Операция заключается в прохождении обоих деревьев в одном порядке до тех пор, пока либо не будут пройдены оба дерева, либо одно из них, либо соответствующие элементы окажутся не равными, либо в одном из деревьев не будет обнаружено отсутствие соответствующего элемента. Только в случае равенства деревьев оба дерева будут пройдены одновременно;
д) копирование дерева. Операция заключается в прохождении исходного дерева и построении нового дерева с элементами, информационные поля которых равны информационным полям соответствующих элементов исходного дерева. Чтобы ввести дерево надо выбрать какой-то способ перечисления его узлов. Одним из возможных способов является так называемая списочная запись (представление). Список — это конечная последовательность атомов либо списков, число которых, может быть и равно нулю (атом — это понятие, определяющее элемент из любого множества предметов). Используя скобки, список можно задать перечислением через запятую его атомов (порядок перечисления атомов определяет их упорядочение). Таким образом, дерево, представленное на рис.
10.б можно записать в виде следующего списка:(A, (B, (D, 0, 0), 0), (C, (E, 0, (G, 0,0)), (F, (H, 0, 0), (I, 0, 0))))Заключение
В версиях Турбо-Паскаля, работающих под операционной системой MS DOS, под данные одной программы выделяется 64 килобайта памяти (или, если быть точнее, 65 520 байт). Это и есть статическая область памяти. При необходимости работать с большими массивами информации этого может оказаться мало. Размер динамической памяти — много больше (сотни килобайт). Поэтому использование динамической памяти позволяет существенно увеличить объем обрабатываемой информации. Приведем основные отличия между статическими и динамическими структурами данных. Статическая структура данных:
имеет идентификатор, по которому можно к ней обратиться; память выделяется в процессе трансляции;
количество элементов такой структуры ограничено и определяется в момент описания;
размерность структуры, т. е. количество ее элементов, не может быть изменено в процессе выполнения программы. Динамическая структура данных:
не имеет идентификатора, а обращение происходит с помощью указателя;
память выделяется в процессе выполнения программы;
можно не фиксировать количество элементов структуры;
можно менять размерность структуры в процессе выполнения программы;
структурные взаимосвязи (связь между элементами) может меняться в процессе выполнения программы. Основным недостатком динамической памяти по сравнению с статической является проигрыш во времени при обращении к величине, так как этот процесс разбит на два шага: сначала ищется указатель, затем по нему — величина. Таким образом, выигрыш в возможностях и памяти приводит к проигрышу во времени динамической структуры данных по сравнению с статической. Использование динамических массивов в качестве динамических величин не всегда возможно и целесообразно. Приведем основные недостатки такой структуры данных:
нет возможности менять просто и быстро удалять элементы из массива или добавлять новые;
при выделении памяти необходимо указывать число элементов, которое точно хватит для данных целей;
не учитываются характерные структуры данных для реализуемой задачи. Для решения этих недостатков используются более гибкие структуры, основанные на списках [3, c27]. Для решения первых двух недостатков наибольшей популярностью и простотой пользуются линейные динамические списки. Количество связанностей выбирается в зависимости от специфики задачи. Более сложные структуры, учитывающие структуру данных задачи, позволяют строить более эффективные и наглядные алгоритмы. Так, например, стек используется в методах трансляции для перевода выражений из стандартной формы записи в постфиксную или инфиксную форму (в зависимости от реализации). Такие структуры данных как очередь широко применяется в теории массового обслуживания, которая целиком и полностью построена на понятии очереди. Так же очереди применяются и в нашей повседневной жизни (во многих учреждениях появились электронные очереди, которые реализуются с помощью такой структуры данных).
Также применяются и более сложные структуры: деревья, хештаблицы и пр. Преимущество линейных структур. В линейных структурах элементы данных располагаются последовательно, друг за другом. Между соседними элементами данных существует отношение непосредственного предшествования.
С каждым элементом данных непосредственно или косвенно сопоставляется его порядковый номер в наборе данных, определяющий его адрес, по которому в свою очередь элемент данных При применении структуры данных иерархического характера (бинарные деревья, хеш-таблицы с неограниченным числом элементов по одному ключу и т. п.) имеют недостатки. Основным недостатком иерархических структур данных является увеличенный размер пути доступа. Очень часто бывает так, что длина маршрута оказывается больше, чем длина самих данных, к которым он ведет. Поэтому в информатике применяют методы для регуляризации иерархических структур с тем, чтобы сделать путь доступа компактным. Несмотря на многочисленные удобства, у простых структур данных есть и недостаток — их трудно обновлять. Иерархические структуры данных по форме сложнее, чем линейные и табличные, но они не создают проблем с обновлением данных.
Их легко развивать путем создания новых уровней. Даже если в учебном заведении будет создан новый факультет, это никак не отразится на пути доступа к сведениям об учащихся прочих факультетов. Недостатком иерархических структур является относительная трудоемкость записи адреса элемента данных и сложность упорядочения. Часто методы упорядочения в таких структурах основывают на предварительной индексации, которая заключается в том, что каждому элементу данных присваивается свой уникальный индекс, который можно использовать при поиске, сортировке и т. п.
Список литературы
Русскоязычные источники
Бондарев В.М., Рублинецкий В. И., Качко Е. Г. Основы программирования. — Харьков: Фолио, Ростов н/Д: Феникс, 1997. — 368 с.
Гагарина Л. Г., Колдаев В. Д. Алгоритмы и структуры данных: — Москва, Финансы и статистика, Инфра-М, 2009 г.- 304 с. Данчула А. Н. Информатика: Учебник / Под общ. ред. — М.: Изд-во РАГС, 2004
Культин Н. Программирование в Turbo Pascal 7.0 и Delphi (+ CD-ROM): — Москва, БХВ-Петербург, 2007 г.- 390 с. Культин Н. T urbo Pascal в задачах и примерах: — Санкт-Петербург, БХВ-Петербург, 2006 г.- 256 с. Лавров С.
Программирование. Математические основы, средства, теория. — СПб.: БХВ-Петербург, 2001. -
320 с. Марченко А. И., Марченко Л. А. Программирование в среде Turbo Pascal 7.
0. Базовый курс: — Москва, Век +, 2004 г.- 464 с. Меженный
О. А. T urbo Pascal. Самоучитель: — Санкт-Петербург, Вильямс, Диалектика, 2008 г.- 336 с. Окулов С. М. Основы программирования. — М.: ЮНИМЕДИАСТАЙЛ, 2002.
— 424 с. Павловская Т. А., Щупак Ю. А. C/C++. Структурное и объектно-ориентированное программирование. Практикум: — Москва, Питер, 2010 г.- 352 с. Попов В.
Б. T urbo Pascal для школьников: — Москва, Финансы и статистика, Инфра-М, 2010 г.- 352 с. Потопахин В.
T urbo Pascal. Освой на примерах: — Санкт-Петербург, БХВ-Петербург, 2005 г.- 240 с. Рапаков Г. Г., Ружецкая С. Ю.
T urbo Pascal для студентов и школьников: — Санкт-Петербург, БХВ-Петербург, 2007 г.- 352 с. Семакин И. Г., Шестаков А. П. Основы алгоритмизации и программирования: Учебник для сред. проф. образования — М.: Издательский центр «Академия», 2008. —
400 с. Симонович С. В. и др. Информатика: Базовый курс: — СПб.: Питер, 2003
Иностранные источники
Альфред В. Ахо, Джон Э. Хопкрофт, Джеффри Д. Ульман.
Структуры данных и алгоритмы: — Москва, Вильямс, 2010 г.- 400 с. Вирт Н. Алгоритмы и структуры данных. — СПб.: Невский Диалект, 2001.
— 352 с. Кнут Д. Искусство программирования. Том1. М.: Издательский дом «Вильямс», 2000. — 720с. Эллиот Б. Коффман Turbo Pascal: — Санкт-Петербург, Вильямс, 2005 г.- 896 с. Электронные источники:
http://comp-science.narod.ru
