| Idea: |
- the node-copying method combines the strengths of fat nodes (cheap updates) and path copying (cheap reads): every node carries its two original child pointers plus a bounded table of extra version-stamped pointers
- an update first tries the cheap move: write one extra pointer into the changed node's table — \(O(1)\), no copying
- only when the table is full is the node copied: the copy starts with the currently live pointers as its originals (and an empty table), and the parent must now point at the copy — the same step one level up, so a full parent cascades further, exactly like path copying
|