Нелинейные динамические структуры
Дерево: граф без циклов.
Рекурсивная программа: программа, в результате вычислений обращающаяся сама к себе.
Представление бинарных деревьев:
прав nil лев nil B nil A nil nil nil лев лев C D E
Способы обхода дерева.
сверху-вниз(рекурсивное правило)
+посетить корень
+ посетить лев. поддерево.
+ посетить прав. поддерево.
симметричный способ
+ посетить лев. поддерево.
+посетить корень
+ посетить прав. поддерево.
снизу-вверх
+ посетить лев. поддерево.
+ посетить прав. поддерево.
+посетить корень
в ширину
+посетить корень
+посетить вершину, отстоящую от корня на единицу по 1му ребру
+посетить вершину, отстоящую от корня на единицу по 2му ребру
Сортировка с использованием стека:
f:=1;
s[1]:=root;
while t<>0 do{ }
Begin
p:=s[t];
t:=t-1;
write(p^key,’ ‘);
If p^r<>nil then
Begin
t:=t+1;
s[t]:p^r;
End;
If p^l<>nil then
Begin
t:=t+1;
s[t]:=p^l;
End;
Задача : дано n – целое кол- во вершин бинарного дерева; построить сбалансированную матрицу.
Type
ref=^T;
T=record;
key:integer;
l,r:ref;
End;
Var
N:integer;
root:ref;
Function TREE(N:integer):ref;
Var
nl,nr,k:integer;
r:ref;
Begin
If N=0 then
tree:=nil;
Else
Begin
nl:=Ndiv2;
nr:=N-nl-1;
Writeln(‘введите ключ’);
Readln(x);
new(p);
p^key:=x;
p^l:=tree(nl);
p^r:=tree(nr);
tree:=p;
End;
End;{TREE}
Procedure PRINT(t:ref);
Begin
If t<> nil then
Write(t^key);
Print(t^l);
Print(t^r);
End;{PRINT}
{ОСНОВНАЯ ПРОГРАММА}
BEGIN
Writeln(‘введите кол-во вершин бинарного дерева’);
Read(N);
root:=tree(n);
PRINT(root);
END.
Задачи поиска
Ставят обычно по отношению к базе данных. Надо найти некую запись в базе. Если ключ принадлежит записи – внутренний ключ. Ключ определяет однозначно запись:
S={a1…an} T<=S(мн-во(таблица))
Написать алгоритм, к-рый определяетa S;про таблицу Т ничего не известно=>задача последовательного поиска:
Посл.поиск:написать алгоритм, к-рый передвигает эл-ты в начало.
Эл-ты упорядоченны в таблице=>применим бинарный поиск( делимТ/2, выбираем средний эл-т, сравниваем его)
f,l-начало, конец
k=a[(f+l)div2];
if k=a then эл-т
if k>a then f:(f+l)div2
if k<a then :(f+l)div2+1,1
T={ai1,…,aik}
p(ai1),…,p(aik)
статистика по числу обращений.
Упоряд.эл-ты в таблице.
Число обращений на число сравнений(функциональная стоимость)
P(aij)j j=1
Доказать, что функциональная стоимость достигаетmin если упорядоченна Т по числу обращений объединяет 2 случая-2 и 3. Сложность алгоритма –n. h=0 n=1 средний 2n-вершина дерева. эл-т 20+21+…+2n<2n+1-1
2n+1-1=k;
2n+1=k+1;
n+1=log2(k+1)-1
Ограничения:
известно, что эл-ты упорядоченны;
и
a
звестно частота обращения к Т и частота для каждого элемента. Т- упорядочена по эл-тамжключ лежит посередине множества=> строим бинарное дерево.
a
b 0
p(a)=3 q(1)=0 1
p
c 1
p
a 3 частота
удачных обращений частота
неудачных обращений
3*1+1*2+1*3=8
3*2+1*1+1*2=9
Бинарное дерево оптимального поиска
Tij-{ai+1,…,aj}-дерево с индексами i и j.
rij-корень Тij
сij-стоимость //
wij-dtc
wij=q(i)+(p(ai+1))+q(i+1)+…+p(aj)+q(j)
Изменим высоту на ед.
Если в качестве корня деева Тij использовать ak k>=j+1, k<=j, то стоимость дерева Тij=сjk=стоимость дерева Тj,k-1.