Aula 16

Um dicionário será implementado como uma arvore de busca binaria que armazena tanto a chave como o valor

0.1 parte da arvore de busca binária

A arvore de bisa binária é implementada por

arv(CHAVE, VALOR, ArvoreEsquerda, ArvoreDireira)  ou vazia

Implemente os predicados da abb

insereabb(+Chave,+Valor, +ArvVelha, -ArvNova)
trocaabb(+Chave, +Valoe, +ArvVelha, -ArvNova) 
lookupabb(+Chave, +Arvore, -Valor)

insereabb insere um par Chave Valor na Arvore velha (ArvVelha) se a chave não esta na arvore, e falha se a chave já esta la.
trocaabb troca o valor associado a chave se ela ja esta na arvore e falha se ela a chave não estiver na arvore.
lookupabb recebe uma chave e uma arvore e "retorna" o valor associado a chave na arvore, ou falha se a chave não esta na arvore.

0.2 parte do dicionário

Assumindo os predicados acima, implemente

getdic(+Chave, +Dicionario, -Valor)

que retorna o valor associado a Chave no Dicionario, ou falha se a Chave não esta no dicionário

xgetdic(+Chave, +Dicionario, +ValorDefault, -Valor)

que retorna o valor associado a Chave no Dicionario, ou o ValorDefault se a Chave não esta no dicionário

putdic(+Chave, +Valor, +DicVelho, -DicNovo)

que insere o par Chave/Valor no dicionário (inserindo ou trocando se for o caso).

1 Solucao

insereabb(CH,V,vazia,arv(CH,V,vazia,vazia).
insereabb(CH,V,arv(CH,_,_,_),_) :- !, fail.
insereabb(CH,V,arv(XCH,XV,AE,AD),NARV) :- CH<XCH 
                              -> insereabb(CH,V,AE,NAE), NARV = arv(XCH,XV,NAE,AD)
                              ; insereabb(CH,V,AD,NAD), NARV = arv(XCH,XV,AE,NAD)

trocaabb(_,_,vazia,_) :- !,fail.
trocaabb(CH,V,arv(CH,_,AE,AD),arv(CH,V,AE,AD)).
trocaacc(CH,V,arv(XCH,XV,AE,AD), NARV) :-  CH<XCH 
                              -> trocaabb(CH,V,AE,NAE), NARV = arv(XCH,XV,NAE,AD)
                              ; trocaabb(CH,V,AD,NAD), NARV = arv(XCH,XV,AE,NAD)

lookupabb(_,vazia,_) :- !,fail.
lookupabb(CH,arv(CH,V,_,_),V).
loopkupabb(CH,arv(XCH,_,AE,AD),V) :- CH<XCH
                              -> loopupabb(CH,AE,V)
                              ; lookup(CH,AD,V).

getdic(CH,D,V) :- lookupabb(CH,D,V).

xgetdic(CH,D,V,DEF) :- lookupabb(CH,D,V) ; V = DEF.

putdic(CH,V,D,ND) :- lookupabb(CH,D,_) 
                    -> trocaabb(CH,V,D,ND)
                     ; insereabb(CH,V,D,ND).