Java并发二叉搜索树死锁问题深度解析与ReentrantLock正确实践

class BST {
  // ... 其他成员变量和构造函数 ...
  Lock leftLock = new ReentrantLock();
  Lock rightLock = new ReentrantLock();

  void insertHelper(int key, int lose, Lock prevLock) {
    // ... 其他逻辑 ...
    if (key < this.key) {
      leftLock.lock(); // 第一次获取leftLock
      if (left == null) {
        left = new BST(key, lose);
        leftLock.unlock();
        prevLock.unlock();
      } else {
        leftLock.lock(); // 第二次获取leftLock
        prevLock.unlock();
        left.insertHelper(key, lose, leftLock);
      }
    } else {
      rightLock.lock(); // 第一次获取rightLock
      if (right == null) {
        right = new BST(key, lose);
        rightLock.unlock();
        prevLock.unlock();
      } else {
        // prevLock.unlock(); // 此处也存在逻辑问题，但死锁主要由重复lock引起
        right.insertHelper(key, lose, rightLock);
      }
    }
  }
}

class BST {
  int key;
  int val;
  BST left = null;
  BST right = null;

  Lock leftLock = new ReentrantLock();
  Lock rightLock = new ReentrantLock();

  BST(int key, int val) {
    this.key = key;
    this.val = val;
  }

  void insertHelper(int key, int lose, Lock prevLock) {
    // 确保锁在任何情况下都能被释放，使用try-finally块是更健壮的做法
    // 这里为了演示核心逻辑，暂时省略try-finally，但在实际生产代码中强烈推荐使用
    // prevLock.lock(); // 假设prevLock在调用insertHelper前已被锁定，这里无需再次lock

    try {
        if (key == this.key) {
            this.val += lose;
            // 找到目标节点，完成操作后释放prevLock
            return; // 最终会在外部的finally块或明确的unlock处释放
        } else if (key < this.key) {
            leftLock.lock(); // 获取左子节点锁
            try {
                if (left == null) {
                    left = new BST(key, lose);
                    return; // 节点已插入，返回
                } else {
                    // 左子节点存在，释放当前节点的锁（prevLock），继续递归
                    // 注意：这里的prevLock是当前节点的锁，而不是leftLock
                    // 递归调用会处理leftLock的释放
                    left.insertHelper(key, lose, leftLock);
                    return;
                }
            } finally {
                // 如果在else分支中，leftLock作为prevLock传入递归，
                // 那么它会在递归的finally块中被释放。
                // 如果在if (left == null) 分支中，leftLock在这里释放
                if (left == null) { // 只有当left为null，且在此处创建新节点时，才在此释放leftLock
                    leftLock.unlock();
                }
            }
        } else { // key > this.key
            rightLock.lock(); // 获取右子节点锁
            try {
                if (right == null) {
                    right = new BST(key, lose);
                    return; // 节点已插入，返回
                } else {
                    // 右子节点存在，释放当前节点的锁（prevLock），继续递归
                    right.insertHelper(key, lose, rightLock);
                    return;
                }
            } finally {
                // 同理，只有当right为null，且在此处创建新节点时，才在此释放rightLock
                if (right == null) {
                    rightLock.unlock();
                }
            }
        }
    } finally {
        // 无论何种情况，确保在方法结束时释放prevLock
        // 这里的prevLock是当前节点的父节点锁，或者根节点的锁
        // 必须确保每次进入insertHelper时prevLock都被锁定，并在退出时释放
        prevLock.unlock();
    }
  }
}

class RootBST {
  Lock rootLock = new ReentrantLock(); // 根节点自身的锁
  BST root = null;

  void insert(int key, int lose) {
    rootLock.lock(); // 锁定根节点
    try {
      if (root == null) {
        root = new BST(key, lose);
      } else {
        root.insertHelper(key, lose, rootLock); // 传递根节点锁
      }
    } finally {
      rootLock.unlock(); // 确保根节点锁被释放
    }
  }
}

class BST {
  int key;
  int val;
  BST left = null;
  BST right = null;

  Lock leftLock = new ReentrantLock();
  Lock rightLock = new ReentrantLock();

  BST(int key, int val) {
    this.key = key;
    this.val = val;
  }

  void insertHelper(int key, int lose, Lock currentParentLock) {
    // currentParentLock 是调用方传递进来的当前节点的父节点锁
    // 在进入本方法时，我们已经持有了currentParentLock
    // 我们的目标是获取当前节点自身的锁，然后释放currentParentLock

    // 假设在调用insertHelper前，prevLock（即这里的currentParentLock）已经被锁定
    // 我们需要获取当前节点对应的锁，但BST节点本身没有一个统一的“nodeLock”
    // 而是通过leftLock/rightLock来保护其子节点。
    // 这里的“手递手”策略需要更精细的设计。

    // 修正后的逻辑：
    // 在进入insertHelper时，currentParentLock是当前节点的父节点锁。
    // 我们需要先判断是向左还是向右，然后获取相应的子节点锁，再释放currentParentLock。

    if (key == this.key) {
        this.val += lose;
        // 找到目标节点，完成操作后释放currentParentLock
        currentParentLock.unlock();
        return;
    } else if (key < this.key) {
        leftLock.lock(); // 获取左子节点锁
        try {
            currentParentLock.unlock(); // 释放父节点锁

            if (left == null) {
                left = new BST(key, lose);
            } else {
                left.insertHelper(key, lose, leftLock); // 递归调用，传递左子节点锁
            }
        } finally {
            // 如果在if (left == null) 分支中创建了新节点，则需要在这里释放leftLock
            // 如果是递归调用，leftLock作为currentParentLock传入，会在递归的finally中释放
            // 因此这里不需要额外的leftLock.unlock()，除非是创建新节点的情况。
            // 但为了简洁和避免重复，让leftLock的释放统一由其作为currentParentLock时处理。
        }
    } else { // key > this.key
        rightLock.lock(); // 获取右子节点锁
        try {
            currentParentLock.unlock(); // 释放父节点锁

            if (right == null) {
                right = new BST(key, lose);
            } else {
                right.insertHelper(key, lose, rightLock); // 递归调用，传递右子节点锁
            }
        } finally {
            // 同理，rightLock的释放统一由其作为currentParentLock时处理。
        }
    }
  }
}