Fórum Problema na implementação de arvore AVL (Remover) #572603

package controller;

public class AvlArvore {
	public AvlNo raiz = null;

	public AvlArvore() {
		raiz = null;
	}

	public void clear() {
		raiz = null;
	}

	public boolean isEmpty() {
		return raiz == null;
	}

	public AvlNo getraizNo() {
		return raiz;
	}

	/** Retorna a altura da árvore */
	private static int altura(AvlNo t) {
		return t == null ? -1 : t.altura;
	}

	/**
	 * Retorna o maior valor ente es e di.
	 */
	private static int max(int es, int di) {
		return es > di ? es : di;
	}

	/** Retorna o fator de balanceamento da árvore com raiz t */
	public int getFator(AvlNo t) {
		return altura(t.esq) - altura(t.dir);
	}

	public boolean inserir(int x) {
		raiz = inserir(x, raiz);
		return true;
	}

	private AvlNo inserir(int x, AvlNo t) {
		if (t == null)
			t = new AvlNo(x, null, null,null);
		else if (x < t.key){
			t.esq = inserir(x, t.esq);
			t.setPai(raiz);
		}
		else if (x > t.key){
			t.dir = inserir(x, t.dir);
			t.setPai(raiz);
		}
		t = balancear(t);
		return t;
	}

	public AvlNo balancear(AvlNo t) {
		if (getFator(t) == 2) {
			if (getFator(t.esq) > 0)
				t = RotacaoDir(t);
			else
				t = RotacaoDuplaDir(t);
		} else if (getFator(t) == -2) {
			if (getFator(t.dir) < 0)
				t = RotacaoEsq(t);
			else
				t = RotacaoDuplaEsq(t);
		}
		t.altura = max(altura(t.esq), altura(t.dir)) + 1;
		return t;
	}

	/** Faz Rotação simples a direita */
	private static AvlNo RotacaoDir(AvlNo x2) {
		AvlNo x1 = x2.esq;
		x2.esq = x1.dir;
		x1.dir = x2;
		x2.altura = max(altura(x2.esq), altura(x2.dir)) + 1;
		x1.altura = max(altura(x1.esq), x2.altura) + 1;
		return x1;
	}

	/** Rotação simples à esquerda */
	private static AvlNo RotacaoEsq(AvlNo x1) {
		AvlNo x2 = x1.dir;
		x1.dir = x2.esq;
		x2.esq = x1;
		x1.altura = max(altura(x1.esq), altura(x1.dir)) + 1;
		x2.altura = max(altura(x2.dir), x1.altura) + 1;
		return x2;
	}

	/** Rotação dupla à direita */
	private static AvlNo RotacaoDuplaDir(AvlNo x3) {
		x3.esq = RotacaoEsq(x3.esq);
		return RotacaoDir(x3);
	}

	/** Rotação dupla à esquerda */
	private static AvlNo RotacaoDuplaEsq(AvlNo x1) {
		x1.dir = RotacaoDir(x1.dir);
		return RotacaoEsq(x1);
	}

	public AvlNo procurar(int el) {
		return procurar(raiz, el);
	}

	protected AvlNo procurar(AvlNo p, int x) {
		while (p != null) {
			/* se valor procuradp == chave do nó retorna referência ao nó */
			if (x == p.key)
				return p;
			else if (x < p.key)
				p = p.esq;
			/*
			 * se valor procurado > chave do nó, procurar na sub-árvore direita
			 * deste nó
			 */
			else
				p = p.dir;
		}
		// caso chave não foi achada, retorna null
		return null;
	}
	public void remover(int x) {
		removerAVL(this.raiz, x);
	}

	public void removerAVL(AvlNo atual, int x) {
		if (atual == null) {
			return;

		} else {

			if (atual.key > x) {
				removerAVL(atual.esq, x);

			} else if (atual.key < x) {
				removerAVL(atual.dir, x);

			} else if (atual.key == x) {
				removerAvlNoEncontrado(atual);
			}
		}
	}

	public void removerAvlNoEncontrado(AvlNo remover) {
		AvlNo r;
		if (remover.getEsq() == null || remover.getDir() == null) {

			if (remover.getPai() == null) {
				this.raiz = null;
				remover = null;
				return;
			}
			r = remover;

		} else {
			r = sucessor(remover);
			remover.setKey(r.getKey());
		}

		AvlNo p = null;
		if (r.getEsq() != null) {
			p = r.getEsq();
		} else {
			p = r.getDir();
		}

		if (p != null) {
			p.setPai(r.getPai());
		}

		if (r.getPai() == null) {
			this.raiz = p;
		} else {
			if (r == r.getPai().getEsq()) {
				r.getPai().setEsq(p);;
			} else {
				r.getPai().setDir(p);
			}
			balancear(r.getPai());
		}
		r = null;
	}
	public AvlNo sucessor(AvlNo q) {
		if (q.getDir() != null) {
			AvlNo r = q.getDir();
			while (r.getEsq() != null) {
				r = r.getEsq();
			}
			return r;
		} else {
			AvlNo p = q.getPai();
			while (p != null && q == p.getDir()) {
				q = p;
				p = q.getPai();
			}
			return p;
		}
	}

	public void inorder() {
		inorder(raiz);
	}

	protected void inorder(AvlNo p) {
		if (p != null) {
			inorder(p.esq);
			System.out.print(p.key + " - ");
			inorder(p.dir);
		}
	}

	public void preorder() {
		preorder(raiz);
	}

	protected void preorder(AvlNo p) {
		if (p != null) {
			System.out.print(p.key + " ");
			preorder(p.esq);
			preorder(p.dir);
		}
	}

	public void postorder() {
		postorder(raiz);
	}

	protected void postorder(AvlNo p) {
		if (p != null) {
			postorder(p.esq);
			postorder(p.dir);
			System.out.print(p.key + " ");
		}
	}

	protected AvlNo procurarpai(int x) {
		AvlNo p = raiz;
		AvlNo prev = null;
		while (p != null && !(p.key == x)) { // acha o nó p com a chave x
			prev = p;
			if (p.key < x)
				p = p.dir;
			else
				p = p.esq;
		}
		if (p != null && p.key == x)
			return prev;
		return null;
	}	
	public void mostrar() {
		if (isEmpty()) {
			System.out.println("Árvore vazia!");
			return;
		}
		System.out.println(raiz.key + "(raiz " + "FB: " + getFator(raiz) + ")" + "\\n");
		String separator = String.valueOf("  |__");
		mostrarSubArvore(raiz.esq, separator);
		mostrarSubArvore(raiz.dir, separator);
	}

	public void mostrarSubArvore(AvlNo No, String separator) {
		if (No != null) {
			AvlNo pai = procurarpai(No.key);
			if (No.equals(pai.esq) == true) {
				System.out.println(separator + No.key + "(" + "pai: " + pai.key + " FB: " + getFator(No) + ")" + "\\n");
			} else {
				System.out.println(separator + No.key + "(" + "pai: " + pai.key + " FB: " + getFator(No) + ")" + "\\n");
			}
			mostrarSubArvore(No.esq, "     " + separator);
			mostrarSubArvore(No.dir, "     " + separator);
		}
	}
	public static void main(String[] args) {
		AvlArvore c = new AvlArvore();
		c.inserir(1);
		c.inserir(2);
		c.inserir(3);
		c.inserir(4);
		c.inserir(5);
		c.inserir(6);
		c.inserir(7);
		c.inserir(8);
		c.inserir(9);
		c.inserir(10);
		c.remover(9);
		c.mostrar();
	}
}