AVL Árvore Balancing
-
18-09-2019 - |
Pergunta
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?
Solução
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.
Outras dicas
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.