as mentioned in the title, assuming that the recycle bin of my org is full, what will happen in recycle bin and the new deleted record, when I delete something from Salesforce ?
Once the recycle bin is full Salesforce automatically start deleting the data. Old data is deleted first.
By default Deleted records remain in the recycle bin for 15 days, and can be restored during that time.
After 15 days, deleted items are purged from the recycle bin, and once purged, they can’t be recovered.
Nothing happens immediately when the Recycle Bin is full. However, on the next Recycle Bin clean up cycle, older records will be purged from the Recycle Bin to bring it below the maximum capacity allowed for your org. For example, if you have a limit of 15,000 records, and the Recycle Bin has 15,250 records, then the oldest 250 records would be purged.
In theory, you typically have a few hours to bring the Recycle Bin below the maximum capacity, but you should not rely on this behavior. Note that the 15 day limit is also only processed every few hours, so you typically have a bit longer than 15 days, though, again, you should not rely on this behavior.
If records exists in recycle bin which is used for sharing recalculation then Salesforce takes time to complete that process, because sharing recalculation includes records from recycle bin.
That's why, if you want to delete those records permanently without moving to recycle bin then recommended to use Bulk API hard delete.