Реферат : Динамические структуры данных: двоичные деревья 


Полнотекстовый поиск по базе:

Главная >> Реферат >> Информатика, программирование


Динамические структуры данных: двоичные деревья




Динамические структуры данных: двоичные деревья

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

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

Двоичное дерево поиска может быть либо пустым, либо оно обладает таким свойством, что корневой элемент имеет большее значение узла, чем любой элемент в левом поддереве, и меньшее или равное, чем элементы в правом поддереве. Указанное свойство называется характеристическим свойством двоичного дерева поиска и выполняется для любого узла такого дерева, включая корень. Далее будем рассматривать только двоичные деревья поиска. Такое название двоичные деревья поиска получили по той причине, что скорость поиска в них примерно такая же, что и в отсортированных массивах: O(n) = C • log2n (в худшем случае O(n) = n).

Пример. Для набора данных 9, 44, 0, –7, 10, 6, –12, 45 построить двоичное дерево поиска.

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

Выделим типовые операции над двоичными деревьями поиска:

добавление элемента в дерево;

удаление элемента из дерева;

обход дерева (для печати элементов и т.д.);

поиск в дереве.

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

Пусть двоичное дерево поиска описывается следующим типом

Type BT=LongInt; U = ^BinTree; BinTree = Record Inf : BT; L, R : U End;

Покажем два варианта добавления элемента в дерево: итеративный и рекурсивный.

{Итеративный вариант добавления элемента в дерево, Turbo Pascal}

Procedure InsIteration(Var T : U; X : BT);

Var vsp, A : U;

Begin

New(A); A^.Inf := X; A^.L:=Nil; A^.R := Nil;

If T=Nil Then T:=A

Else Begin vsp := T;

While vsp <> Nil Do

If A^.Inf < vsp^.Inf

Then

If vsp^.L=Nil Then Begin vsp^.L:=A; vsp:=A^.L End Else vsp:=vsp^.L

Else

If vsp^.R = Nil Then Begin vsp^.R := A; vsp:=A^.R End Else vsp := vsp^.R;

End

End;

{Рекурсивный вариант добавления элемента в дерево, Turbo Pascal}

Procedure InsRec(Var Tree : U; x : BT);

Begin

If Tree = Nil

Then Begin

New(Tree);

Tree^.L := Nil;

Tree^.R := Nil;

Tree^.Inf := x

End

Else If x < Tree^.inf

Then InsRec(Tree^.L, x)

Else InsRec(Tree^.R, x)

End;

Аналогично на C++.

typedef long BT;

struct BinTree{

BT inf;

BinTree *L; BinTree *R;

};

/* Итеративный вариант добавления элемента в дерево, C++ */

BinTree* InsIteration(BinTree *T, BT x)

{ BinTree *vsp, *A;

A = (BinTree *) malloc(sizeof(BinTree));

A->inf=x; A->L=0; A->R=0;

if (!T) T=A;

else {vsp = T;

while (vsp)

{if (A->inf < vsp->inf)

if (!vsp->L) {vsp->L=A; vsp=A->L;}

else vsp=vsp->L;

else

if (!vsp->R) {vsp->R=A; vsp=A->R;}

else vsp=vsp->R;

}

}

return T;

}

/* Рекурсивный вариант добавления элемента в дерево, C++ */

BinTree* InsRec(BinTree *Tree, BT x)

{

if (!Tree) {Tree = (BinTree *) malloc(sizeof(BinTree));

Tree->inf=x; Tree->L=0; Tree->R=0;

}

else if (x < Tree->inf) Tree->L=InsRec(Tree->L, x);

else Tree->R=InsRec(Tree->R, x);

return Tree;

}

Существует несколько способов обхода (прохождения) всех узлов дерева. Три наиболее часто используемых из них называются обход в прямом (префиксном) порядке, обход в обратном (постфиксном) порядке и обход во внутреннем порядке (или симметричный обход). Каждый из обходов реализуется с использованием рекурсии.

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

{Turbo Pascal}

Procedure PrintTree(T : U);

begin

if T <> Nil

then begin PrintTree(T^.L); write(T^.inf : 6); PrintTree(T^.R) end;

end;

// C++

void PrintTree(BinTree *T)

{

if (T) {PrintTree(T->L); cout << T->inf<< " "; PrintTree(T->R);}

}

Реализуем функцию, возвращающую true (1), если элемент присутствует в дереве, и false (0) — в противном случае.

{Turbo Pascal}

function find(Tree : U; x : BT) : boolean;

begin

if Tree=nil then find := false

else if Tree^.inf=x then Find := True

else if x < Tree^.inf

then Find := Find(Tree^.L, x)

else Find := Find(Tree^.R, x)

end;

/* C++ */

int Find(BinTree *Tree, BT x)

{ if (!Tree) return 0;

else if (Tree->inf==x) return 1;

else if (x < Tree->inf) return Find(Tree->L, x);

else return Find(Tree->R, x);

}

По сравнению с предыдущими задача удаления узла из дерева реализуется несколько сложнее. Можно выделить два случая удаления элемента x (случай отсутствия элемента в дереве является вырожденным):

1) узел, содержащий элемент x, имеет степень не более 1 (степень узла — число поддеревьев, выходящих из этого узла);

2) узел, содержащий элемент x, имеет степень 2.

