Árvores
Esse capítulo é dedicado aos aspectos computacionais do estudo das árvores. Árvores são um tipo específico de grafo, que são conectados grafos simples que não tem circuitos simples.
O código Maple nesse capítulo assume que você está usando uma versão atualizada do Maple Network Package. Essas melhorias afetam principalmente a exibição das árvores. Em particular, o comando draw foi atualizado para se entender como desenhar árvores com raiz. Para testar se você está utilizando a versão correta, carregue o pacote networks e rode a versão comando, como em:
with(networks): version();
Se esse comando não produzir uma descrição da versão, então vocês está utilizando a versão errada. Uma versão apropriada pode ser encontrada no site ftp: http://www.mhhe.com/math/advmath/rosen/r5/instructor/maple.html junto com instruções de instalação.
Primeiro, nós iremos discutir como representar, desenhar, e trabalhar com árvores usando o Maple. Especificamente, nós iremos descrever como representar e construir árvores e derivar características básicas sobre árvores em Maple. Nós iremos demonstrar como utilizar o Maple para desenhar árvores.Nós iremos demonstrar como resolver vários problemas, onde árvores fazem um papel importante usando Maple, como procurando e construindo códigos prefixos, usando uma implementação específica do algoritmo de Huffman. Nós iremos descrever como usar o Maple para fazer diferentes métodos de percorrer árvore, onde o percurso é a visita dos vértices da árvore em uma ordem pré-definida. Então nós iremos discutir como esses percursos se relacionam com o tópico de organização. Continuamos mostrando como usar o Maple para criar spanning trees de grafos. Então, nós iremos mostrar como usar o Maple como resolver vários problemas utilizando backtracking. Finalmente, iremos mostrar como encontrar spanning trees de peso mínimo de grafos ponderados usando Maple.
Contents
Introdução à Árvores
Para começar, iremos demonstrar como construir árvores em Maple. Dada uma árvore sem raiz, nós podemos construir essa árvore em Maple assim como faríamos com qualquer grafo. Nós também iremos dar um procedure que usa algumas capacidades embutidas do Maple que determinam se um grafo específico é uma árvore.
Antes de entrar na implementação, há dois pontos importantes que devem ser mencionados. Primeiro, notamos que o Maple difere da terminologia de texto, no senso que o Maple refere-se a simples ciclos, quando o texto se refere a simples circuitos. O segundo ponto que vale mencionar é de que uma árvore sem raiz é um grafo simples que não tem ciclos simples. Estruturalmente falando, uma árvore com raiz é exatamente a mesma coisa que uma árvore sem raiz, com a propriedade adicional de que há um vértice específico chamado de raiz, que é visto como o ponto inicial de uma árvore. Em termos de implementação Maple, representamos árvores sem raiz como grafos, e criamos árvores sem raiz a partir de árvores sem raiz utilizando comandos Maple como spantree, que serão abordados posteriormente, especificando um nó desejado para uma árvore sem nó.
Outro tipo importante de árvore é a árvore ordenada, que é uma árvore com raiz onde os filhos de um vértice ordenados de alguma maneira como 1st, 2nd,...,m-th filhos se houverem m filhos de um dado vértice. Nós iremos fazer uso do peso dos vértices para determinar a ordem dos filhos de um vértice específico. Esse tipo de árvore irá aparecer posteriormente, mas é importante distinguir árvores sem raiz, com raiz e desordenadas, e árvores com raiz e ordenadas.
Como primeiro exemplo, iremos discutir árvores sem raiz. Criamos uma árvore exatamente da mesma maneira que criamos um grafo, usando o pacote networks do Maple. Como nosso primeiro exemplo, iremos criar uma árvore simples em 4 vértices.
with(networks): new(T1): addvertex(a,b,c,d,f,g,T1): addedge(a,b,a,c,a,d,b,f,b,g, T1): draw(Tree(a),T1);
Suponha que fomos dados um grafo e se foi pedido para determinar se ele é ou não uma árvore. Pela definição de árvores, precisamos verificar as 3 seguintes propriedades:
1.O grafo é conectado.
2. O grafo é simples.
3. O grafo não tem ciclos.
Usando Maple, essas propriedades são facilmente verificadas. Em particular, podemos determinar se um grafo é conectado em Maple usando o comandoscomponents, que retorna uma coleção de conjuntos de vértices, onde cada conjunto nessa coleção contém os vértices de um componente conexo do grafo. Podemos determinar se um grafo é simples usando o comando Maple gsimp, que retorna a árvore simples por baixo de um multigrafo, e então comparando o número de arestas da árvore por baixo do grafo original. Isso nos leva até o procedure IsSimple.
IsSimple := proc(G::graph) local H;
H := networks[duplicate](G);
if nops(edges(gsimp(H))) = nops(edges(G)) then true
else false fi;
end:
Note que não devemos simplificar G por si só, pois tal simplificação é um processo irreversível.
Para testar conectividade, utilizamos o procedure IsConnected
IsConnected := proc(G::graph) evalb(nops(components(G)) = 1) end:
Podemos determinar se um grafo tem ou não ciclos utilizando o comando cyclebase do Maple que retorna um conjunto de ciclos, ou circuitos simples, que formam uma base de todos os ciclos (circuitos simples) no grafo dado; se o cyclebase não tiver ciclos, o grafo não tem ciclos. Isso, junto com os dois testes anteriores pode ser usado para testar se um grafo é uma árvore.
IsTree:=proc(G::graph)
if not (IsConnected(G) and IsSimple(G)) then
RETURN(false); fi;
if cyclebase(G) = {} then RETURN(true);
else RETURN(false); fi;
end:
Se você preferir, pode substituir o teste cycle base test nesse procedure por um que verifica se o número de arestas é um a menos que o número de vértices.
Agora estamos prontos para usar o procedure IsTree para determinar se alguns grafos particulares são árvores;
IsTree(T1); IsTree(complete(3));
Árvores com raiz
Até esse ponto, nós lidamos apenas com árvores sem raiz. Podemos usar o comando Maplespantree para mudar uma árvore sem raiz em uma árvore com raiz. Ele faz isso atualizando os conjuntos de ancestrais e filhas (descendentes) para cada vértice, para refletir a estrutura da spanning tree.
Para usar o comando spantree, devemos selecionar o vértice e formar uma spanning tree com esse vértice como raiz, direcionando todas as arestas na árvore em direção a raiz. (Estudaremos spanning trees mais tarde nesse capítulo. Geralmente, o comando spantree pega um grafo conexo indireto G e um vértice v e constrói uma spanning tree de G usando v como a raiz, direcionando todas as arestas em direção a v.) Por exemplo, podemos transformar a árvore T1 em uma árvore com raiz, tomando a como sua raiz e utilizando o comando:
T2:=spantree(T1, a):
Podemos facilmente observar relações entre vértices de uma árvore utilizando comandos embutidos no Maple. Entre os comandos que são úteis para isso estão daughter, ancestor, neighbours e departures. O comando daughter encontra os filhos de um vértice em uma árvore com raiz, e o comando ancestor do Maple encontra o vértice pai de um vértice em uma árvore com raiz. Os comandos neighbors e departures agem de maneira similar, determinando os filhos de um vértice em uma árvore com raiz.
Para ilustrar o uso de alguns desses comandos no Maple, podemos determinar relações de árvores como pais, filhos, ancestrais e descendentes de vértices específicos. Por exemplo, podemos encontrar os filhos do vértice a na árvore T2, usando o comando:
daughter(a, T2);
Para achar o pai de d na árvore T2, usamos o comando:
ancestor(d, T2);
Agora representamos um procedure que encontra todos os descendentes, ancestrais e irmãos de um vértice particular em uma árvore com raiz. Esse procedure, chamado Family, pode ser descrito usando o seguinte pseudo-código:
1. Para encontrar todos os ancestrais, usamos o comando ancestor do Maple até não haverem mais ancestrais (ex: quando atingimos o vértice raiz).
2. Para achar todos os descendentes, usamos o comando daughter repetidamente até não haverem mais descendentes(ex: quando todas as folhas de um vértice forem atingidas).
3. Para se achar todos os irmãos de um vértice v, primeiros encontramos o ancestral de v, chamado w; os irmãos de v são descendentes de outro w de v.
Uma implementação desse procedure é como a seguinte:
Family := proc(v::name,G::graph)
local Temp, Ancestors, Descendants, Siblings;
Ancestors := ancestor(v,G);
Temp := ancestor(v,G);
while not (Temp = {}) do
Ancestors := Ancestors union Temp;
Temp := ancestor(Ancestors,G);
od;
Descendants := daughter(v,G);
Temp := daughter(v,G);
while not (Temp = {}) do
Descendants := Descendants union Temp;
Temp := daughter(Descendants,G);
od;
Siblings := daughter(ancestor(v, G), G) minus v;
[Ancestors,Siblings,Descendants];
end:
Agora iremos construir uma árvore mais larga, chamada T3 que é a árvore mostrada na Página 5433 do texto, e então iremos executar o novo procedure criado em um de seus vértices.
new(T3): addvertex(A,B,C,D,E,F,G,H,I,J,K,L,M,N,T3): addedge( [A,B],[A,J],[A,K],[B,C],[B,E],[B,F], [C,D],[F,G],[F,I],[G,H],[K,L],[L,M],[L,N], T3): draw(Tree(A),T3);
Os descentendes do vértice B são obtidos pelo comando:
Bfamily := Family(B,T3); Bfamily[3];
A seguir, determinamos o conjunto de vértices internos (galhos) e folhas de uma árvore com raiz. Lembre-se que um v é um vértice interno de uma árvore com raiz se v tiver filhos, e que v é o vértice folha de uma árvore com raiz se v não tiver filhos. Em outras palavras, em qualquer árvore com raiz não trivial (ex:.uma árvore com raiz que é mais do que apenas um vértice raiz), as folhas são essas com gráu de vértice 1, e os vértices internos são vértices com grau maior que 1.
Sabendo disso, podemos usar o comando Maplevdegree para determinar o conjunto de folhas e o conjunto de vértices internos dada uma árvore com raiz.
Leaves:=proc(T::graph, root::name)
select( proc(x,T) evalb( vdegree(x,T) < 2 ) end,
vertices(T) minus root , T );
end:
Internal:=proc(T::graph, root::name)
select( proc(x,T) evalb( vdegree(x,T) > 1 ) end,
vertices(T) minus root , T );
end:
Leaves(T2, a); Internal(T2,a);
Agora iremos discutir como encontrar o maior número de filhos de um vértice interno de uma árvore com raiz. Lembre-se que se m é esse número, a árvore é chamada de árvore m-ária. Também iremos descrever como determinar se uma árvore m-ária é balanceado. Lembre-se que uma árvore é balanceada se todas as folhas estão no nível h ou h-1 se uma árvore tem um total de h níveis, onde o nível do vértice é a distância do caminho único from da raiz até tal vértice.
Para utilizar o Maple para determinar se uma árvore é uma árvore m-ária, podemos simplesmente olhar a sequencia de graus do vértice, tomando em conta que para todos os vértices exceto a raiz, o grau de tal vértice é um a mais que o número de descendentes. Isso pode ser feito usando o comando vdegree no Maple. Para determinar se uma árvore é balanceada, podemos usar a estrutura de armazenamento interno de uma árvore em Maple. Iremos utilizar do fato de que o Maple armazena o nível do vértice em uma árvore como o peso do vértice para esse vértice. Por exemplo, se v é um vértice que está no nível 3 de uma árvore, então podemos extrair essa informação usando o comando vweight no vértice v.
Esaa técnica é formalizade pelo seguinte procedure no Maple:
ArityBalanced:=proc(G::graph, Root::name)
local Leaf_Depth, V, Max_Children, is_balanced,i;
V:=vertices(G); Leaf_Depth:={};
is_balanced:=false;
for v in V do
if (not (v = Root)) and (vdegree(v,G)=1) then
Leaf_Depth:=Leaf_Depth union vweight(v, G);
fi;
od;
if nops(Leaf_Depth) > 2 then
printf(`The tree is not balanced`);
elif nops(Leaf_Depth) = 1 then
printf(`The tree is balanced`);
is_balanced:=true;
elif nops(Leaf_Depth) = 2
and abs(Leaf_Depth[1] - Leaf_Depth[2]) > 1 then
printf(`The tree is not balanced`);
else
printf(`The tree is balanced %a`, Leaf_Depth );
is_balanced:=true;
fi;
Max_Children:=maxdegree(G)-1;
if vdegree(Root, G) > Max_Children then
Max_Children:=vdegree(Root, G);
fi;
printf(`The arity of the tree is %d`, Max_Children);
[Max_Children, is_balanced];
end:
ArityBalanced(T3, A):
Agora iremos utilizar o procedure ArityBalanced para verificar a fórmula na página 541 do texto para árvore m-árias cheias. Isto é, iremos construir um procedure para computar o número de vértices internos e folhas de dada árvore m-ária, e comparar essas quantidades como esboçado no teorema 3 e teorema 4 da página 541 do texto. O procedure chamado TheoremVerify utilizará:
TheoremVerify:=proc(G::graph, Root::name) local internal, m, leaves, n, i, V, is_full_tree; V:=vertices(G); n:=nops(V); i:=0; internal:=0; leaves:=0; is_full_tree:=true;
Use o procedure ArityBalanced para determinar o número de argumentos
m:=ArityBalanced(G, Root)[1];
while is_full_tree and i<n do
i:=i+1;
Se não houverem filhos do vértice, ele é uma folha
if nops(daughter(V[i], G)) = 0 then
leaves:=leaves+1;
Se o número de filhos não for m, então não é uma árvore completa
elif not (nops(daughter(V[i],G)) = m) then
printf(`The tree is not a full tree`);
is_full_tree:=false;
O vértice atual é um vértice interno
else
internal:=internal+1;
fi;
od;
if is_full_tree then
printf(`Vertices count is %d`, n);
printf(`Computed count (m*i+1) is %d`, m*internal + 1);
printf(`Leaf count is %d`, leaves);
printf(`Computed count ((m-1)*i + 1) is %d`,
(m-1)*internal+1);
fi; NULL;
end:
Utilizaremos o procedure TheoremVerify para verificar os teoremas 3 e 4 do texto em uma árvore 3-ária completa.
new(Full1):
addvertex(A,2,3,4,5,6,7,8,9,10, Full1):
addedge(A,2, A,3, A,4, 2,5, 2, 6, 2,7,
4,8, 4,9, 4,10, Full1):
TheoremVerify(Full1, A);
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:
new(g): addvertex(1,2,g): vweight(1,g);
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:
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:
Usar essa comparação nos permite geralmente ignorar que tipo de marcação está sendo utilizada.
IsLessThan(1,2); IsLessThan(b,a); IsLessThan(1,b);
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.
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:
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:
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;
Temos uma árvore com raiz...
cur_vertex := FindRoot(T); while x <> cur_vertex do
As ordenações relativas dos descendentes e x e cur_vertex determinam se x pode ser inserido como folha.
Kids := daughter(cur_vertex,T);
Kids := sort( convert(Kids,list) , IsLessThan );
Candidates :=
sort( [ x, cur_vertex, op(Kids)], IsLessThan );
Comece com casos fáceis
if nops(Candidates) = 2 then
não há filhos, então adicione apenas um novo filho.
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
dois descendentes, então não há inserção nesse nível...
if IsLessThan(x,cur_vertex)
then cur_vertex := Kids[1];
else cur_vertex := Kids[2]; fi;
next;
elif nops(Candidates) = 3 then
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]
if Candidates[1] = cur_vertex
or Candidates[3] = cur_vertex
then
cur_vertex := Kids[1];
next;
fi;
Para todos os casos restantes adicione em x como um novo vértice
if IsLessThan(x,cur_vertex) then
addvertex(x,weight=`Lft`,T);
else
addvertex(x,weight=`Rht`,T);
fi;
Sim! Esse nível.
addedge( [cur_vertex,x] , T);
cur_vertex := x;
break;
fi;
od;
RETURN( cur_vertex );
end:
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:
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;
Para ver a árvore resultante e sua estrutura, use o comando Mapledraw.
draw(Tree(4), Tree_Num);
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.
BiSearch := proc(T::graph, v)
local i, Kids, cur_vertex;
cur_vertex := FindRoot(T);
while v <> cur_vertex do
print(cur_vertex);
verifique os casos fáceis
if v = cur_vertex then RETURN(true); fi;
Kids := daughter(cur_vertex,T);
if Kids = {} then RETURN( false) fi;
descendentes, então comece a procurar...
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
não está presente, a não ser que cur_vertex seja o primeiro ou último da lista
if Candidates[1] <> cur_vertex
and Candidates[3] <> cur_vertex then
RETURN( false );
fi;
cur_vertex := Kids[1];
next;
fi;
od;
RETURN(true);
end:
Para testar esse procedure, tentamos procurar por dois elementos, um que está na árvore e um que não está. Tree_Num;
BiSearch(Tree_Num,8); BiSearch(Tree_Num,12);
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.
HuffCompare :=proc(a::list,b::list) if a[2] <= b[2] then true else false fi; end:
Por examplo, descobrimos que [b,10] < [a,15].
HuffCompare([b,10],[a,15]);
Utilizando esse método de comparação, listas de códigos de elementos podem ser ordenadas em ordem crescente.
sort( [[a,5],[b,10],[c,8],[d,11]], HuffCompare);
O algoritmo de codificação de Huffman completo é implementado da seguinte maneira:
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;
pegue os dois primeiros elementos de código
x:=Q[1]; Q:=subsop(1=NULL, Q);
y:=Q[1]; Q:=subsop(1=NULL, Q);
construa o novo vértice e sua localização
z := [ i , x[2]+y[2]];
for j to nops(Q) while HuffCompare( z, Q[j]) do
j := j+1;
od; j := j-1;
adicione os vértices e arestas a árvore
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:
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;
Huf:=Huffman([[f,15],[b,9],[d,22],[c,13],[a,16],[e,45]]):
Para ver o resultado, novamente utilizamos o comando Mapledraw;
rt := FindRoot(Huf); draw(Tree(rt), Huf);
