2
$\begingroup$

When performing an insertion/deletion on a red-black tree, how can be argued or proved that it requires at most one/two trinode restructuring(s) respectively? My thoughts so far were: after inserting a node and two consecutive red nodes exist along a path from root to a leaf a restructuring is done followed by recoloring, resulting in a red-black tree. Does this mean that after inserting a node there can only exist at most one double red problem in the tree which requires one restructuring to fix it?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.