split(L,0,[],L) :- !.
split([X|Xs],N,[X|Ys],Zs) :- N > 0, N1 is N - 1, split(Xs,N1,Ys,Zs).

range([H | T], L, L, []) :- !.
range([H | T], N, L, [H | Tail]) :- N < L, N1 is N + 1, range(T, N1, L, Tail).

element_at([H | T], 0, H) :- !.
element_at([H | T], N, R) :- N1 is N - 1, element_at(T, N1, R).
divide(T, X, L, R) :- length(T, N), N1 is N / 2, N2 is N1 + 1, split(T, N2, L1, R), range(L1, 0, N1, L), element_at(L1, N1, X).

tree_build([], []) :- !.
tree_build(T, (X, L, R)) :- divide(T, X, Left, Right), tree_build(Left, L), tree_build(Right, R).

map_get(((Key, Val), L, R), Key, Val) :- !.
map_get(((XVal, XKey), L, R), Val, Key) :- (XVal > Val, map_get(L, Val, Key)) ; (XVal < Val, map_get(R, Val, Key)).

map_replace([], _, _, []) :- !.
map_replace(((Val, Key), L, R), Val, NewKey, ((Val, NewKey), L, R)) :- !.
map_replace(((XVal, XKey), L, R), Val, NewKey, ((XVal, XKey), NewL, R)) :- XVal > Val, map_replace(L, Val, NewKey, NewL).
map_replace(((XVal, XKey), L, R), Val, NewKey, ((XVal, XKey), L, NewR)) :- XVal < Val, map_replace(R, Val, NewKey, NewR).