I know we can augment Red black tree with black depth without affecting its basic operations which is a theorem. But let say I define red depth as number of red ancestors a node has. Can we maintain all basic operations without affecting its asymptotic performance when we augment trees with red depth?

Findings: I think when we change the depth of a parent node, the depth of all nodes in subtree will decrease, so I believe Insert and Delete won't work. Is that so?


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.