Случай 1 не представляет сложности. Предыдущий узел соединяется либо с единственным поддеревом удаляемого узла (если степень удаляемого узла равна 1), либо не будет иметь поддерева совсем (если степень узла равна 0).

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

{Turbo Pascal}

function Delete(Tree: U; x: BT) : U;

var P, v : U;

begin

if (Tree=nil)

then writeln('такого элемента в дереве нет!')

else if x < Tree^.inf then Tree^.L := Delete(Tree^.L, x) {случай 1}

else

if x > Tree^.inf

then Tree^.R := Delete(Tree^.R, x) {случай 1}

else

begin {случай 1}

P := Tree;

if Tree^.R=nil

then Tree:=Tree^.L

else if Tree^.L=nil

then Tree:=Tree^.R

else begin

v := Tree^.L;

while v^.R^.R <> nil do v:= v^.R;

Tree^.inf := v^.R^.inf;

P := v^.R;

v^.R :=v^.R^.L;

end;

dispose(P);

end;

Delete := Tree

end;

{C++}

BinTree * Delete(BinTree *Tree, BT x)

{ BinTree* P, *v;

if (!Tree) cout << "такого элемента в дереве нет!" << endl;

else if (x < Tree->inf) Tree->L = Delete(Tree->L, x);

else if (x > Tree-> inf) Tree->R = Delete(Tree->R, x);

else {P = Tree;

if (!Tree->R) Tree = Tree->L; // случай 1

else if (!Tree->L) Tree = Tree->R; // случай 1

else { v = Tree->L;

while (v->R->R) v = v->R; // случай 2

Tree->inf = v->R->inf;

P = v->R; v->R = v->R->L;

}

free(P);

}

return Tree;

}

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

Список литературы

Для подготовки данной работы были использованы материалы с сайта http://comp-science.narod.ru

Похожие работы:

  • Структуры данных

    Реферат >> Математика
    ... 1; в двоичном или бинарном дереве она соответсвенно равна 2. Перечисление бинарных деревьев. Попробуем подсчитать число двоичных деревьев ... мы уже сталкивались когда рассматривали динамические структуры данных. Когда мы не можем фиксировать ...
  • Динамические структуры данных

    Лабораторная работа >> Информатика, программирование
    ... в динамической памяти структура (рис.1б). Рис.1. Двоичное дерево и его представление с помощью списочных структур памяти а - двоичное дерево; б - представление дерева ... роботи програми. Висновок Динамічні структури даних дозволяють гнучкіше та ширше ...
  • Алгоритмы и структуры данных. Программирование в Cи

    Реферат >> Информатика, программирование
    ... чисел в компьютере является двоичная. Недостатком этой системы является ... цифр при изображении длинных двоичных чисел. Поэтому в информатике ... корни деревьев. Бинарное дерево можно изобразить следующим образом: Таким образом, динамические структуры данных, ...
  • Ссылочные типы. Динамические переменные

    Курсовая работа >> Информатика, программирование
    ... ); writeln( Formula( Source ) ); end. 4. Двоичные деревья Элементы двоичного дерева помимо информативной части имеют две ... этом, для представления дерева рекурсивной динамической структурой целесообразно модифицировать описание типа дерева, данное выше. А ...
  • Структура рабочей сети Internet

    Дипломная работа >> Информатика, программирование
    ... инфологических моделей. Реляционная структура данных В конце 60-х ... с базами данных; возможность динамического определения данных; поддержка ... отношений связанных данных. Например - дерево директорий. ... первый тип файла - двоичный - хранит образ формы ...
  • Структура рабочей сети Internet

    Реферат >> Компьютерные науки
    ... моделей. 1.2.4Реляционная структура данных В конце 60-х ... с базами данных; возможность динамического определения данных; поддержка ... отношений связанных данных. Например - дерево директорий. TStringGrid ... , причем первыйтип файла - двоичный - хранит образ формы и ...
  • Технический словарь

    Топик >> Иностранный язык
    ... преобразование из двоичного (представления) в десятичное binary tree двоичное дерево binding ... (ориентированное) дерево 2. (неориентированное) дерево 3. дерево (структура данных, представляющая дерево) tree grammar грамматика деревьев tree index древовидный ...
  • VB, MS Access, VC++, Delphi, Builder C++ принципы(технология), алгоритмы программирования

    Реферат >> Информатика, программирование
    ... элемент на его новое место. Динамические структуры данных позволяют быстро и легко выполнять такого ... с двоичными деревьями. Например, можно преобразовать двоичное отношение «меньше» в двоичное дерево. Если использовать внутренние узлы дерева для ...
  • Алгоритмические языки и программирование

    Реферат >> Информатика, программирование
    ... как все данные занесены в двоичное дерево сортировки, выполняется обратный обход дерева с выводом. Деревья применяются ... С.М.Юдин, Инструментальная система ИНФОРТ и работа с динамическими структурами данных, М., издательство МАИ, 1984. 9. Лекции, семинары ...
  • Ответы на вопросы по курсу “Системное программирование”

    Шпаргалка >> Информатика, программирование
    ... операции. Указатели и динамические структуры данных: стеки, списки, очереди, деревья. Указатель – тип данных, хранящих адрес в памяти ... NULL NULL NULL Структура двоичного дерева. Каждый элемент содержит поле данных и два указателя - на ...