Двоичные деревья и их роль в информатике

     Министерство  образования и науки РФ

Государственное образовательное учреждение высшего 

профессионального образования  «Красноярский государственный  педагогический университет им. В.П. Астафьева» 

Кафедра алгебры 
 
 
 
 
 
 

ДВОИЧНЫЕ  ДЕРЕВЬЯ И ИХ РОЛЬ В ИНФОРМАТИКЕ

(курсовая  работа) 
 
 
 
 

Выполнил: Д.Н.Ростовцева,

  Студентка 42 группы 

Научный руководитель:

к.ф.–м.н., А.Н. Руцкий 
 
 
 

Красноярск, 2010

Содержание 

Введение…………………………………………………………………………..3

Глава I. Деревья, используемые в информатике………………………………5

1. Корневые деревья в информатике …………………………………..5
2. Двоичные деревья …………………………………………………….8
3. Виды двоичных деревьев……………………………………………..9                                         

Глава II. Двоичные деревья в информатике…………………………………..10

1. Сортировка данных                                                                            
1. Метод дерева сортировки ……………………………………10
2. Метод кучи……………………………………………………...16
2. Представление алгебраических выражений с помощью двоичных деревьев………………………………………………………………18

Заключение……………………………………………………………………...20

Библиографический список ………………………………………………….23 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

    Введение 

    Впервые понятие «дерево» ввел физик Густав Кирхгофф в 1847 году. Будучи студентом Кенигсбергского университета, он сформулировал законы, управляющие течением тока в электрических сетях. Сети проводов могут быть рассмотрены, как графы. Уравнения, которые вытекают из законов Кирхгоффа, не являются не зависимыми, и Кирхгофф использовал деревья для получения независимого подмножества уравнений.

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

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

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

    Допустим  А – конечное множество элементов с тотальным порядком, который мы будем обозначать символом ≤. Будем писать а ≤ b и говорить «а меньше или равно b». Предположим, что элементы множества А заданы неупорядоченным списком а₁, а₂, …, а_N и мы хотим отсортировать данный список, то есть получить упорядоченный список s_1, s₂, …,s_N, то есть получить список s₁ ≤ s₂ ≤ … ≤ s_N.

    Имеются много методов получения желаемого  списка. Например, «метод селекции», «пузырьковый метод», « метод вставки » и  т.д. В данной курсовой работе  рассмотрим  два метода сортировки – «метод дерева сортировки» и « метод кучи», а так же покажем, как с помощью деревьев можно записывать алгебраические выражения.

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

    Для достижения поставленной цели необходимо решить следующие задачи:

1. Проанализировать учебную и справочную литературу по данной теме и систематизировать основной материал.
2. Систематизировать теорию по данному вопросу.
3. Показать применение двоичных и корневых деревьев в информатике.
4. Сформулировать алгоритмы сортировки по методу дерева сортировки и по методу кучи.

    ГЛАВА I. ДЕРЕВЬЯ, ИСПОЛЬЗУЕМЫЕ В ИНФОРМАТИКЕ 

    1.1. Корневые деревья в информатике 

    Многие  приложения теории графов, особенно в  компьютерной науке (информатике), используют определенные типы деревьев, так называемые корневые деревья. Корневое дерево – это дерево, у которого одна специфическая вершина отличается от всех остальных. Корневое дерево может быть использовано, чтобы описать отношение между потомками человека. Например, типичное генеалогическое дерево, показывающее потомков прабабушки Антона (рис. 1). 

    Корневые  деревья более знакомы в компьютерной науке как модели для структуры  директории файлов. Обычно корень –  это позиция для возврата операционной системы перед очередным стартом. На рисунке 2  показана часть многопользовательской файловой директории, организованной в виде корневого дерева. Такая организация директории преследует две цели: во-первых, связные файлы оказываются удобным образом сгруппированными, а во-вторых, различные пользователи системы получают возможность организовать защиту доступа к своей информации, потребовав предъявления пароля.

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

    Определение 1. Корневое дерево – это пара (Т, v^*), где Т – дерево и v^* Î V_T. Специфическая, отличная от других вершин, v^* называется корнем дерева. Лист в корневом дереве – это вершина, которая имеет валентность 1 и которая не равна корневой вершине; вершиной решения (или внутренней вершиной) называется вершина, которая не является ни корневой, ни листом.

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

    Определение 2. Пусть (Т, v^*) является корневым деревом. Уровень вершины w для дерева Т – это длина (единственного) пути для Т от вершины v^* к вершине w. Высотой дерева Т называется максимальный уровень его вершин.

    Пусть Т – корневое дерево и пусть  р – вершина уровня к > 0, то есть, иначе говоря, мы предполагаем, что р ≠ v^*. Так как путь для дерева Т от v^* к р является единственным, то из этого следует, что вершина р является смежной для единственной вершины уровня к-1.

    Определение 3. Пусть (Т, v^*) – корневое дерево, и пусть р – вершина уровня к > 0. Вершина q уровня к-1  и смежная вершине р, называется родителем вершины р. В свою очередь вершина р называется ребенком вершины q, а любая вершина уровня к, смежная к вершине q, называется братом вершины р.

    Определение 4. m- арным деревом называется корневое дерево, в котором каждая родительская вершина имеет самое большее m детей, и некоторые родительские вершины имеют ровно m детей.

    Определение 5. Корневое дерево высоты h называется совершенным, если все листовые вершины расположены на уровне  h.

    Пример. На рисунке 3 корень дерева - v*, листья – w, n, m, c, s, f, j, z, вершины решений – k, p, e, a,g, r, d.  

