仅使用本地锁从BST中进行多线程删除

Question

在用Java编写BST的多线程实现时，我遇到了以下问题。该BST不应使用全局锁定，而应尽可能少地锁定，仅锁定要更改的节点（添加和删除命令）。因此，其他线程只要不尝试更改与您相同的节点，就可以在树中处于活动状态。我找不到一种方法来删除具有2个子节点的节点。普通算法说要找到要删除的节点的顺序后继者，以将其放置在已删除的节点的位置，然后再删除已复制的节点。但这可能会在这两个节点之间的线程中产生问题，并且需要复制的节点，在传输之后，即使该线程在树中，该线程也不会找到所请求的节点。看一下下面的示例：正在执行Tread 1remove(5)。它找到下一个键（6）并将其复制到该节点，然后从副本中删除该节点。但是同时，另一个执行contains(6)命令的线程正在节点8上等待，执行节点号6之后将不再位于其路径中，即使6节点仍在树中，它也会返回错误的结果。

删除命令之前的状态示意图（蓝色箭头指示^第二个线程在何处。

删除命令后的状态示意图（蓝色箭头指示^第二个线程在何处。 

如何在不锁定整个树的情况下克服此问题？

Answer 1

我使用的解决方案是为BST提供一个版本号，并且每次remove有两个子节点的节点需要a时，我都会在删除重复的节点之前增加版本号。然后，每个操作在开始之前都会检查版本号，如果我得到一个表明未找到密钥的结果，我会检查版本号是否仍然相同，如果不相同，请重试该操作。这表示：对于remove和contains-如果操作失败（这意味着，关键是没有找到）和版本改变了，再试一次。对于insert-我检查版本号，而不是在操作结束时检查，而是在我处于一片叶子时以及在创建和添加新节点之前检查版本号。如果要添加一个新节点，这意味着我没有找到带有该键的节点，我想确保在更改键并创建新叶子之前，键确实不在树中，以防止出现以下情况：一个双键将被添加到树中，然后我需要通过删除节点来重做此操作。