I am familiar with the concept of path-copying in the context of binary trees to achieve persistent modifications, but I am unsure if the inclusion of parent pointers has any effect on the complexity. We can assume that rotations may occur, so for practical consideration we can assume an AVL or red-black tree.

My current thought process is that "when a node is modified, anything that points to that node must also be copied". If that theory is correct, and we therefore copy every node along the path from the root to the node, what happens when we do rotations along the path? My intuition is that nodes on the path are the only ones modified, but I am worried that the sibling node that is not on the path might also need to be copied. I would guess that that is not the case, but I am struggling to confirm that.

Does the existence of parent pointers affect the number of nodes to be copied during a modification in a persistent binary tree?


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.