Long description

Part (a): It is labeled Original tree. The tree starts at Adding a node. A has two possibilities B and E. B has two possibilities C and D. Part (b): It is labeled initialize node X and connect E to X. Any readers in A and E are not affected. The tree is the same as in part (a). Only node X is added at the top of node E in a dashed square box and a dashed downward arrow connected to node E. Part (c): It is labeled When X is completely initialized, connect X to A. Readers currently in E will have read the old version, while readers in A will pick up the new version of the tree. In this part, the tree is the same as in part (b). Only, node A is connected to node X and node X is connected to node E. Also, node X is in a normal squared box, not a dashed line box. Part (d): It is labeled as Decouple B from A. Note that there may still be readers in B. All readers in B will see the old version of the tree, while all readers currently in A will see the new version. The tree is the same as in part (c). Only, there is a bidirectional arrow from node C to node X. Part (e): It is labeled as Wait until we are sure that all readers have left B and C. These nodes cannot be accessed anymore. The tree is the same as in part (d). Only, node B is now in a dashed box with dashed connected arrows. Part (f): It is labeled as Now we can safely remove B and D. Now, finally in a tree, A has two possibilities C and X. X has one possibility E.