Jump to content
  • Revista PROGRAMAR: Já está disponível a edição #60 da revista programar. Faz já o download aqui!

Yasnac

Balancear árvores - rotações ED e DE

Recommended Posts

Yasnac

Boas.

Relativamente a balancear arvores, existem aquelas 4 rotações comuns: EE, DD, ED e DE. As duas primeiras já as consegui fazer, mas não estou a conseguir perceber o porquê das as outras não funcionarem. Como resolvo isto? 

typedef struct arvore {
	int data;
	struct arvore * esquerda;
	struct arvore * direita;
} *Arvore;

Arvore DD(Arvore pointer){
	int a,b;

	a = pointer->data;
	b = pointer->direita->direita->data;

	pointer->data = pointer->direita->data;
	pointer->direita->data = b;
	pointer->esquerda = pointer->direita->direita;
	pointer->direita->direita = NULL;
	pointer->esquerda->data = a;
	
	return pointer;
}

Arvore EE(Arvore pointer){
	int a,b;

	a = pointer->data;
	b = pointer->esquerda->esquerda->data;

	pointer->data = pointer->esquerda->data;
	pointer->esquerda->data = b;
	pointer->direita = pointer->esquerda->esquerda;
	pointer->esquerda->esquerda = NULL;
	pointer->direita->data = a;
	
	return pointer;
}

Arvore ED(Arvore pointer){

	int a,b,c;
	a = pointer->esquerda->direita->data;
	b = pointer->esquerda->data;
	c = pointer->data;

	pointer->esquerda->esquerda = pointer->esquerda;
	pointer->esquerda->direita = NULL;
	pointer->esquerda->data = a;


	EE(pointer);

	return pointer;
}

void balancear(Arvore pointer) {

	if(pointer!=NULL){
		// DD
		if((pointer->direita!=NULL) && (pointer->direita->direita!=NULL))  {
			printf("DD\n");
			DD(apt);
		}
		// EE
		else if ((pointer->esquerda!=NULL) && (pointer->esquerda->esquerda!=NULL)) {
			printf("EE\n");
			EE(apt);
		}
		// DE
		else if ((pointer->direita!=NULL) && (pointer->direita->esquerda!=NULL)) {
			printf("DE\n");
			DE(apt);
		}
		// ED
		else if ((pointer->esquerda!=NULL) && (pointer->esquerda->direita!=NULL)) {
			printf("ED\n");
			ED(apt);
			}
		}
}

 

Edited by Yasnac
faltava código para ajudar a perceber

Share this post


Link to post
Share on other sites
M6

Tens de ser mais claro e concreto nas tuas dúvidas. Referir que conseguiste 2 e que outras 2 não funcionam e não percebes o porquê não permite que alguém te ajude.
 


10 REM Generation 48K!
20 INPUT "URL:", A$
30 IF A$(1 TO 4) = "HTTP" THEN PRINT "400 Bad Request": GOTO 50
40 PRINT "404 Not Found"
50 PRINT "./M6 @ Portugal a Programar."

 

Share this post


Link to post
Share on other sites
Yasnac
3 horas atrás, M6 disse:

Tens de ser mais claro e concreto nas tuas dúvidas. Referir que conseguiste 2 e que outras 2 não funcionam e não percebes o porquê não permite que alguém te ajude.
 

Obrigado desde já pela resposta.

Para fazer os balanceamentos EE e DD, fiz um esquema género https://www.tutorialspoint.com/data_structures_algorithms/images/avl_left_rotation.jpg, dei valores de input p.e 7->8->9 e fui confirmando instrução a instrução. No final, consegui chegar ao balanceamento, quer EE, quer DD.

Para os desbalanceamentos ED e DE optei por criar um desbalanceamento EE e DD a partir destes para depois ser só aplicar um balanceamento EE e DD. Já confirmei várias vezes instrução a instrução, dando valores de input e no final ele dá-me Segmentation Fault. Não consigo perceber porquê e o que estou a fazer mal.

 

Obrigado!

Share this post


Link to post
Share on other sites
M6

O segmentation fault indica que estás a tentar aceder a um endereço de memória que não é teu. Toda a gente que já programou com apontadores já passou por isso! :D

Não tens ai o código todo, mas vejo ai um "apt" (apt->esquerda->data, por exemplo) que parece indicar uma variável global, o que nunca é bom presságio.
Vê em que linha tens o segmentation fault, provavelmente estás à espera de ter ai algo que já (ou ainda) ai não está.


10 REM Generation 48K!
20 INPUT "URL:", A$
30 IF A$(1 TO 4) = "HTTP" THEN PRINT "400 Bad Request": GOTO 50
40 PRINT "404 Not Found"
50 PRINT "./M6 @ Portugal a Programar."

 

Share this post


Link to post
Share on other sites
Yasnac
2 horas atrás, M6 disse:

O segmentation fault indica que estás a tentar aceder a um endereço de memória que não é teu. Toda a gente que já programou com apontadores já passou por isso! :D

Não tens ai o código todo, mas vejo ai um "apt" (apt->esquerda->data, por exemplo) que parece indicar uma variável global, o que nunca é bom presságio.
Vê em que linha tens o segmentation fault, provavelmente estás à espera de ter ai algo que já (ou ainda) ai não está.

Já editei. Em vez de apt é pointer. O código está todo aí e acrescentei a função balancear que testa se está desbalanceada e onde invoco as 4 rotações com as 4 situações possíveis.

O segmentation fault eu sei o que é mas não percebo mesmo de onde ele vem neste caso.

Obrigado!

Share this post


Link to post
Share on other sites
HappyHippyHippo

eu gostava de perceber porque razão uma rotação (qualquer que seja ela) leva a mexer nos ponteiros para os dados guardados nos nós, visto que uma rotação não é mais do que alterar os ponteiros para as subárvores ...


IRC : sim, é algo que ainda existe >> #p@p

Share this post


Link to post
Share on other sites
Yasnac
Em 01/06/2019 às 11:30, HappyHippyHippo disse:

eu gostava de perceber porque razão uma rotação (qualquer que seja ela) leva a mexer nos ponteiros para os dados guardados nos nós, visto que uma rotação não é mais do que alterar os ponteiros para as subárvores ...

Certo. E por isso já tentei fazer as rotações sem mexer nesses ponteiros. Fiz a rotação EE assim:
 

Arvore LL(Arvore pointer) {

   Arvore a = pointer->esquerda;
   Arvore b = pointer;

   b->esquerda = NULL;
   b->direita = NULL;

   a->direita = b;
   printf("a->valor %d\n",a->valor);
   printf("a->dir->valor %d\n",a->direita->valor);
   printf("a->esquerda->valor %d\n",a->esquerda->valor);

   return a;
}

Contudo, ele após inserir por exemplo os valores 10,9,8 executa isto:
https://imgur.com/y8EBDxy

a->valor 9

a->dir->valor 10

a->esquerda->valor 8

Listar crescente: 10



Estrutura: 10 ( ) ( )

Quantidade: 1



Altura: 1

Não percebo o porquê de ele imprimir mal a estrutura e a listagem.

Antes do return o a->valor tem um valor e depois do return tem outro. Porquê?

Obrigado!

Edited by Yasnac

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

×

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.