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

Содержание

 

 

ВВЕДЕНИЕ

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

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

Объектом разработки в курсовой работе является структура  данных – бинарное дерево поиска.

Целью работы является изучение данной структуры, а затем разработка приложения на языке программирования Pascal с её реализацией .

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

 

 

1.Общие сведения  о бинарных деревьях.

 

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

Рис.1 "Пример бинарного дерева"

 

На рисунке показан  общепринятый способ изображения бинарного  дерева. Это дерево состоит из семи узлов, и А-корня дерева. Его левое поддерево имеет корень В, а правое - корень С. Это изображается двумя ветвями, исходящими из А: левым - к В и правым - к С. Отсутствие ветви обозначает пустое поддерево. Например, левое поддерево бинарного дерева с корнем С и правое поддерево бинарного дерева с корнем Е оба пусты. Бинарные деревья с корнями D, G, Н и F имеют пустые левые и правые поддеревья.

Если А - корень бинарного  дерева и В - корень его левого или  правого поддерева, то говорят, что А-отец В, а В-левый или правый сын А. Узел, не имеющий сыновей (такие как узлы D, G, Н и F), называется листом.

Узел nl - предок узла n2 (а n2-потомок nl), если nl-либо отец n2, либо отец некоторого предка n2.

Узел n2-левый потомок  узла n1, если n2 является либо левым сыном n1, либо потомком левого сына n1. Похожим образом может быть определен правый потомок.

Два узла являются братьями, если они сыновья одного и того же отца. Если каждый узел бинарного  дерева, не являющийся листом, имеет  непустые правые и левые поддеревья, то дерево называется строго бинарным деревом. Строго бинарное дерево с n листами всегда содержит 2n-1 узлов.

Пример строго бинарного  дерева приведен на рисунке ниже.

Рис.2 "Строго бинарное дерево"

 

Уровень узла в бинарном дереве может быть определен следующим образом. Корень дерева имеет уровень 0, и уровень любого другого узла дерева имеет уровень на 1 больше уровня своего отца. Например, в бинарном дереве на первом рисунке узел Е - узел уровня 2, а узел Н-уровня 3. Глубина бинарного дерева - это максимальный уровень листа дерева, что равно длине самого длинного пути от корня к листу дерева. Стало быть, глубина дерева на первом рисунке равна 3.

Полное бинарное дерево уровня n - это дерево, в котором  каждый узел уровня n является листом и каждый узел уровня меньше n имеет непустые левое и правое поддеревья.

На рисунке приведен пример полного  бинарного дерева.

Рис.3 "Полное бинарное дерево"

 

Почти полное бинарное дерево - это бинарное дерево, для которого существует неотрицательное целое k такое, что:

1. Каждый лист в  дереве имеет уровень k или  k+1.

2. Если узел дерева имеет правого  потомка уровня k+1, тогда все его        левые потомки, являющиеся листами,  также имеют уровень k+1.

Есть еще одна разновидность  бинарных деревьев, которая называется дерево поиска. Это двоичное дерево организовано так, что для каждой вершины справедливо утверждение, что все ключи левого поддерева меньше ключа , а все ключи правого поддерева больше его, то такое дерево будем называть деревом поиска. В таком дереве легко обнаружить заданный элемент, для этого достаточно, начав с корня, двигаться к левому или правому поддереву на основании лишь одного сравнения с ключом текущей вершины. Дерево поиска для заданной последовательности целых чисел 23, 17, 26, 32, 18, 6, 2, 5, 8, 29, 146 имеет вид:

Рис.4 "Бинарное дерево поиска"

1.1.Операции  над бинарными деревьями

 
Бинарное  дерево должно реализовывать следующие операции:

1. Инициализация бинарного дерева: 
   текущий указатель устанавливается неопределенным (или нулевым, nil), а количество узлов нулевым.
2. Помещение в бинарное дерево элемента: 
   для нового элемента в бинарном дереве создается соответствующий узел, указатели на потомков которого пусты (поиск позиции для такого узла начинается с корня и проходит согласно правилам, определяющим структуру бинарного дерева).
