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.