Условия вращения дерева AVL - PullRequest
Новая
       36

Условия вращения дерева AVL

1 голос
/ 24 октября 2019

Я в среднесрочной перспективе изучаю различные древовидные алгоритмы, такие как двоичные деревья, деревья AVL и т. Д. И т. Д.

Экзамен не столько о том, как написать код, сколько о том, что происходит, когда вы 'пытаемся установить баланс дерева. Но я пытаюсь написать это в коде, чтобы я чувствовал себя комфортно для предстоящих заданий. Я думаю, что выписал действительные коды для поворотов, как показано ниже, но я продолжаю получать исключение нулевого указателя при попытке получить высоты.

Дерево реализовано правильно (я случайно составил список чисел и нарисовалдерево вручную, записывая, какая высота должна быть для каждого узла и сопоставляя ее с System.out). 

 private Node rightRotation(Node node) {   //Creates a temp node and rotates the child and grandchild
        Node temp = node.lC;
        node.lC = temp.rC;
        temp.rC = node;
        return temp;                              //Returns the temp node with the new alignment 
    }

    private Node lRotation(Node node) {
        Node temp = node.rC;
        node.rC = temp.lC;
        temp.lC = node;
        return temp;
    }

    private Node rLRotation(Node node) {
        node.rC = rightRotation(node.rC);
        return lRotation(node);
    }

    private Node lRRotation (Node node) {
        node.lC = lRotation(node.lC);
        return rightRotation(node);
    }

это мои условия 


    void updateTree(){
        if (rC.height - lC.height >= 1 && rC.lC.height > rC.rC.height | rC.rC == null) rLRotation(this);
        else if (lC.height - rC.height >= 1 && lC.rC.height > lC.lC.height | lC.lC == null) lRRotation(this);
        else if (rC.height - lC.height >= 1) lRotation(this);
        else if (lC.height - rC.height >= 1) rightRotation(this);
    }
...