3. Получение значения текущего элемента
4. Поиск заданного элемента: 
   если искомый элемент находится в дереве, то возвращается указатель на него, в противном случае возвращается nil, сигнализирующий о неуспехе поиска значения.
5. Удаление узла из дерева
6. Уничтожение бинарного дерева

1.2.Представление  бинарных деревьев.

 

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

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

Рис.5. Представление бинарного дерева в виде списковой структуры

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

Рис.6. Представление бинарного дерева в виде массива

 

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

Однако далеко не все  бинарные деревья являются полными. Для неполных бинарных деревьев применяют  следующий способ представления. Бинарное дерево дополняется до полного дерева, вершины последовательно нумеруются.

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

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

адрес = 2к-1+i-1,

где k-номер уровня вершины, i- номер на уровне k в полном бинарном дереве. Адрес корня будет равен единице. Для любой вершины можно вычислить адреса левого и правого потомков

адрес_L = 2к+2(i-1)

адрес_R = 2к+2(i-1)+1

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

1.3.Применение.

 

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

1.4.Способы  прохождения (или обхода) бинарного  дерева.

 

Над бинарным деревом  есть операция - его прохождение, т.е. нужно обойти все дерево, отметив  каждый узел один раз. Прохождение (или обход) бинарного дерева означает систематическое перечисление всех узлов для выполнения необходимой функциональной обработки. Наиболее известны и практически важны 3 способа прохождения, которые отличаются порядком и направлением обхода бинарного дерева. Можно проходить узлы в прямом порядке (сверху - вниз), в симметричном порядке (слева -направо) и, наконец, в концевом порядке(снизу-вверх).

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

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

• Попасть в корень,
• Пройти все поддеревья слева на право в прямом порядке.

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

• Пройти левое поддерево,
• Попасть в корень,
• Пройти следующее за левым поддерево.
• Попасть в корень и т.д. пока не будет пройдено крайнее правое поддерево.

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

• Пройти все поддеревья слева на право,
• Попасть в корень.

 

Рис.7. Траектория обхода бинарного дерева.

 

 

 

 

2.Алгоритм поиска  по бинарному дереву.

 

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

Рис.8. Фрагмент бинарного дерева поиска.

 

В приведенном рисунке  фрагмента бинарного дерева поиска ключ узла "В" меньше ключа узла "А", а ключ узла "С"больше ключа узла "А", т. е.  
         key(B) < key(A)      и       key(C) > key(A)  
Правило сравнения ключей определяется типом ключевых данных. Скалярные ( например, целочисленные) ключи упорядочиваются естественным образом по их величинам. Векторные ( например, символические) ключи упорядочиваются лексиграфически. Лексиграфический порядок образует упорядочивание векторов последовательно по величинам компонент. 

Например. вектор V=(V1,..,Vj,..,Vp) лексиграфически больше, чем вектор W=(W1,..,Wj,..,Vp), если Vj=Wj при j<q и Vq>Wq. 

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

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

Алгоритм:

• Если дерево пусто, сообщить, что узел не найден, и остановиться.
• Иначе сравнить K со значением ключа корневого узла X.
• Если K=X, выдать ссылку на этот узел и остановиться.
• Если K>X, рекурсивно искать ключ K в правом поддереве Т.
• Если K<X, рекурсивно искать ключ K в левом поддереве Т.

 

 

3.Разработка  программы

 

Процедура добавления элемента

 

procedure AddToTree (var Tree:PNode;x:integer); {Входные параметры - адрес корня дерева и добавл элемент }

begin

if Tree=nil then  {Если дерево пустое то создаём его корень}

   begin

     New(Tree);   {Выделяем память }

     Tree^.data:=x;     {Добавляем данные }

     Tree^.left:=nil;     {Зануляем указатели на левого }

     Tree^.right:=nil;  {и правого сыновей }

      exit;

   end;

if x < Tree^.data then   {Доб к левому или правому поддереву это завсит от вводимого элемента}