2. Двоичные  деревья

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

    Определение 7. Полным бинарным (двоичным) деревом называется дерево, у которого только одна вершина имеет валентность 2, а все остальные вершины имеют валентность 1 или 3. вершины с валентностью 2 называется корнем дерева; вершины с валентностью 3 называются вершинами решения и вершины с валентностью 1 называются листьями.

    Пусть Т - полное двоичное дерево с высотой  превышающей ноль и с корнем v^*. Удаление v^* и двух его инцидентных граней порождает два непересекающихся двоичных дерева (двоичный лес), чьи корни – это вершины дерева Т первого уровня. Они называются левым поддеревом и правым поддеревом корня v^*. Корни этих поддеревьев называются левым и правым ребенком корня v^*, а удаленные грани называются соответственно левой и правой ветками вершины v^*. Для каждого из этих поддеревьев, если их высота не меньше 1, могут быть определенны их соответствующие левые и правые поддеревья, и так вдоль всего дерева. Если Т – не является полным двоичным деревом, то его левое или правое поддерево может быть пустым.

    Определение 8. Двоичное дерево включает совокупность трех множеств (L, S, R), где L и R – двоичные (или пусты) деревья, а S синглетное множество. Единственным элементом множества S является корень.   Элементы L и Rназываются соответственно левым и правым поддеревьями корня.

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

    1.3. Виды двоичных деревьев 

    Процедура сортировки с помощью дерева использует специальный вид двоичного дерева. Это – двоичное дерево, у которого множество вершин полностью упорядоченно (на множестве вершин определен тотальный порядок). Для каждой вершины v дерева, вершины в его левом поддереве – меньше или равны вершины v, и сама вершина v – меньше или равна вершинам правого поддерева. Введем формальное определение.

    Определение 9. Дерево сортировки – это двоичное дерево Т такое что:

1. множество вершин V тотально упорядоченно (с отношением порядка обозначаемым символом ≤), и
2. для каждой вершины v Î V, w_L ≤ v для каждой вершины w_L, находящейся в левом поддереве  вершины v, и v ≤ w_R для каждой вершины w_R, находящейся в правом поддереве  вершины v.

    Определение 10. Ниспадающая куча – это двоичное дерево высоты h такая что:

1. все листовые вершины расположены на уровнях h-1 или h;
2. листовые вершины на уровне h оказываются расположенными на диаграмме максимально далеко слева ( это имплицирует то, что любая листовая вершина на уровне h-1 является расположенной максимально далеко справа. Другими словами, поддерево, полученное из исходного в результате, удаления вершин уровня h и их инцидентных граней является совершенным двоичным деревом);
3. множество вершин имеет тотальный порядок, обозначаемый как ≤;
4. если «q» является родителем «р», то р ≤ q, то есть ребенок «р» меньше или равен родителя «q» относительно заданного порядка.

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

    ГЛАВА II. ДВОИЧНЫЕ ДЕРЕВЬЯ В ИНФОРМАТИКЕ 

    2.1. Сортировка данных 

    2.1.1. Метод дерева сортировки 

    Процедура сортировки по методу дерева происходит в два этапа. Предположим нам  даны элементы множества А в качестве неупорядоченного (несортированного) списка а₁, а₂, …, а_N. На первом этапе список используется, чтобы сконструировать дерево сортировки, у которого вершинами являются элементы множества А и корнем является элемент а₁ – первый элемент несортированного списка. Второй этап позволяет получить сортированный список на основании дерева сортировки.

    Прежде  чем перейти к общей процедуре  реализации данного метода рассмотрим следующий пример.

    Пример. Предположим, что начальный список – 6, 2, 9, 4, 15, 1, 12, 7, 20, 10, 3, 11, и требуется его отсортировать по возрастающей. Последовательность деревьев сортировки получается путем добавления каждого элемента списка в определенное место (очередь) в качестве листовой вершины. Множество вершин окончательного (заключительного) дерева сортировки содержит все элементы исходного списка.

    Итак, первый элемент 6 определен в качестве корня. Так как 2 ≤ 6, то мы создаем левую от корня ветку с вершиной 2 на ее конце.

    Затем, так как 9 ≥ 6, то мы  создаем правую для корня 6 ветку и размещаем на ее конце 9.

    Отсортируем следующий элемент 4, для этого  сначала сравним его с корнем 6. так как 4 ≤ 6, то мы должны разместить 4 в левое для корня 6 поддерево. Таким образом, мы рассматриваем левое поддерево, у которого корень – 2. теперь 4 ≥ 2, поэтому мы создаем правую ветку для вершины 2 и на конце этой ветки размещаем вершину 4.

    При вставке следующего элемента 15 мы руководствуемся следующими соображениями: 15 ≥ 6, поэтому идем по правому для корня 6 поддереву к вершине – 9; 15 ≥ 9, поэтому создаем правую ветку для вершины 9 и размещаем на втором уровне вершин.

    На  данной стадии мы построили (выстроили) следующее дерево сортировки (рис. 5):

    Будем продолжать наращивать дерево, аналогичным  образом  добавляя остальные элементы исходного списка. Чтобы вставить элемент х, мы сначала сравниваем его с корнем 6. если х  ≤ 6 идем по левому поддереву; иначе идем по правому поддереву. Повторяем сравнение х с корнем нового дерева. На некоторой стадии сложится такая ситуация, при которой у нас не будет ни левого, ни правого поддерева, по которому можно было бы идти, и тогда следует добавить х в качестве левого или правого ребенка.

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

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

    Требуемая процедура внесения в список может  быть описана рекурсивно следующим  образом:

1. вносим в список элементы из левого поддерева корня,
2. вносим в список непосредственно сам корень, и
3. вносим в список элементы из правого поддерева корня.

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

    Проиллюстрируем как работает этот метод на некотором шаге. Рассмотрим поддерево, изображенное на рисунке 7.

    Чтобы обработать это дерево сортировки, мы начинаем составлять список элементов, в который помещаем сначала элементы дерева сортировки, находящиеся в левом поддереве. В данном случае первым таким элементом будет (1). Далее вносим корневой элемент (2). Затем вносим в список элементы, находящиеся в правом поддереве. Чтобы вносить в список элементы правого поддерева, мы снова осуществляем три описанных шага. Описанный алгоритм дает список 1, 2, 3, 4, и на этом заканчивается первая стадия для главного дерева.

    Вторая  стадия начинается с внесения в список элемента 6 – корня основного  дерева сортировки. Далее мы должны внести в список элементы правого поддерева по аналогии с описанным алгоритмом. Окончательный список в результате сортировки будет 1, 2, 3, 4, 6, 7, 9, 10, 11, 12, 15, 20.

    Опишем  процедуру составления списка для  общего случая дерева сортировки, которая состоит из двух этапов:

1. построение дерева сортировки на основе произвольного списка элементов;
2. составление списка упорядоченных элементов на основе дерева сортировки.

    Этап 1. построение дерева сортировки.

    Предположим, что а₁, а₂, …, а_N – исходный, не отсортированный список элементов. Работая с элементами этого списка, мы на каждом шаге присоединяем к дереву сортировки ровно одну ветку. Каждый раз, когда элемент обработан, мы добавляем к дереву ветку с листовой вершиной, которая впоследствии может стать родителем. В самом начале процедуры построения дерева сортировки самый первый элемент а₁ определяется, как корневой элемент дерева и при этом мы получаем дерево сортировки, у которого корень имеет непустые левые и правые поддеревья.

    Добавление  ветки с элементом «х» на конец  происходит следующим образом. Сравниваем элемент «х» с корнем; если х  ≤ v^* переходим к корню левого поддерева, иначе к корню правого поддерева. Далее мы сравниваем «х» с корнем соответствующего поддерева и все повторяем снова.

    Итак, построение дерева сортировки реализует  следующий алгоритм.

    Алгоритм построения дерева сортировки:

1. для множества, состоящего всего лишь из одного элемента, этот элемент и является корнем, а дерево сортировки представляет собой дерево сортировки с одним элементом, который является вершиной этого дерева. Для множества не из одного элемента первый элемент выбираем корнем.
2. элемент а_n сравниваем с корнем. Если а_n ≤ корня, то переходим к левому поддереву. Если левое поддерево пусто, то добавляем а_n в качестве левого ребенка корня. Если корень ≤ а_n, то переходим к правому поддереву. Если правое поддерево пусто, то добавляем а_n в качестве правого ребенка корня. Чтобы образовать следующее дерево сортировки, увеличиваем n до n+1 и повторяем шаг 2.

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

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

    Этап 1. Создание кучи.

    Пусть задан не отсортированный список   а₁, а₂, …, а_N. Множество, состоящее из одного элемента, представляет собой тривиальный случай. Предположим, что элементы а₁, а₂, …, а_к-1 уже были сформированы в виде кучи, и мы должны добавить следующий элемент а_к. Имеется единственная позиция, при которой, добавляя а_к, мы удовлетворяем условиям определения ниспадающей кучи. Это либо ближайшая правая позиция от самой правой вершины на самом высоком уровне, либо, если самый высокий уровень полностью укомплектован, крайняя левая позиция на новом более высоком уровне.

    Однако  добавление а_к в такое положение еще не гарантирует с неизбежностью образование кучи.

    Создание  кучи из исходного списка а₁, а₂, …, а_N может быть получено на основании следующего алгоритма.

    Алгоритм  создания кучи:

1. Множество а₁ – корень.
2. Добавляем следующий элемент таким образом, чтобы дерево удовлетворяло условиям 1 и 2 из определения кучи.
3. Если необходимо, восстанавливаем кучу по методу «пузырькового» подъема новой вершины вдоль дерева.
4. повторяем шаги 2 и 3 для каждого элемента списка.

    Этап 2. Получение упорядоченного (отсортированного) списка на основании кучи.

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

    Алгоритм  преобразования кучи.

1. обменяем корень с последней вершиной «u», то есть с самой правой вершиной на самом высоком уровне. Зафиксируем положение полученной последней вершины. ( Под фиксацией положения вершины, мы подразумеваем, что зафиксированная вершина игнорируется при всех последующих манипуляциях дерева).
2. восстановим дерево до кучи, путем осаждения вниз нового корня «u» следующим образом: поменяем местами корень «u» с самым большим из двух его детей, затем переходит к поддереву, меняя каждый раз вершину «u» с самым большим из её детей. Если это поддерево имеет высоту 0, то переходим к шагу 3, иначе повторяем шаг 2 для этого поддерева.
3. повторяем шаги 1 и 2 пока все вершины не окажутся зафиксированными.

    Пример. Произвести сортировку по методу «кучи» списка 10, 7, 8, 5, 4, 9, 1, 3, 6,  2.

    Предположим, что куча на рисунке 8 получена из исходного не отсортированного списка.

    Корень  кучи – это максимальный элемент, который поэтому должен быть помещен  в конце списка. Поменяем этот корень местами с последней вершиной в куче. Зафиксируем положение последней вершины.

    Мы  должны восстановить кучу, помня о  том, что вершина 10 уже находится  в своей окончательной позиции  и её никуда не следует перемещать. Итак, чтобы восстановить кучу, надо корень 4 опустить вниз по дереву, последовательно обменивая число 4 с большим из его детей, то есть с 9. и так далее продолжая процесс, мы приходим к такому преобразованию дерева, при котором все его вершины находятся в своем окончательном положении.  

       Пусть S представляет собой множество, на котором определены две двоичные операции Å и *. Без соглашения о порядке выполнения операций выражение типа x Å y * z могут быть прочитаны неоднозначно: или (x Å y) * z, или x Å (y * z).

       Такие выражения могут быть однозначно представлены на основе двоичных деревьев следующим образом. Выражение могут  быть определены рекурсивно, как Х a У, где a - символ двоичной операции, а Х и У являются элементами множества S или выражений, составленных из элементов множества S. Такое выражение может быть представлено как двоичное дерево  с корнем a, левым ребенком Х и правым ребенком У. Например, рис. 9. 

    Заключение 

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