Реферат

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

Работа добавлена на сайт bukvasha.net: 2015-06-29

Поможем написать учебную работу

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

Предоплата всего

от 25%

Подписываем

договор

Выберите тип работы:

Скидка 25% при заказе до 9.11.2024


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

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

Двоичное дерево поиска может быть либо пустым, либо оно обладает таким свойством, что корневой элемент имеет большее значение узла, чем любой элемент в левом поддереве, и меньшее или равное, чем элементы в правом поддереве. Указанное свойство называется характеристическим свойством двоичного дерева поиска и выполняется для любого узла такого дерева, включая корень. Далее будем рассматривать только двоичные деревья поиска. Такое название двоичные деревья поиска получили по той причине, что скорость поиска в них примерно такая же, что и в отсортированных массивах: 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 infR);}

}

Реализуем функцию, возвращающую 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 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;

}

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


1. Реферат на тему Аттикa
2. Реферат на тему Christ VICTORY Essay Research Paper Christ VICTORY
3. Реферат на тему Platos Theory Of Knowledge Essay Research Paper
4. Реферат Экономическая теория М. Фридмена
5. Реферат на тему Cafe At Night Essay Research Paper Caf
6. Реферат на тему Punishment Essay Research Paper Punishment by Rabindranath
7. Реферат Climate and Weather in Great Britain Климат и погода в Великобритании
8. Реферат на тему Монтажная микросварка
9. Реферат Определить себестоимость 1 Гкал тепловой энергии на проектируемой промышленной котельной и устан
10. Реферат Проблема бюджетного федерализма в России