Dúvidas sobre rotação de árvores e (seta) -> [RESOLVIDO]

FilipeBraz
(usa Arch Linux)

Enviado em 07/06/2017 - 12:42h

Boa tarde Pessoal,
o código a seguir é um código incompleto, porém tenho muita dúvida em relação às setas e como proceder com o balanceamento da árvore. Na teoria entendo muito bem, mas para a implantação já me complico.

#include <stdio.h>

#include <iostream>

#include <string>

#include <conio.h>

#include <stdlib.h>

#include <locale.h>



//Definimos o registro que representará cada elemento da árvore avl



struct ARVORE{

	int num, altd, alte;

	ARVORE *dir, *esq;

};



ARVORE* rotacao_esquerda(ARVORE* aux){

	ARVORE *aux1, *aux2;

	aux1 = aux->dir; 

	aux2 = aux1->esq;

	aux->dir = aux2;

	aux1->esq = aux;

	if(aux->dir == NULL){

		aux->altd=0;

	}else if (aux->dir->alte > aux->dir->altd){

		aux->altd = aux->dir->alte+1;

	} else{

		aux->altd = aux->dir->altd+1;

	}

	

	if(aux1->esq->alte > aux1->esq->altd){

		aux1->alte = aux1->esq->alte+1;

	} else{

		aux1->alte = aux1->esq->altd+1;

	}

	return aux1;

}



ARVORE* rotacao_direita(ARVORE* aux){

	ARVORE *aux1, *aux2;

	aux1 = aux->esq;

	aux2 = aux1->dir;

	aux->esq = aux2;

	aux1->dir = aux;

	if(aux->esq == NULL){

		aux->alte=0;

	}else if (aux->esq->alte > aux->esq->altd){

		aux->alte = aux->esq->alte+1;

	} else{

		aux->alte = aux->esq->altd+1;

	}

	

	if(aux1->dir->alte > aux1->dir->altd){

		aux1->altd = aux1->dir->alte+1;

	} else{

		aux1->altd = aux1->dir->altd+1;

	}

	return aux1;

}



ARVORE* balanceamento(ARVORE *aux){

	int d, df;

	d= aux->altd - aux->alte;

	if(d == 2){

		df = aux->dir->altd - aux->dir->alte;

		if (df>=0){

			aux = rotacao_esquerda(aux);

		} else{

			aux->dir=rotacao_direita(aux->dir);

			aux = rotacao_esquerda(aux);

		}

	} else if(d == -2){

		df = aux->esq->altd - aux->esq->alte;

		if(df <= 0){

			aux = rotacao_direita(aux);

		} else{

			aux->esq = rotacao_esquerda(aux->esq);

			aux = rotacao_direita(aux);

		}

	}

	return aux;

}



ARVORE* inserir(ARVORE *aux, int num){

	ARVORE *novo;

	if(aux == NULL){

		novo = new ARVORE();

		novo->num = num;

		novo->altd = 0;

		novo->alte = 0;

		novo->esq = NULL;

		novo->dir = NULL;

		aux = novo;

	} else if(num < aux->num){

		aux->esq = inserir(aux->esq, num);

		if(aux->esq->altd > aux->esq->alte){

			aux->alte = aux->esq->altd+1;

		} else{

			aux->alte = aux->esq->alte+1;

		}

		

		aux = balanceamento(aux);

	} else{

		aux->dir = inserir(aux->dir, num);

		if(aux->dir->altd > aux->dir->alte){

			aux->altd = aux->dir->altd+1;

		} else{

			aux->altd = aux->dir->alte+1;

		}

		

		aux = balanceamento(aux);

	}

	return aux;

}



ARVORE* desalocar(ARVORE* aux){

	if(aux != NULL){

		aux->esq = desalocar(aux->esq);

		aux->dir = desalocar(aux->dir);

		delete aux;

	}

	return NULL;

}



int main(void) {

	ARVORE *raiz = NULL;

	ARVORE *aux;

	int op, achou, numero;

	do{

		std::cout << "\n1 - Inserir";

		std::cout << "\n2 - Consultar";

		std::cout << "\n3 - Mostrar os elementos da Árvore em ordem";

		std::cout << "\n4 - Esvaziar";

		std::cout << "\n0 - Sair";

		std::cout << "\nDigite sua opcao: ";

		std::cin >> op;

		if(op < 0 || op > 5){

			std::cout << "\nOpcao invalida!!!";

		} else if(op == 1){

			

		}else if(op == 2){

			

		}else if(op == 3){

			

		}else if(op == 4){

			

		}

	}while (op!= 0);

	raiz = desalocar(raiz);

	return 0;

} 

paulo1205
(usa Ubuntu)

Enviado em 07/06/2017 - 18:57h

Com relação ao operador ->, ele existe para que você possa fazer acesso aos membros de uma estrutura indicada por um ponteiro, sem precisar derreferenciar a estrutura toda de uma vez.

struct item_t {

  char nome[40];

  char descricao[100];

  unsigned quantidade;

  double preco;

};



void imprime_item(struct item_t *p_item){

  printf(

    "Nome do item: %s\n"

    "   Descrição: %s\n"

    "   Preço unitário: R$%02.f\n"

    "   Quantidade em estoque: %u\n",

    p-Item->nome, p_item->descricao,

    p_item->preco, p_item->quantidade

  );

} 

A rigor, o operador -> não seria estritamente necessário. Você pode obter o mesmo efeito final usando derreferência do ponteiro, seguida do acesso ao campo do objeto derreferenciado.

if(p_item->preco != (*p_item).preco)

  fprintf(stderr, "Essa situação é impossível, pois os dois lados são sinônimos.  Esta mensagem nunca será impressa.\n"); 

Se as duas coisas são sinônimas, por que não suprimir o ->? Existe uma razão histórica, implicada pelo comportamento de versões muito antigas do C (veja https://stackoverflow.com/questions/13366083/why-does-the-arrow-operator-in-c-exist, que é uma explicação bem completa, por sinal).

Teoricamente, hoje já não seriam mais necessários dois operadores distintos em C, mas acaba que “a->b” consome um caráter a menos no arquivo, de duas a quatro teclas a menos na hora de digitar, e menos poluição visual na tela. Fora isso, em C++ existe uma outra vantagem, que é a de poder fazer sobrecarga do operador -> (o operador ., por outro lado, não pode ser sobrecarregado).

FilipeBraz
(usa Arch Linux)

Enviado em 08/06/2017 - 21:38h

Ah sim, no caso então a seta é usada para acessar o membro de uma estrutura referenciada pelo ponteiro... Irei fazer os testes aqui, obrigado.