The codex has this to say on wp_delete_post.
When the post and page goes, everything that is tied to it is deleted also. This includes comments, post meta fields, and terms associated with the post.
Which kind of suggests that if a post that had the tags a,b,c attached to it gets deleted, then, all the a,b and the c tags are also deleted from the wp_terms, and wp_term_taxonomies tables even if those tags were to be associated with some other living posts!* - which I doubt is the case. Why would WP API delete the terms that are working for some other posts?