% (1)

vazia([]).

% (2)

folha(Info, [Info,[],[]]).

% (3)

info([Info,_,_], Info).

% (4)

esq([_,Esq,_], Esq).

% (5)

dir([_,_,Dir], Dir).

% (6)
% busca falha se não houver;
% se houver, retorna nó onde achou

busca(Chave, Arv, Arv) :- info(Arv, Chave).
busca(Chave, Arv, R) :-
	info(Arv, Info),
	Chave =< Info,
	esq(Arv, Esq),
	busca(Chave, Esq, R).
busca(Chave, Arv, R) :-
	info(Arv, Info),
	Chave >= Info,
	dir(Arv, Dir),
	busca(Chave, Dir, R).

% (7)

insert(Chave, Arv, Nova) :-
	vazia(Arv), !,
	folha(Chave, Nova).
insert(Chave, Arv, Arv) :-
	info(Arv,Chave).
insert(Chave, [Info,Esq,Dir], [Info,Nova,Dir]) :-
	Chave < Info,
	insert(Chave, Esq, Nova).
insert(Chave, [Info,Esq,Dir], [Info,Esq,Nova]) :-
	Chave > Info,
	insert(Chave, Dir, Nova).

% (8)

pre([]).
pre([Info,Esq,Dir]) :-
	write(Info), nl,
	pre(Esq),
	pre(Dir).

% (9)

in([]).
in([Info,Esq,Dir]) :-
	in(Esq),
	write(Info), nl,
	in(Dir).

% (10)

pos([]).
pos([Info,Esq,Dir]) :-
	pos(Esq),
	pos(Dir),
	write(Info), nl.

% (11)

altura(Arv, 0) :- vazia(Arv), !.
altura(Arv, H) :-
	esq(Arv, Esq), altura(Esq, E),
	dir(Arv, Dir), altura(Dir, D),
	H is 1 + max(E,D).

% (12)
% É mais eficiente calcular a altura junto com
% a verificação de se é balanceada.

balanceada(Arv) :- balanc_aux(Arv,_).
balanc_aux(Arv, 0) :- vazia(Arv), !.
balanc_aux(Arv, H) :-
	esq(Arv, Esq), balanc_aux(Esq, E),
	dir(Arv, Dir), balanc_aux(Dir, D),
	Diff is abs(E - D),
	Diff =< 1,
	H is 1 + max(E,D).