AVL Árvore Balancing

Question

Eu estou trabalhando em uma tarefa que me pede para implementar uma árvore AVL. Eu tenho certeza que eu tenho a rotação métodos corretos, mas eu estou tendo dificuldade para descobrir quando usá-los.

Por exemplo, a explicação no livro diz que eu deveria subir o mesmo caminho que eu fui para baixo para inserir o nó / elemento. No entanto, não pode ter qualquer ponteiros do pai.

Últimas código:

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;
}

O que eu quero fazer aqui é subir de volta a árvore, mas só pode verificar o balanceamento depois que insere o nó. Assim, este estar na cláusula else.

Eu também tentei colocar o código de equilíbrio em que R Samuel Klatchko sugerido, mas verificou o saldo em cada inserção. Por exemplo: Se um inserções 7, 9, 5, 3 e 1 consecutivamente, eu recebo uma exceção de ponteiro nulo ao tentar inserir 1

.

EDIT: Uma razão para o acima exposto pode ter algo a ver com a maneira que eu estava fazendo a altura. Ele funciona muito bem com uma única rotação bem se eu calcular a altura de cada vez com a altura (), mas que quebra o tempo de uma árvore AVL O (log (n)).

Quaisquer pensamentos sobre como fazer isso?

Answer 1

código Você está subindo o mesmo caminho que você desceu. Considere este código:

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

e modificá-lo um pouco:

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

Como o código retorna a partir das chamadas recursivas, cada retorno traz de volta para o pai. Por não devolver imediatamente o valor da chamada recursiva, você tem uma chance de fazer o seu reequilíbrio.

Atualização para o código mais recente

Não se esqueça de reequilíbrio quando você inseriu para a direita.

Answer 2

Você pode tentar passar o ponteiro do pai para o método insert, ou você poderia converter insert em um método iterativo e manter um pilha explícita em que você grava o caminho para baixo da árvore.

A propósito, a fim de escolher qual a rotação de uso, você pode só sei que um nó é desequilibrado, você tem que saber se o sub mais profundo é à direita ou à esquerda. Isso significa que seu método isBalanced simples não é suficiente. Também é ineficiente, e vai explodir a árvore AVL O (log n) complexidade, porque você calcular as alturas de cada vez.