call(G,Val0,ValF) holds, then the value
associated with Key in NewTree is ValF, otherwise it is the value
associated with the key in Tree. Fails if Key isn't in Tree or if
call(G,Val0,ValF) is not satisfiable for all Val0 in Keys. Assumes
keys are sorted and not repeated (fails if this is not true).