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

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

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

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

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

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

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

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

  Студентка 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» относительно заданного порядка.

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