Проблема с перезаписью ссылки на узел дерева в Java - PullRequest
Новая
       6

Проблема с перезаписью ссылки на узел дерева в Java

0 голосов
/ 26 ноября 2018

В настоящее время я создаю ScapeGoatTree для проекта.Однако у меня возникла проблема с получением моей функции перестроения, чтобы правильно завладеть узлом козла отпущения, который он строит.В приведенном ниже коде вы увидите внутри оператора if (height> alpha height) еще 2 оператора if.Первый оператор if сравнивает мой узел козла отпущения (который, как я знаю, с текущими тестовыми данными должен быть статическим узлом root.left), и он правильно говорит, что они равны.Однако, когда я пытаюсь изменить узел Placeholder (который, мы надеемся, должен быть ссылкой на объект на 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);
    }
}

1 Ответ

0 голосов
/ 26 ноября 2018

Чтобы решить проблему значения / ссылки: не примитивные переменные в Java ведут себя (в основном, большое предостережение, выходящее за рамки этого ответа) как указатели на области памяти.Когда вы говорите ToBeReplaced, вы меняете адрес памяти, на который указывает ToBeReplaced.

К вашей более конкретной проблеме есть несколько способов справиться с этим.Я бы справился с этим, изменив возврат с FindScapegoat, чтобы указать, является ли узел левым или правым.Кажется, что он проверяет только непосредственные дочерние элементы, поэтому нет необходимости возвращать ссылку на сам узел.

Примерно так: 

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, чтобы избежать дублирования кода.

...