The insertion procedure in red-black-tree, the insertion algorithm is something like, 1. hey, here is the newbie z! 2. are you smaller than this newbie? (z) yes -> okay, next (smaller guy) no -> okay, next (bigger guy) then finally, find the correct location on which a < z <…