The category_id appears in tables categories, categories_descriptions, products_to_categories and possibly meta_tags_categories_description.

If you can determine the deleted categories_id (perhaps from one of the other tables) it might be easier to restore the categories_id, parent_id, and categories_status = 1 in table categories, and then delete it properly from Admin > Catalog > Categories/Products.