Способы построения и представления деревьев

     Содержание 

Введение

   1.Теоретическая часть…………………………………………………….. …...3

   1.1. Рекурсии……………………………………………………………………4

   1.2. Общие сведения о деревьях…………………………………………….….5

   1.3. Леса………………………………………………………………………....6

   1.4. Представление деревьев в памяти ЭВМ………….………………….…….7

   1.5. Идеально сбалансированное бинарное дерево……………….……...…….8

   1.6. Бинарные деревья поиска……………………………………….……...…..9

   1.7. Сбалансированные деревья поиска…………………………...…………..10

  1.7.1. Сбалансированные АВЛ-деревья поиска……………...…………..……10

  1.7.2. Рандомизированные деревья поиска……………………………..……..11

   1.8. Операции над деревьями………………………………………….………11

   2. Практическая часть……………………………………………….……..…..17

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

  Список используемой литературы……………………...……………….……..26 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

     Введение 

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

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

             Целью работы является:

-  Рассмотреть способы построения и представления деревьев

       Задача  данной работы:

• Изучить сведения о деревьях
• Изучить основные операции над деревьями
• Закрепить теоретические и практические знания по программированию на С++

 
 
 
 
 
 
 
 
 
 
 
 
 
 
     

1. Теоретическая часть.

 

1. Рекурсии

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

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

     Рекурсивную процедуру Р можно представить как некоторую композицию Р из множества операторов S, не содержащих Р, и самой Р:

     Р => P[S,P].

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

     Р => if В then P[S,P] или Р => P[S, if В then Р].

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

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

2. Общие сведения о деревьях

 

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

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

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

     Древовидная структура с базовым типом Т— это либо 1) пустая структура, либо 2) узел типа Т, с которым связано конечное число древовидных структур с базовым типом Т, называемых поддеревьями. Верхний узел называется корнем.

     Число поддеревьев данного узла образует степень узла, максимальное значение m степени всех узлов дерева является степенью дерева. Дерево степени m называется m-арным деревом. Если все узлы дерева, кроме листьев, имеют степень, равную т, то такое дерево называется полным т-арным деревом. Дерево степени 2 называется бинарным (двоичным) деревом. Оно также может быть полным и неполным.

     Если в дереве на каждом уровне задан порядок следования вершин, то такое дерево называется упорядоченным деревом. Обычно деревья считаются упорядоченными, порядок следования вершин любого узла считается заданным слева направо. Каждая вершина m-арного дерева может быть представлена строкой символов над алфавитом {0,1,..., т-1}, при этом корень дерева характеризуется пустой строкой. Узлам первого уровня приписываются односимвольные строки 0,l,...,m-1, узлам второго уровня — двухсимвольные строки, узлы i-го уровня характеризуются строками длины i. Любая дочь вершины v характеризуется строкой, префикс которой является строкой узла v, к которой справа приписывается символ 0,1,...или т- 1 в зависимости от ее позиции в нижележащем от v уровне. Строка, приписанная к листу дерева, не является префиксом ни для каких других строк, характеризующих другие вершины дерева, т.е. является уникальной. Множество строк, соответствующих листьям некоторого дерева, образует префиксный код этого дерева.  

     1.3. Леса

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

     Лес может быть преобразован в бинарное дерево. Алгоритм преобразования леса в бинарное дерево схож с алгоритмом преобразования m-арного дерева. Сначала каждое дерево леса обрабатывается точно так же, как и отдельное дерево на первом этапе. Затем корни деревьев соединяются горизонтальными линиями и осуществляется поворот по часовой стрелке на 45 градусов относительно корня первого (левого) дерева. Таким образом, корнем леса, представленного бинарным деревом, становится корень первого дерева, второе дерево становится правым поддеревом корня первого, третье дерево — правым поддеревом корня второго дерева и т.д.

     Представление m-арного дерева и леса бинарным деревом дает возможность однообразного физического представления деревьев в ЭВМ и облегчает их обработку. 

     1.4. Представление деревьев в памяти ЭВМ

     Элементы древовидной структуры могут быть размещены как в последовательной (векторной) памяти, так и в динамически получаемых областях памяти. Поскольку каждый узел дерева имеет логические связи со своими дочерними узлами, эти связи должны^I быть отражены и в физической структуре в явном или неявном виде. Рассмотрим бинарное дерево. При явном отражении связей каждый узел дерева имеет структуру вида:

     Данные — Левый указатель LPTR — Правый указатель RPTR.

     Здесь поля LPTR и RPTR содержат указатели на левое и правое поддеревья данного узла. Форма указателей может быть различной

     Представление дерева в векторной памяти допустимо только тогда, когда в процессе обработки объем памяти, занимаемой его элементами, не превышает фиксированного объема векторной памяти, т.е. число элементов дерева не может превышать некоторого предельного значения. Элементы дерева занимают последовательные ячейки векторной памяти. При явном задании связей указатели LPTR и RPTR можно задавать двояко: либо в виде индексов элементов вектора, либо их адресов в памяти.

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

     1.5. Идеально-сбалансированное бинарное дерево

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

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

     Если число узлов п известно и дана последовательность значений поля данных вершин а[0], а[1],… а[n-1], то можно использовать следующий рекурсивный алгоритм построения идеально сбалансированного дерева.

     1. Начиная с а[0], берем очередное значение a[i] в качестве зна- 
чения корня дерева (поддерева).

2. Строим левое поддерево с п1 = n/2 узлами тем же способом.
3. Строим правое поддерево с nr = n-nl-l узлами.

     Таким образом, значение а[0], окажется в корне дерева, и именно на него будет ссылаться указатель дерева, а[1],… а[nl],  значения попадут в левое поддерево, остальные — в правое поддерево. Следовательно, распределение значений по узлам дерева полностью определяется исходной последовательностью данных. 

     1.6.Бинарные (двоичные) деревья поиска

     Бинарные деревья чаще всего применяются для представления множеств данных, элементы которых ищутся по уникальному, только им присущему ключу. Если бинарное дерево организовано таким образом, что для каждого узла ti, все ключи в левом поддереве меньше ключа ti, а ключи в правом поддереве больше ключа ti, то это дерево называется бинарным деревом поиска. В дереве поиска можно найти место каждого ключа, двигаясь начиная от корня и переходя на левое или правое поддерево каждого узла в зависимости от значения ключа. Таким образом, места элементов в дереве распределяются как значениями ключей, так и последовательностью их поступления. Определяющим фактором является значение ключа, от последовательности поступления элементов зависит степень сбалансированности дерева. При случайном распределении ключа в исходной последовательности получается почти сбалансированное дерево. Если же исходная последовательность упорядочена по возрастанию или убыванию ключей, то дерево вырождается в последовательный список. Высота такого дерева равна числу элементов дерева, уменьшенному на 1.

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