So, I came up with this scheme for locking nodes when rotating in a binary tree, in which several threads simultaneously have read and write access, which includes locking four nodes per revolution, which, apparently, is an awful lot? I realized that one of the methods is smarter, then I came up with a way to reduce the lock, but google did not go up much (I probably use the wrong terminology).
This is my current outline. Orange and red nodes either move or change by rotation, and they must be blocked, and Green nodes are located next to any node affected by rotation, but they are not affected.
the birth of a binary tree
I decided that there should be a better way to do this, one of my ideas is to take a snapshot of the four affected nodes, rotate them in a snapshot, and then replace the current nodes with snapshots (provided that nothing has changed when I did rotation) - this would allow me to be almost free from blocking, but I'm afraid that the memory overhead can be significant, given that rotation is a fairly quick operation (reassigning three pointers)?
I think I'm looking for pointers (no puns) on how to do this effectively.
source
share