copy-tree only makes copies of the cons cells, not the arrays. global-map is a "dense" map, which implies it has an array (well, a char-table) inside where it stores the mapping for "simple char" bindings. And (kbd "C-r") corresponds to a simple char binding, so it gets stored in the array (which was not copied by copy-tree).
This said, you should basically never copy a keymap.
Instead just make your new keymap inherit from global-map, e.g. with (defvar my-new-map (make-composed-keymap nil global-map)). This map will start out identical to global-map but you can then modify it all you want without affecting global-map itself.
copy-treeisn't a deepcopy. Trycopy-keymap. – npostavs Jul 13 '16 at 21:52