M.P.I - 1998/99 - Trabalho Prático Nr. 1
[ DI/UM ]

Introdução

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.

Enunciado

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.

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.

Valorização

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.

Valorização ++

Implemente a função untraces referida atrás para árvores binárias.


Voltar à página principal de MP-I .
Outras disciplinas leccionadas pelo DIUM

Jose Nuno Oliveira
10/22/1998