Nsryjdtyk

I am currently building a ScapeGoatTree for a project. However I am having an issue getting my rebuild function to properly take hold of the scapegoat node it is building. In the below code you will see inside the 'if( height >alpha height)' statement 2 more if statements. The first if statement compares my scapegoat node (which I know with current test data should be the static root.left node) and it correctly says they are equal. However when I try to change the Placeholder node(Which should hopefully be an object reference to root.left) it merely overwrites my placeholder node. So thus the second if statement does not fire off, but I need the returned value of my FindScapeGoat to be the node being edited.

I am not going to lie I have always been a bit bad at understanding the pass by reference and pass by value differences in languages, but I really do need to figure out how I can properly apply changes to root.left without needing a specific call to it (since the function will not always choose root.left as the scapegoat node I need a way to call various nodes in my tree rooted at a static location).

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);

    }

}

To address the value/reference issue: non-primitive variables in Java behave (mostly, big caveat that's way out of scope for this answer) like pointers to memory locations. When you say ToBeReplaced you're changing the memory address that ToBeReplaced points to.

To your more specific issue, there are a couple of ways to handle this. The way that I would handle it would be to change the return from FindScapegoat to indicate whether the node is left or right. It seems like it's examining only the immediate children, so there's no need to return a reference to the node itself.

Something like this:

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);

}

You then could move the TreeSize call into the RebuildTree method to avoid the duplicated code.