Balanceamento de arvore AVL

Programação Java
#1

Galera eu to precisando de um metodo pra balancear uma arvore avl, eu fiz o tradicional: uma classe No e essa classe tem uma variavel filhoEsquerda e uma filhoDireita, criei os metodos de inserir, localizar e deletar. Agora eu preciso de um metodo q verifique se a arvore esta balanceada e se nao estiver faça o balanceamento. Alguem pode me ajudar?

#2

Bom concegui eu msm fazer os metodos, to postando pra se alguem algum dia precisar…

protected void balanceia(no atual) {
		no aux = new no();
		no aux2 = new no();
		if ((atual != null) && (atual.direita != null)
				&& (atual.direita.direita != null)
				&& (fatorBalanceamento(atual) == -2)
				&& (fatorBalanceamento(atual.direita) == -1)
				&& (fatorBalanceamento(atual.direita.direita) == -1)) {
			if (localizaPai(atual.chave).direita == atual) {
				localizaPai(atual.chave).direita = atual.direita;
			} else {
				localizaPai(atual.chave).esquerda = atual.direita;
			}
			;
			aux = atual;
			atual = atual.direita;
			aux.direita = atual.esquerda;
			atual.esquerda = aux;
		} else if ((atual != null) && (atual.esquerda != null)
				&& (atual.esquerda.esquerda != null)
				&& (fatorBalanceamento(atual) == 2)
				&& (fatorBalanceamento(atual.esquerda) == 1)
				&& (fatorBalanceamento(atual.esquerda.esquerda) == 1)) {
			if (localizaPai(atual.chave).direita == atual) {
				localizaPai(atual.chave).direita = atual.esquerda;
			} else {
				localizaPai(atual.chave).esquerda = atual.esquerda;
			}
			;
			aux = atual;
			atual = atual.esquerda;
			aux.esquerda = atual.direita;
			atual.direita = aux;

		} else if ((atual != null) && (atual.esquerda != null)
				&& (atual.esquerda.direita != null)
				&& (fatorBalanceamento(atual) == 2)
				&& (fatorBalanceamento(atual.esquerda) == -1)
				&& (fatorBalanceamento(atual.esquerda.direita) == 1)) {
			if (localizaPai(atual.chave).direita == atual) {
				localizaPai(atual.chave).direita = atual.esquerda.direita;
			} else {
				localizaPai(atual.chave).esquerda = atual.esquerda.direita;
			}
			;
			aux = atual;
			aux2 = atual.esquerda;
			atual = atual.esquerda.direita;
			aux2.direita = atual.esquerda;
			aux.esquerda = atual.direita;
			atual.direita = aux;
			atual.esquerda = aux2;

		} else if ((atual != null) && (atual.direita != null)
				&& (atual.direita.esquerda != null)
				&& (fatorBalanceamento(atual) == -2)
				&& (fatorBalanceamento(atual.direita) == 1)
				&& (fatorBalanceamento(atual.direita.esquerda) == -1)) {
			if (localizaPai(atual.chave).direita == atual) {
				localizaPai(atual.chave).direita = atual.direita.esquerda;
			} else {
				localizaPai(atual.chave).esquerda = atual.direita.esquerda;
			}
			;
			aux = atual;
			aux2 = atual.direita;
			atual = atual.direita.esquerda;
			aux.direita.esquerda = atual.direita;
			aux.direita = atual.esquerda;
			atual.direita = aux;
			atual.esquerda = aux2;

		}

	}

	public no localizaPai(int chave) {
		no atual = primeiro;
		no pai = new no();
		while (atual.chave != chave) {
			if (chave < atual.chave) { 
				pai = atual;
				atual = atual.esquerda;
			} else {
				pai = atual;
				atual = atual.direita; 
			}
			if (atual == null) 
				return null; 
		}
		return pai;
	}

protected int fatorBalanceamento(no atual) {
		int fatorbalanceamento = 0;
		if ((atual.esquerda != null) && (atual.direita != null)) {
			fatorbalanceamento = atual.esquerda.altura()
					- atual.direita.altura();

		} else if ((atual.esquerda == null) && (atual.direita != null)) {
			fatorbalanceamento = -1 - atual.direita.altura();
		} else if ((atual.esquerda != null) && (atual.direita == null)) {
			fatorbalanceamento = atual.esquerda.altura() + 1;
		}
		return fatorbalanceamento;
	}
#3