BeginPackage["trees`"]

trees::usage = "Pacote com implementação de árvores de pesquisa de registos"

treeQ::usage="treeQ[x] devolve True se o argumento for uma árvore de pesquisa de registos e False caso contrário"

void::usage="void denota a árvore vazia"

join::usage = "join[x,y,d,n] denota a árvore com o registo de conteúdo d e a chave n na raíz, sub-árvore esquerda x e sub-árvore direita y"

voidQ::usage="voidQ[x] devolve True sse o seu argumento for a árvore vazia"

root::usage = "root[x] devolve o conteúdo do registo na raíz da árvore x"

left::usage="left[x] devolve a sub-árvore esquerda de x"

right::usage="right[x] devolve a sub-árvore direita de x"

searchkey::usage="searchkey[x,n] devolve True sse existir na árvore x um registo com chave n"

findreg::usage = "findreg[x,n] devolve o conteúdo do registo associado à chave n, se existir, e Null caso contrário"

addreg::usage = "addreg[x,d,n] acrescenta à árvore x um registo com conteúdo d e chave n"

delreg::usage = "delreg[x,n] elimina o primeiro registo com chave n na árvore x (devolvendo Null se não existir)"

Begin["`Private`"]

treeQ=Function[e,e=={}||(treeQ[e[[1]]]&&treeQ[e[[3]]]&&IntegerQ[e[[4]]])];

void={};

join=Function[{x,y,r,n},
      If[treeQ[x]&&treeQ[y]&&IntegerQ[n],{x,r,y,n},Print["Argumento inválido (join)"]]];

voidQ=Function[x,x=={}];

root=Function[x,If[treeQ[x]&&Not[voidQ[x]],x[[2]],Print["Argumento inválido (root)"]]];

left=Function[x,If[treeQ[x]&&Not[voidQ[x]],x[[1]],Print["Argumento inválido (left)"]]];

right=Function[x,If[treeQ[x]&&Not[voidQ[x]],x[[3]],Print["Argumento inválido (right)"]]];

key=Function[x,If[treeQ[x]&&Not[voidQ[x]],x[[4]],Print["Argumento inválido"]]];

searchkey=Function[{x,n},
      If[treeQ[x]&&IntegerQ[n],
        If[voidQ[x],False,
          If[n==key[x],True,
            If[n<key[x],searchkey[left[x],n],searchkey[right[x],n]]]],
        Print["Argumento inválido (searchkey)"]]];

findreg=Function[{x,n},
      If[searchkey[x,n],
        If[n==key[x],root[x],
          If[n<key[x],findreg[left[x],n],findreg[right[x],n]]],
        Print["Argumento inválido (findreg)"]]];

addreg=Function[{x,r,n},
      If[treeQ[x]&&IntegerQ[n],
        If[voidQ[x],join[void,void,r,n],
          If[n<key[x],join[addreg[left[x],r,n],right[x],root[x],key[x]],
            join[left[x],addreg[right[x],r,n],root[x],key[x]]]],
        Print["Argumento inválido (addreg)"]]];

findlast=Function[{x},
      If[treeQ[x]&&Not[voidQ[x]],
        If[voidQ[right[x]],{root[x],key[x]},findlast[right[x]]],
        Print["Argumento inválido (findlast)"]]];

dellast=Function[{x},
      If[treeQ[x]&&Not[voidQ[x]],
        If[voidQ[right[x]],left[x],
          join[left[x],dellast[right[x]],root[x],key[x]]],
        Print["Argumento inválido (dellast)"]]];

delreg=Function[{x,n},
      If[searchkey[x,n],
        If[n==key[x],
          If[voidQ[left[x]],right[x],
            join[dellast[left[x]],right[x],findlast[left[x]][[1]],findlast[left[x]][[2]]]],
          If[n<key[x],join[delreg[left[x],n],right[x],root[x],key[x]],
            join[left[x],delreg[right[x],n],root[x],key[x]]]],
        Print["Argumento inválido (delreg)"]]];

End[]

EndPackage[]