Java 中树节点引用被覆盖的问题

Question

我目前正在为一个项目构建一个 ScapeGoatTree。但是，我在让我的重建函数正确掌握它正在构建的替罪羊节点时遇到了问题。在下面的代码中，您将在 'if( height >alpha height)' 语句中看到另外 2 个 if 语句。第一个 if 语句比较我的替罪羊节点（我知道当前测试数据应该是静态 root.left 节点）并且它正确地说它们是相等的。但是，当我尝试更改占位符节点（希望它应该是对 root.left 的对象引用）时，它只会覆盖我的占位符节点。因此，第二个 if 语句不会触发，但我需要 FindScapeGoat 的返回值作为正在编辑的节点。

我不想撒谎我一直不太擅长理解语言中的引用传递和值传递差异，但我确实需要弄清楚如何正确应用更改 root.left 而不需要对其进行特定调用（因为该函数不会总是选择 root.left 作为替罪羊节点，我需要一种方法来调用我的树中以静态位置为根的各种节点）。

public static void Insert(int key) {
    height = dupflag = 0;
    root = insertHelp(root, key);
    if(dupflag == 0) MaxNodeCount++;    //If inserted value wasn't duplicate increase max node count
    double alphaHeight = ((Math.log(MaxNodeCount) / Math.log(1 / alpha)) + 1);
    if (height > alphaHeight){
        Node ToBeRebalanced = FindScapegoat(root, key);  // Find scapegoat node
        int sizeRoot = TreeSize(ToBeRebalanced, 0);
        if(ToBeRebalanced == root.left) System.out.println("Scapegoat node == root.left");
        ToBeRebalanced = RebuildTree(sizeRoot+1, ToBeRebalanced);
        if(ToBeRebalanced == root.left) System.out.println("Scapegoat node == root.left");
        Print(ToBeRebalanced);
        Print(root);
    }
}

Answer 1

解决 value/reference 问题：Java 中的非原始变量的行为（主要是，超出此答案范围的重要警告）类似于指向内存位置的指针。当您说 ToBeReplaced 时，您正在更改 ToBeReplaced 指向的内存地址。

对于您的更具体的问题，有几种方法可以解决这个问题。我处理它的方式是将 return 从 FindScapegoat 更改为指示节点是左还是右。它似乎只检查直接子节点，因此不需要 return 对节点本身的引用。

像这样：

public enum Side {
    LEFT,
    RIGHT
}
//...
Side ToBeRebalanced = FindScapegoat(root, key);  // Find scapegoat node
if (ToBeRebalanced == Side.Left){
  int sizeRoot = TreeSize(root.left, 0);
  root.left = RebuildTree(sizeRoot+1, root.left);
} else {
  int sizeRoot = TreeSize(root.right, 0);
  root.right = RebuildTree(sizeRoot+1, root.right);
}

然后您可以将 TreeSize 调用移动到 RebuildTree 方法中以避免重复代码。

Java 中树节点引用被覆盖的问题

Issue with tree node reference being overwritten in Java

java

binary-tree