русс | укр

Языки программирования

ПаскальСиАссемблерJavaMatlabPhpHtmlJavaScriptCSSC#DelphiТурбо Пролог

Компьютерные сетиСистемное программное обеспечениеИнформационные технологииПрограммирование

Все о программировании


Linux Unix Алгоритмические языки Аналоговые и гибридные вычислительные устройства Архитектура микроконтроллеров Введение в разработку распределенных информационных систем Введение в численные методы Дискретная математика Информационное обслуживание пользователей Информация и моделирование в управлении производством Компьютерная графика Математическое и компьютерное моделирование Моделирование Нейрокомпьютеры Проектирование программ диагностики компьютерных систем и сетей Проектирование системных программ Системы счисления Теория статистики Теория оптимизации Уроки AutoCAD 3D Уроки базы данных Access Уроки Orcad Цифровые автоматы Шпаргалки по компьютеру Шпаргалки по программированию Экспертные системы Элементы теории информации

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


Дата добавления: 2013-12-23; просмотров: 3888; Нарушение авторских прав


Многосвязные списки

 

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

Переход между звеньями АА и БА может выполнен по дополнительной связи, в обход звеньев АБ и АВ. Из-за такого характера перемещения эти списки иногда называют скип-списками (skip - перепрыгивать). А при характере размещения данных, подобном показанному на этом рисунке, такие списки называют словарными (иногда просто словарями, но термин "словарь" может использоваться в теории структур данных в разных значениях).

 

Типы деревьев: Двоичные (бинарные), ориентированные, упорядоченные, мультивариантные (дерево Байера).

 

Дерево - динамическая нелинейная структура данных, каждый элемент которой содержит собственно информацию (или ссылку на то место в памяти ЭВМ, гди хранится информация) и ссылки на несколько (не менее двух) других таких же элементов. Для бинарного дерева таких ссылок две: на правый соседний и левый соседний элементы.

 

Основные операции, выполняемые над деревьями (те же, что и над списками) - вставка, удаление и поиск элементов.

 

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

 

Чем же отличается бинарное дерево от двусвязного списка? Иногда ничем, не только от двусвязного, но и от односвязного списка. Основное отличие - у списка соседними являются предшествующий и последующий элементы, и структура линейна; а у бинарного дерева соседними являются элементы с меньшим и большим ключом, и структура, в общем случае ветвящаяся - в виде дерева, откуда она и получила свое название.



 

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

Этой структуре соответствует набор типов языка Паскаль:

 

type

info=(* тип хранимых данных *);

ptr=^node;

node=record

key:Integer;

left,right:ptr;

data:^info

end;

var

tree:ptr;

 

Бинарное дерево, образованное такими элементами показано там же.

Элемент дерева получил название "узел" (node), иногда его называют листом. Единственный начальный элемент (откуда дерево развивается) - корень (root). Фрагмент (часть) дерева - поддерево или ветвь. Узел, от которого не отходят ветви - конечный или терминальный узел. Количество уровней - высота дерева.

 

 

Применение деревьев: для хранения информации, как таковой; в процедурах поиска; для организации файлов на дисковых носителях; в построении эффективных кодов для сжатия информации (коды Шеннона-Фано и Хаффмэна).

 

 

Рассмотрим принцип построения дерева при занесении в него информации. Пусть последовательно вводятся записи с ключами 70, 60, 85, 87, 90, 45, 30, 88, 35, 20, 86, 82.

1. Корень - 70;

2. 60<70, следовательно новый узел будет расположен слева от 70;

3. 85>70, следовательно новый узел будет расположен справа от 70;

4. 87>70, следовательно 87 будет находиться в правой ветви; 87>85, следовательно 87 будет расположен справа от 85. И т. д.

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

 

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

 

 

Существует три способа прохождения дерева:

1. Последовательный - дерево проходится, начиная с левой ветви вверх к корню, затем к правой ветви;

2. Нисходящий - от корня к левой ветви, затем к правой;

3. Восходящий - проходится левая ветвь, затем правая, затем корень.

 

 

 

 

Под корнем здесь понимается как корень всего дерева, так и корень текущей ветви (поддерева).

 

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

 

Порядок сортировки дерева определяется методом, которым дерево будет проходиться.

 

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

 

Сбалансированное бинарное дерево - максимально широкое и низкое.

 

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

 

Если данные случайны, то получается дерево, приближенное к сбалансированному.

 

Дерево - рекурсивная структура данных, так как любое поддерево - это тоже дерево. В связи с этим, наиболее эффективными при работе с деревьями оказываются рекурсивные процедуры. Хотя возможно применение и процедур без рекурсии. Рассмотрим разные варианты построения этих процедур.

Рекурсивная процедура добавления узла в дерево на языке "Паскаль"

 

procedure addnode_r(r,prev:ptr; newkey:integer);

begin

if r=nil then

begin

new(r);

r^.left:=nil;

r^.right:=nil;

r^.key:=newkey;

if tree=nil then

tree:=r; {Первый узел}

else

begin

if newkey<prev^.key then

prev^.left:=r

else

prev^.right:=r

end;

exit

end;

if newkey<r^.key then

addnode_r(r^.left,r,newkey)

else

addnode_r(r^.right,r,newkey)

end;

 

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

Аргументы процедуры:

указатель на корень дерева или ветви, в котором ищется место для нового узла;

указатель на предыдущий узел;

ключ;

Сохраняемые данные или указатель на них.

 

При первом вызове второй аргумент может быть равен nil.

 

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

