Within Redtail you can access your Recycle Bin from that tab after selecting Contacts from your Left Menu Bar:
Note that you have a "Search Recycle Bin" option above the contacts here that will allow you to quickly see if a contact is in your Recycle Bin.
Then, your previously deleted records are on display in your Recycle Bin in alphanumeric order:
Each deleted record has a corresponding date in the Deleted On column to let you know when the record was removed from your database. If you click the Actions icon to the left of a deleted contact's Name, you'll see that you have two options:
Clicking Permanently Delete Contact will remove the record from your Recycle Bin, and you will not be able to restore it at a later date.
Clicking Restore Contact will place the Record back in your database.
These two actions can also be performed in bulk by selecting the desired contacts and then clicking Restore or Permanently delete from the menu accessible at the top right corner of the Recycle Bin: