If they haven't been overwritten, they're still in the database file they get stored in, but you'd need a SQLite editor and a little experience with SQL to look at the database to see which field is the active/deleted field, how it denotes either (it could be as simple as 0 is deleted and 1 is active), then you'd have to find the deleted records you wanted to restore, then UPDATE each one to flip the flag from deleted to active. (And you might have to root the phone to get to the database).
Which is why it's always a good idea to make backups - of everything, even some system apps. (If Play gets uninstalled or corrupted somehow, and you have a backup of the apk file for it, no problem. If you don't, you can't use Play to get to the Play store to get Play ...)