Балансировка дерева AVL

StackOverflow https://stackoverflow.com/questions/2004351

  •  18-09-2019
  •  | 
  •  

Вопрос

Я работаю над заданием, которое просит меня реализовать дерево 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.

Я также пытался поместить код баланса туда, где предложил Р. Сэмюэл Клатчко, но проверял баланс на каждой вставке.Например:Если кто-то вставит 7, 9, 5, 3 и 1 последовательно, я получу исключение нулевого указателя при попытке вставить 1.

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

Есть мысли о том, как это сделать?

Это было полезно?

Решение

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

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

и немного измените его:

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

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

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

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

Другие советы

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

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

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top