Remoção Árvore AVL

3 de maio de 2011 2 respostas

jayBean 3 de maio de 2011

Buenas rapaziada!
Tudo certinho?
Estou estudando árvores e recursão em C++, e estou batendo pino com a remoção de um nó em uma árvore AVL, estou tentando implementar a idéia de pegar o menor elemento a direita do nó para fazer a substituição. Alcançar este nó não é o problema, porém fazer a troca dos ponteiros está complicada, na verdade trocar os ponteiros quando estou removendo a raiz que está sendo complicado, ou seja, é um caso a parte.

pensando na interface da árvore tenho:

nodeTreeInt* treeIntAVL::remove(int valor){
	return raiz->remove(valor);
}

e agora sim a implementação de verdade:

nodeTreeInt* nodeTreeInt::remove(int valor){
	if(this == NULL) return NULL;
	if(this->getDado() == valor){
		if(this->isFolha()){
			delete(this);
			return NULL;
		}else{
			nodeTreeInt *substituto = getMenor(this->getDir()); // pega o substituto
			this->setDir(NULL);
			nodeTreeInt *aux = this;
			substituto->setEsq(this->getEsq());
			substituto->setDir(this->getDir());			
			if(substituto->getFb() == 2 && substituto->getEsq()->getFb()== -1){
				//rotaciona filho esq a esquerda 
				//rotaciona esse ? direita
				this->setEsq(this->getEsq()->rotacionaEsquerda());
				return (this->rotacionaDireita());		
			}
			if(substituto->getFb() == -2 && substituto->getDir()->getFb() == 1){
				//rotaciona filho a direita
				//rotaciona esse ? esquerda
				this->setDir(this->getDir()->rotacionaEsquerda());
				return (this->rotacionaEsquerda());
			}
			if(substituto->getFb() == 2) return (substituto->rotacionaDireita());
			if(substituto->getFb() == -2) return (substituto->rotacionaEsquerda());
			return substituto;
		}
	}
	if(valor > this->getDado()){
		this->setDir(this->getDir()->remove(valor));
		return this->getDir();
	}
	if(valor < this->getDado()){
		this->setEsq(this->getEsq()->remove(valor));
		return this->getEsq();
	}	
}

Podem me dar uma luz?

Abraço!

2 Respostas

jayBean 3 de mai. de 2011

Aqui está outra tentativa frustrada, na verdade era esperado que não funcionasse, seria absurdo conseguir atribuir outro ponteiro para o “this”.

nodeTreeInt* treeIntAVL::remove(int valor){
	if(valor == this->getRaiz()->getDado()){
		this->setRaiz(raiz->remove(valor));
		return this->getRaiz();
	}
	return raiz->remove(valor);
}

nodeTreeInt* nodeTreeInt::remove(int valor){
	if(this == NULL) return NULL; // não existe
	if(valor < this->getDado()){ //delegação
		this->setDir(this->getEsq()->remove(valor));
		return (this->balancear());
	}
	if(valor > this->getDado()){ //delegação
		this->setEsq(this->getDir()->remove(valor));
		return(this->balancear());
	}
	if(this->getEsq() != NULL || this->getDir() != NULL){//1 nó filho
		nodeTreeInt *no = this;
		if(this->getEsq() != NULL){
			this = this->getEsq();
		}else{
			this = this->getEsq();
		}
		delete no;
		return this->balancear();		
	}else{ // 2 nós filhos
		this->setDado(getMenor(this->getDir())->getDado());
		this->getDir()->remove(this->getDado());
		return (this->balancear());
	}	
}

alguém ?

jayBean 3 de mai. de 2011

Bem, consegui… Deixarei o código caso alguém um dia precisa de uma referência.

nodeTreeInt* treeIntAVL::remove(int valor){
	if(valor == this->getRaiz()->getDado()){
		this->setRaiz(this->getRaiz()->remove(valor));
	}
	return this->getRaiz()->remove(valor);
}

nodeTreeInt* nodeTreeInt::remove(int valor){
	if(this == NULL) return NULL;
	if(valor < this->getDado()){
		this->setEsq(this->getEsq()->remove(valor)->balancear());
		return this->balancear();
	}
	if(valor > this->getDado()){
		this->setDir(this->getDir()->remove(valor)->balancear());
		return this->balancear();
	}
	if(this->getEsq() == NULL || this->getDir() == NULL){
		nodeTreeInt *node = this;
		if(node->getEsq() != NULL){
			node = node->getEsq();
		}else{
			node = node->getDir();
		}
		delete this;
		return node;
	}else{
		this->setDado(this->getMenor(this->getDir())->getDado());
		this->setDir(this->getDir()->remove(this->getDado()));
		return this->balancear();
	}
	return NULL;
}

Abraço!

Criado 3 de maio de 2011

Ultima resposta 3 de mai. de 2011

Respostas 2

Participantes 1

2 Respostas

Topicos relacionados