Рекурсивная функция построения идеально сбалансированного дерева с заданным числом узлов на языке "Паскаль"

 

function maketree(n_node:integer):ptr;

var

newnode:ptr;

newkey,nl,nr:integer;

begin

if n_node=0 then

newnode:=nil

else

begin

nl:=n_node div 2;

nr:=n_node-nl-1;

{Ввод ключа и данных}

read(newkey);

new(newnode);

with newnode^ do

begin

key:=newkey;

left:=maketree(nl);

right:=maketree(nr)

end;

end;

maketree:=newnode

end;

 

read(n);

tree:=maketree(n);

{Первый вызов}

 

Рекурсивные процедуры прохождения дерева в последовательном (inorder), нисходящем (preorder) и восходящем (postorder) порядках на языке "Паскаль"

 

procedure inorder(r:ptr);

begin

if r=nil then exit;

inorder(r^.left);

writeln( ... ); {Вывод информации}

inorder(r^.right)

end;

 

procedure preorder(r:ptr);

begin

if r=nil then exit;

writeln( ... ); {Вывод информации}

preorder(r^.left);

preorder(r^.right)

end;

 

procedure postorder(r:ptr);

begin

if r=nil then exit;

postorder(r^.left);

postorder(r^.right)

writeln( ... ); {Вывод информации}

end;

 

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

 

Возможно добавление нового узла в дерево и без использования рекурсии:

Нерекурсивная процедура добавления нового узла в дерево на языке "Паскаль"

 

procedure addnode2(skey:integer; var tree:ptr; newdata:^info);

var

r,s:ptr;

t:^info;

begin

if not searchtree(skey,tree,r) then

begin

new(t); {Занесение}

t:=newdata; {данных}

new(s); {новый}

s^.key:=skey;

s^.left:=nil; {узел}

s^.right:=nil;

s^.data:=t;

if tree=nil then

tree:=s

else

if skey<r^.key then

r^.left:=s

else

r^.right:=s

end

end;

 

 

Поиск в бинарных деревьях выполняется достаточно просто:

Программа поиска в бинарном дереве на языке "Паскаль"

 

function search_tree(skey:integer; var tree,fnode:ptr):boolean;

var

p,q:ptr;

b:boolean;

begin

b:=false;

p:=tree;

if tree<>nil then

repeat

q:=p;

if p^.key=skey then

b:=true

else

begin

if skey<p^.key then

p:=p^.left

else

p:=p^.right

end

until (b) or (p=nil);

search_tree:=b;

fnode:=q;

end;

 

Длительность поиска зависит от структуры дерева. Для сбалансированного дерева (изображено на рисунке) поиск аналогичен двоичному - то есть нужно посмотреть не более Log2N узлов.

Для вырожденного дерева (изображено на рисунке) поиск аналогичен поиску в односвязном списке – в среднем нужно посмотреть половину узлов.

Удаление узла из дерева - существенно более сложный процесс, чем поиск, так как удаляемый узел может быть корневым, левым или правым. Узел может давать начало другим деревьям (их может быть от 0 до двух).

 

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

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

 

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

 

Такой узел может иметь не более одной ветви.

Пример удаления из дерева узла с ключом 50.

Процедура удаления узла должна различать три случая:

- узла с данным ключом в дереве нет;

- узел с заданным ключом имеет не более одной ветви;

- узел с заданным ключом имеет две ветви.

 

Процедура удаления узла (автор - Н. Вирт)

Процедура удаления узла двоичного дерева на языке "Паскаль"

 

procedure delnode(var d:ptr; key:integer);

var

q:ptr;

 

procedure del1(var r:ptr);

begin

if r^.right=nil then

begin

q^.key:=r^.key;

q^.data:=r^.data;

q:=r;

r:=r^.left

end

else

del1(r^.right)

end;

 

begin

if d=nil then exit {Первый случай}

else

if key<d^.key then

delnode(d^.left,key)

else

if key>d^.key then

delnode(d^.right,key)

else

begin

q:=d; {Второй случай}

if q^.right=nil then

d:=q^.left

else

if q^.left=nil then

d:=q^.right

else {Третий случай}

del1(q^.left)

end

end;

 

Вспомогательная рекурсивная процедура del1 вызывается только в третьем случае. Она проходит дерево до самого правого узла левого поддерева, начиная с удаляемого узла q^, и заменяет значения полей key и data в q^ соответствующими записями полей узла r^. После этого узел, на который указывает r можно исключить (r:=r^.left).

 

 



<== предыдущая лекция | следующая лекция ==>
Кольцевые списки | Учебно-методические материалы по дисциплине


Карта сайта Карта сайта укр


Уроки php mysql Программирование

Онлайн система счисления Калькулятор онлайн обычный Инженерный калькулятор онлайн Замена русских букв на английские для вебмастеров Замена русских букв на английские

Аппаратное и программное обеспечение Графика и компьютерная сфера Интегрированная геоинформационная система Интернет Компьютер Комплектующие компьютера Лекции Методы и средства измерений неэлектрических величин Обслуживание компьютерных и периферийных устройств Операционные системы Параллельное программирование Проектирование электронных средств Периферийные устройства Полезные ресурсы для программистов Программы для программистов Статьи для программистов Cтруктура и организация данных


 


Не нашли то, что искали? Google вам в помощь!

 
 

© life-prog.ru При использовании материалов прямая ссылка на сайт обязательна.

Генерация страницы за: 0.012 сек.