M.P.I - 1998/99 - Trabalho Prático Nr. 1 | |
---|---|
[ DI/UM ] |
Este trabalho deve ser realizado por grupos com um máximo de três alunos. O trabalho deve ser entregue até ao dia 6 de Novembro na recepção do Departamento de Informática e nele deve constar a listagem do código escrito assim como um pequeno relatório.
Pretende-se definir um módulo de árvores binárias em HASKELL. Para isso vamos considerar o seguinte fragmento de código.
module ArvBin where import List data ArvBin a = Vazia | Nodo a (ArvBin a) (ArvBin a) deriving Eq vazia :: ArvBin a -> Bool vazia Vazia = True vazia _ = False esq :: ArvBin a -> ArvBin a esq (Nodo x y z) = y dir :: ArvBin a -> ArvBin a dir (Nodo x y z) = z val :: ArvBin a -> a val (Nodo x y z) = x
Pretende-se agora completar código deste módulo por forma a incluir a funcionalidade descrita abaixo.
(Nodo 5 (Nodo 3 (Nodo 1 Vazia Vazia) (Nodo 4 Vazia Vazia)) Vazia)como:
{5:{3:{1:_|_}|{4:_|_}}|_}
Vamos designar por traço de uma árvore um percurso da raiz até uma sub-árvore vazia. Assim, e a título de exemplo, a árvore
(Nodo 5 (Nodo 3 (Nodo 1 Vazia Vazia) (Nodo 4 Vazia Vazia)) Vazia)possui como traços as sequências [5,3,1]; [5,3,4] e [5].
Uma das principais motivos para a utilização das árvores binárias é o facto de permitirem uma pesquisa mais eficiente. Para isso devem ser construidas de uma forma particular: em qualquer nodo, os valores armazenados na sub-árvore esquerda devem ser inferiores ao valor desse nodo e os armazenados na sub-árvore direita superiores. Nesse caso, para pesquisar um elemento numa árvore, necessitamos de procurar unicamente uma das sub-árvores o que torna o processo de busca mais eficiente. Em Haskell podemos definir essa função como
elemAB :: (Ord a) => a -> ArvBin a -> Bool elemAB x Vazia = False elemAB x (Nodo v e d) = x==v || if x<v then (elemAB x e) else (elemAB x d)
Uma árvore que satisfaça o invariante descrito acima designa-se por "árvore binária de procura".
Uma estrutura de dados também implementada em árvores binárias é a "Heap". Uma "Heap" é uma árvore binária onde cada traço está ordenado de forma crescente.
As árvores binárias podem ser generalizadas retirando a restrição de existirem exactamente duas sub-árvores em cada nodo não vazio. Uma árvore genérica é então uma árvore com um número arbritário de sub-árvores.
data ArvGen a = AGVazia | AGNodo a [ArvGen a]
Implemente a função untraces referida atrás para árvores binárias.