merge(null, Root2, Root2) :- !.
merge(Root1, null, Root1) :- !.
merge((Val1, Key1, Pr1, Left1, Right1), (Val2, Key2, Pr2, Left2, Right2), (Val1, Key1, Pr1, Left1, NewRight1)) :- Pr1 > Pr2, merge(Right1, (Val2, Key2, Pr2, Left2, Right2), NewRight1).
merge((Val1, Key1, Pr1, Left1, Right1), (Val2, Key2, Pr2, Left2, Right2), (Val2, Key2, Pr2, NewLeft2, Right2)) :- Pr1 =< Pr2, merge((Val1, Key1, Pr1, Left1, Right1), Left2, NewLeft2).

split(null, _, null, null) :- !.
split((XVal, Key, Pr, Left, Right), Val, (XVal, Key, Pr, Left, NewRight), Res2) :- XVal =< Val, split(Right, Val, NewRight, Res2), !.
split((XVal, Key, Pr, Left, Right), Val, Res1, (XVal, Key, Pr, NewLeft, Right)) :- XVal > Val, split(Left, Val, Res1, NewLeft), !.

tree_build([], null) :- !.
tree_build([(HVal, HKey) | []], (HVal, HKey, HPr, null, null)) :-  rand_int(100, HPr), !.
tree_build([(HVal, HKey) | T], V) :- T \= [], tree_build(T, Res), rand_int(100, HPr), merge((HVal, HKey, HPr, null, null), Res, V).

map_get((Val, Key, Pr, Left, Right), Val, Key) :- !.
map_get((XVal, XKey, Pr, Left, Right), Val, Key) :- (XVal > Val, map_get(Left, Val, Key)) ; (XVal < Val, map_get(Right, Val, Key)).

map_replace([], _, _, []) :- !.
map_replace(null, _, _, null) :- !.
map_replace((Val, Key, Pr, Left, Right), Val, NewKey, (Val, NewKey, Pr, Left, Right)) :- !.
map_replace((XVal, XKey, Pr, Left, Right), Val, NewKey, (XVal, XKey, Pr, Res, Right)) :- XVal > Val, map_replace(Left, Val, NewKey, Res).
map_replace((XVal, XKey, Pr, Left, Right), Val, NewKey, (XVal, XKey, Pr, Left, Res)) :- XVal < Val, map_replace(Right, Val, NewKey, Res).

change((Val, Key, Pr, Left, Right), NewKey, (Val, NewKey, Pr, Left, Right)).
map_put(null, Val, NewKey, (Val, NewKey, Pr, null, null)) :- rand_int(100, Pr), !.
map_put((XVal, XKey, Pr, Left, Right), Val, NewKey, Res) :-
                                                    split((XVal, XKey, Pr, Left, Right), Val, ResLeft, ResRight),
                                                    split(ResLeft, Val - 1, LeftLeft, Middle),
                                                    ((Middle == null,
                                                    rand_int(100, NewPr),
                                                    merge(LeftLeft, (Val, NewKey, NewPr, null, null), CurRes));
                                                    (Middle \= null,
                                                     change(Middle, NewKey, NewNode),
                                                     merge(LeftLeft, NewNode, CurRes))),
                                                     merge(CurRes, ResRight, Res).
map_remove(null, _, null) :- !.
map_remove((XVal, XKey, Pr, Left, Right), Val, Res) :-
    												split((XVal, XKey, Pr, Left, Right), Val, ResLeft, ResRight),
                                                   	Val1 is Val - 1,
                                                   	split(ResLeft, Val1, LeftLeft, Middle),
    												merge(LeftLeft, ResRight, Res).