AVL Tree Balancing - PullRequest
Новая
       32

AVL Tree Balancing

4 голосов
/ 05 января 2010

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

Например, объяснение в книге говорит, что я должен подняться по тому же пути, по которому я пошел, чтобы вставить узел / элемент. Однако у меня не может быть родительских указателей.

Последний код: 

public BinaryNode<T> insert(BinaryNode<T> node) {
    if (this.getElement().compareTo(node.getElement()) > 0) {
        if (this.getLeftChild() != null) {
            BinaryNode<T> b = this.getLeftChild().insert(node);

            if(!this.isBalanced()) {
                this.balance();
            }

            return b;
        } else {
            this.setLeftChild(node);
        }

    } else if (this.getElement().compareTo(node.getElement()) < 0) {
        if (this.getRightChild() != null) {
            return this.getRightChild().insert(node);
        } else {
            this.setRightChild(node);
        }
    }

    return this;
}

То, что я хочу сделать здесь, это забраться обратно вверх по дереву, но он может проверить баланс только ПОСЛЕ того, как вставит узел. Следовательно, это в предложении else.

Я также попытался поместить код баланса, где предложил R Samuel Klatchko, но проверил баланс на каждой вставке. Например: если вставить последовательно 7, 9, 5, 3 и 1, я получаю исключение нулевого указателя при попытке вставить 1.

РЕДАКТИРОВАТЬ: Одна из причин для вышеизложенного может иметь отношение к тому, как я делал высоту. Он отлично работает с одним поворотом вправо, если я вычисляю высоту каждый раз с помощью height (), но это нарушает время O (log (n)) дерева AVL.

Есть мысли о том, как этого добиться?

Ответы [ 2 ]

3 голосов
/ 05 января 2010

Ваш код поднимается по тому же пути, по которому вы пошли. Рассмотрим этот код: 

if (this.getLeftChild() != null) {
    return this.getLeftChild().insert(node);
}

и слегка его изменить: 

if (this.getLeftChild() != null) {
    boolean b = this.getLeftChild().insert(node);
    // do something here
    return b;
}

Когда код возвращается из рекурсивных вызовов, каждое возвращение возвращает вас к родителю. Не сразу возвращая значение рекурсивного вызова, у вас есть шанс выполнить перебалансировку.

Обновление для последнего кода

Не забудьте перебалансировать, когда вы вставите вправо.

1 голос
/ 05 января 2010

Вы можете попробовать передать родительский указатель в метод insert, или вы можете преобразовать insert в итеративный метод и сохранить явный стек, в котором вы записываете путь вниз по дереву.

Кстати, чтобы выбрать, какой поворот использовать, вы можете просто знать, что узел не сбалансирован, вы должны знать, находится ли более глубокое поддерево справа или слева. Это означает, что вашего простого isBalanced метода недостаточно. Это также неэффективно и приведет к сложности O (log n) дерева AVL, потому что вы каждый раз вычисляете высоты.

...