bfinds(KVs,T) :- bfinds(KVs,_,T).

btree(t(_,_,_,_)).

bfinds([],T,T).
bfinds([K=V|Rest]) --> bfind(K,V), bfinds(Rest).

bfind(K,V,t(K,V,L,R),t(K,V,L,R))  :- !.
bfind(K,V,t(K0,V0,L0,R),t(K0,V0,L,R)) :- K @< K0, !, bfind(K,V,L0,L).
bfind(K,V,t(K0,V0,L,R0),t(K0,V0,L,R)) :- bfind(K,V,R0,R).

bput(K,V,t(K,_,L,R),t(K,V,L,R))  :- !.
bput(K,V,t(K0,V0,L0,R),t(K0,V0,L,R)) :- K @< K0, !, bput(K,V,L0,L).
bput(K,V,t(K0,V0,L,R0),t(K0,V0,L,R)) :- bput(K,V,R0,R).

% pop Leas
blest(K,V,t(K,V,_,_),_) :- !.
blest(K,V,t(K0,V0,L,R),t(K0,V0,L,R)) :- blest(K,V,L).

bmost(K,V,t(K,V,_,_)) :- !.
bmost(K,V,t(_,_,_,R)) :- bmost(K,V,R).

l2t(KVs,T) :- btree(T0), l2t(KVs,T0,T).
l2t([],T,T) :- !.
l2t([K=V],T0,T) :- bfind(K,V,T0,T),!.
l2t(L,T0,T) :-
	halve(L,Left,K=V,Right),
	bfind(K,V,T0,T1),
	l2t(Left,T1,T2),
	l2t(Right,T2,T).

halve([X],[],X,[]).
halve([X,Y|L],[X|Front],Mid,Back) :- halve1(L,[Y|L],Front,[Mid|Back]).
halve1([_,_|Count], [H|T], [H|F], B) :- !, halve1(Count, T, F, B).
halve1(_, B, [], B).

bprint(T) :- bprint(T,0,'.','').
bprint(X,_,_,_) :- var(X), !.
bprint(t(K,V,L,R),In,C,Prefix) :-
    indent(In,C),
	write(Prefix),
	write(K=V),nl,
	bprint(L,In+4,C,' < '),
	bprint(R,In+4,C,' > ').

indent(N,C) :- N1 is N, forall(between(1,N1,_),write(C)).