53
edits
Changes
→Aplicação de Árvores
== Aplicação de Árvores ==
Essa sessão foca no uso de árvores em árvores de busca binárias. Especificamente, chamamos o uso de árvores em algoritmos de busca binária assim como o uso de árvores em código Huffman. A razão pela qual desejamos usar árvores binárias é de que podemos usar a binary estrutura binária da árvore para tomar decisões binárias(ex: true/false) quanto a inserção ou procura de caminhos.
Uma árvore é chamada de árvore binária se todos os vértices na árvore tiverem no máximo dois filhos. Nesse capítulo, iremos utilizar árvores binárias ordenadas. A ordenação dos vértices é simplesmente a marcação dos filhos de um vértice como o filho a esquerda ou o filho a direita, onde o filho a esquerda é considerado o filho que deve ser visitado primeiro, e o da direita, o que deve ser visitado em segundo.
==='''Inserção binária'''===
Click here to access a summary of all the Maple code used in this section.
Um benefício crucial em árvores binárias ordenadas é de que o tempo de buscar exigido to para encontrar um específico elemento da árvore é logarítmico no número de vértices da árvore. A maior desvantegem é de que a inserção de um vértice é muito mais taxativa. Discutiremos estes em mais detalhe enquanto percorremos a própria impementação de um algoritmo de inserção binária.
Requerimos marcações no vértice. No Maple podemos utilizar o nome do vértice como marcação já que ele pode ser tanto inteiro como string.
Um vértice tipico na árvore tem dois descendentes (filhas). Devemos ser capazes de especificar quais desses dois vértices é o descendente da esquerda e qual é o da direita. Podemos indicar isso utilizando o peso do vértice. No Maple, cada vértice tem um peso padrão de 0, como demonstrado no simples exemplo:
<pre>
new(g): addvertex(1,2,g):
vweight(1,g);
</pre>
Podemos utilizar o peso do vértice para especificar uma ordenação da esquerda para a direita. Uma solução ainda mais simples é de simplesmente concordar que o peso do vértice é seu nome e impor uma ordenação nesses nomes.
Para comparar o nome de dois vértices, podemos utilizar um procedure como:
<pre>
IsLessThan := proc(a,b) local t;
if type( [a,b], [string,string]) then
t := sort( [a,b] , lexorder );
else
t := sort([a,b]);
fi;
if a = t[1] then true else false fi;
end:
</pre>
Usar essa comparação nos permite geralmente ignorar que tipo de marcação está sendo utilizada.
<pre>
IsLessThan(1,2); IsLessThan(b,a); IsLessThan(1,b);
</pre>
Ela também facilita a mudança do critério de comparação em outro ponto posterior, refazendo o código do algoritmo inteiro.
Também precisaremos ser capazes de achar a raiz da árvore. O seguinte procedure calcula tal raiz e força a árvore a lembrar sua raiz, para que a computação não precise ser repetida.
<pre>
FindRoot := proc(T::GRAPH)
local v, V;
V := vertices(T);
if not assigned( T(Root) ) then
for v in V do
if indegree(v,T) = 0 then
T(Root) := v; # remember the root
fi;
od;
if not assigned( T(Root) ) then
ERROR(`no root`) fi;
fi;
T(Root);
end:
</pre>
O procedure para construir uma árvore binária ordenadapor inserção é como o exemplo seguinte. Para facilitar, utilizamos o nome do vértice como seu valor quando fazemos comparação.
1. Dado um vértice v para inserir na árvore T, precisamos localizar o local correto na árvore T para inserir v.
2. Se a árvore T estiver vazia, inserir v como raiz.
3. Caso contrário, transforme a raiz da árvore na variável para o vértice atual cur_vertex, e compare v com cur_vertex. se v =cur_vertex, está feito.
4. se v <cur_vertex então procure o filho a esquerda, caso contrário, procure o filho a direita. Isso é feito mudando cur_vertex para ser o filho a esquerda ou a direita e comparando o novo cur_vertex com v.
5. Eventualmente, não seremos capazes de procurar na direção que a comparação diz que devemos ir. Nesse ponto, insira v como o filho não presente de cur_vertex.
A seguir, uma implementação detalhada do algoritmo:
<pre>
Binsertion := proc(T::graph, x::string,integer)
local cur_vertex, V, i, Kids, Left, Right;
V := vertices(T);
if nops(V) = 0 then
addvertex(x, T);
T(Root) := x ; # remember the root for later
RETURN( x );
fi;
</pre>
Temos uma árvore com raiz...
<pre>
cur_vertex := FindRoot(T);
while x <> cur_vertex do
</pre>
As ordenações relativas dos descendentes e x e cur_vertex determinam se x pode ser inserido como folha.
<pre>
Kids := daughter(cur_vertex,T);
Kids := sort( convert(Kids,list) , IsLessThan );
Candidates :=
sort( [ x, cur_vertex, op(Kids)], IsLessThan );
</pre>
Comece com casos fáceis
<pre>
if nops(Candidates) = 2 then
</pre>
não há filhos, então adicione apenas um novo filho.
<pre>
if IsLessThan(x,cur_vertex) then
addvertex(x,weight=`Lft`,T);
else
addvertex(x,weight=`Rht`,T);
fi;
addedge( [cur_vertex,x] , T);
cur_vertex := x;
break;
elif nops(Candidates)=4 then
</pre>
dois descendentes, então não há inserção nesse nível...
<pre>
if IsLessThan(x,cur_vertex)
then cur_vertex := Kids[1];
else cur_vertex := Kids[2]; fi;
next;
elif nops(Candidates) = 3 then
</pre>
não nesse nível se o padrão é [x,L,cur_vertex] ou [L,x,cur_vertex] [cur_vertex,L,x] ou [cur_vertex,x,L]
<pre>
if Candidates[1] = cur_vertex
or Candidates[3] = cur_vertex
then
cur_vertex := Kids[1];
next;
fi;
</pre>
Para todos os casos restantes adicione em x como um novo vértice
<pre>
if IsLessThan(x,cur_vertex) then
addvertex(x,weight=`Lft`,T);
else
addvertex(x,weight=`Rht`,T);
fi;
</pre>
Sim! Esse nível.
<pre>
addedge( [cur_vertex,x] , T);
cur_vertex := x;
break;
fi;
od;
RETURN( cur_vertex );
end:
</pre>
O procedure addvertex é usado aqui em uma maneira que atualiza os pesos de cada vértice na medida que ele é criado. Isso serve para indicar se é vértice é um descendente a esquerda ou a direita. Enquanto não usamos esses pesos, eles poderiam ser utilizados como uma medida alternativa para ordenação de descendentes de qualquer vértice particular.
Ao invés disso, para a ordenação, nós usamos os nomes dos vértices para indicar a ordenação relativa dos vértices. O fato de que qaiquer dois vértices (e não apenas descendentes do mesmo vértice) podem ser comparados nos permite combinar o novo vértice, os descendentes, e o vértice atual tudo em uma lista ordenada a qual é então inspecionada para determinar qual dos vários casos especiais é relevante durante a inserção de um novo vértice. Qualquer que seja o método de comparação de vértices que for utilizado, é importante que o procedure comparação seja passado na rotina de ordenação como um argumento extra.
Para validar esse procedure, examine como a seguinte lista de inteiros é adicionada:
<pre>
Num_List:=[4,6,2,8,5,3,7,1]:
new(Tree_Num):
for i from 1 to 8 do
Binsertion(Tree_Num, Num_List[i]);
od;
</pre>
Para ver a árvore resultante e sua estrutura, use o comando Mapledraw.
<pre>
draw(Tree(4), Tree_Num);
</pre>
O resultado é claramente uma árvore binária de busca.
Árvores binárias existem para serem procuradas. O seguinte procedure BiSearch faz isso. Declarações do tipo Print foram adicionadas para ilustrar o caminho que o algoritmo usa enquanto faz a busca na árvore.
<pre>
BiSearch := proc(T::graph, v)
local i, Kids, cur_vertex;
cur_vertex := FindRoot(T);
while v <> cur_vertex do
print(cur_vertex);
</pre>
verifique os casos fáceis
<pre>
if v = cur_vertex then RETURN(true); fi;
Kids := daughter(cur_vertex,T);
if Kids = {} then RETURN( false) fi;
</pre>
descendentes, então comece a procurar...
<pre>
Kids := sort( convert(Kids,list) );
Candidates :=
sort( [v , cur_vertex, op(Kids)], IsLessThan);
if nops(Candidates) = 4 then # both descendents
if IsLessThan(cur_vertex,v) then
cur_vertex := Kids[2];
else
cur_vertex := Kids[1];
fi;
next; # back to top of loop
elif nops(Candidates) = 3 then
</pre>
não está presente, a não ser que cur_vertex seja o primeiro ou último da lista
<pre>
if Candidates[1] <> cur_vertex
and Candidates[3] <> cur_vertex then
RETURN( false );
fi;
cur_vertex := Kids[1];
next;
fi;
od;
RETURN(true);
end:
</pre>
Para testar esse procedure, tentamos procurar por dois elementos, um que está na árvore e um que não está. Tree_Num;
<pre>
BiSearch(Tree_Num,8);
BiSearch(Tree_Num,12);
</pre>
==='''Codificação de Huffman'''===
A codificação de Huffman é um método para construir um código prefixo eficiente para um conjunto de caractéres. Ele é baseado num algoritmo ganancioso, onde em cada passo os vértices com menos peso são examinados. A codificação de Huffman pode produzir códigos de prefixo em condições óptimas. O seguinte pseudo-código descreve um algoritmo para codificação de Huffman. (Para uma discussão mais completa sobre a codificação de Huffman, veja Cormen, Leiserson, e Rivest, Introduction to Algorithms, MIT Press, 1989.)
Comece criando uma lista ordenada de elementos a serem codificados, onde a ordenação é com respeito a frequência de ocorrência desses elementos. Considere cada elemento da lista como um vértice com peso igual a sua frequência de ocorrência.
1. Remove os dois primeiros elementos, x e y, dessa lista;
2. Atribua x como o filho a esquerda e y como o filho a direita de um novo vértice em nossa árvore;
3. Atribua o peso de z para ser a soma dos pesos de x e y;
4. Insira z na posição correta de nossa lista, e repita o passo(2).
5. Quando completar, nossa lista deve conter apenas um elemento, que é uma árvore binária com raiz.
6. Novamente, uma rotina de comparação especial é necessária. Elementos do código são representados por listas como em [a,15] and [b,10]. O seguinte procedure HuffCompare compara dois de tais elementos.
<pre>
HuffCompare :=proc(a::list,b::list)
if a[2] <= b[2] then true else false fi;
end:
</pre>
Por examplo, descobrimos que [b,10] < [a,15].
<pre>
HuffCompare([b,10],[a,15]);
</pre>
Utilizando esse método de comparação, listas de códigos de elementos podem ser ordenadas em ordem crescente.
<pre>
sort( [[a,5],[b,10],[c,8],[d,11]], HuffCompare);
</pre>
O algoritmo de codificação de Huffman completo é implementado da seguinte maneira:
<pre>
Huffman:=proc(L::listlist)
local i, j, k, n, Q, T, x, y, z, Temp;
new(T);
Q := sort( L , HuffCompare ); i := 1;
while(nops(Q)>1) do
i := i+1;
</pre>
pegue os dois primeiros elementos de código
<pre>
x:=Q[1]; Q:=subsop(1=NULL, Q);
y:=Q[1]; Q:=subsop(1=NULL, Q);
</pre>
construa o novo vértice e sua localização
<pre>
z := [ i , x[2]+y[2]];
for j to nops(Q) while HuffCompare( z, Q[j]) do
j := j+1;
od; j := j-1;
</pre>
adicione os vértices e arestas a árvore
<pre>
Q := [seq(Q[k],k=1..j),z,seq(Q[k],k=j+1..nops(Q))];
addvertex([x[1],y[1],z[1]],weights=[x[2],y[2],z[2]],T);
addedge([z[1],x[1]],[z[1],y[1]],T);
od;
RETURN( eval(T) );
end:
</pre>
O tipo listlist denota uma lista de listas. O eval final é incluído para garantir que o resultado retornado pelo procedure é a própria árvore, e não apenas seu nome.
Teste esse novo procedure na seguinte lista de caractéres em inglês emparelhados com uma frequência relativa de ocorrência;
<pre>
Huf:=Huffman([[f,15],[b,9],[d,22],[c,13],[a,16],[e,45]]):
</pre>
Para ver o resultado, novamente utilizamos o comando Mapledraw;
<pre>
rt := FindRoot(Huf);
draw(Tree(rt), Huf);
</pre>
== Percursos em Árvore ==