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?


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.