AVL Tree Balancing

Question

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

EDIT: Одна из причин этого может иметь какое-то отношение к тому, как я делал высоту. Он отлично работает с одним вращением вправо, если я каждый раз вычисляю высоту с высотой(), но нарушает время O (log (n)) дерева AVL.

Любые мысли о том, как это сделать?

Answer 1

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

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

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

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

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

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

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

Answer 2

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

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