I don't know exactly how to do this on a Mac, but I've done it on a PC:
- iTunes keeps your library in two file formats: the binary library it usually reads from, and an XML version it can rebuild from if your binary library gets corrupted.
- since you deleted the songs from within iTunes, your binary library now reflects a library of 0 songs (oh no!) but I'm 75% sure that the XML library is only updated periodically, like maybe each time you close iTunes or something. I hope you haven't done that yet.
- first, navigate to your music/iTunes library folder and make copies of the two library files before you start messing with them (put them somewhere safe!)
- move your actual music files from the trash back into their respective folders. Again, if iTunes erased the directory structure, you may have to restore from a backup instead. iTunes won't see them yet, but at least they're back in their rightful spot, and the next steps will encourage iTunes to remember them.
- close iTunes. Open the iTunes binary database file with a text editor and erase a chunk of it or type something witty, then save and close. your goal is to corrupt this database, which will force iTunes to rebuild from the XML database (no, you can't just delete the binary database file. It has to be there but be corrupted).
- copy your backup XML database back into the iTunes Library folder and start iTunes. If it worked, you'll see a dialog that says something like "rebuilding library" and it'll take a while, but you should get back pretty much everything, including playlists.
- the only things NOT stored in the XML database are iTunes-specific (non-ID3 standard) metadata, such as (I think) last played and play count. But if it works, that's a small loss in the grand scheme of things.
- Like I said, the XML database is generally a mirror image of the binary database, which might mean that your XML database also now has a whopping 0 songs in it. If that's the case, your best option is to grab the backup library and just start over from there.