Jump to content

Stergerea Unui Nod Dintr-Un Abc Echilibrat Avl

skyler_sdf

By +skyler_sdf
in C / C++ / C#

 Share

Recommended Posts

skyler_sdf Proficient

+skyler_sdf

Posted
Posted

Un arbore binar de cautare(ABC) echilibrat AVL este un arbore in care in fiecare nod are proprietatea ca inaltimile subarborilor stang si drept difera cu cel mult 1.

Avem 3 situatii posibile in acest nod, codificate cu valorile variabilei FactEch=(inaltimea subarborelui drept)-(inaltimea subarborelui stang), pe care o numim fator de echilibru, in felul urmator:

FactEch=

1, daca h(left)=h(right)-1

0, h(left)=h(right)

-1, daca h(left)=h(right)+1, unde h reprezinta inaltimea, left si right=subarborele stang, respectiv subarborele drept

In vederea echilibrarii arborelui vom folosi functii de rotatie, in functie de valoarea factorului de echilibru.

Un exemplu finalizat cu desene si explicatii pentru fiecare rotatie- aici: Link sau aici: Link

#include<stdio.h>

#include<malloc.h>

#define F 0

#define T 1

struct nod{

	char info;

	int FactEch;

	struct nod *st;

                  struct nod *dr;

};

struct nod *inserare( char , struct nod * , int * );

void listare(struct nod * , int );

struct nod *echilibrare_dr(struct nod * , int * );

struct nod *echilibrare_st(struct nod * , int * );

struct nod *sterge(struct nod * , struct nod * , int * );

struct nod *sterge_element(struct nod * , char , int * );


struct nod *inserare(char info, struct nod *tata, int *H)

{

struct nod *nod1;

struct nod *nod2;

if(!tata)

{

	tata=(struct nod*)malloc(sizeof(struct nod));

	tata->info=info;

	tata->st=NULL;

	tata->dr=NULL;

	tata->FactEch=0;

	*H=T;

	return tata;

}

if(info<tata->info)

{

	tata->st=inserare(info, tata->st, H);

	if(*H) //creste inaltimea subarborelui stang

	{

    switch(tata->FactEch)

		{


		case 1: //subarborele drept este mai inalt

			tata->FactEch=0;

			*H=F;

			break;

		case 0: //subarbore echilibrat

			tata->FactEch=-1;

			break;

                                    case -1: //subarborele stang mai inalt

                                                 nod1=tata->st;

                                                 if(nod1->FactEch==-1)

                                                   {

                                                     printf("Rotatie simpla la dreapta \n");

			tata->st=nod1->dr;

			nod1->dr=tata;

			tata->FactEch=0;

			tata=nod1;

			tata->FactEch=0;

			}

			else

				//cazul nod1->FactEch==0 nu este posibil pentru ca am fi avut *h=1

				//ramane nod1->FactEch==1

			{


				printf("Rotatie dubla la dreapta \n");

				nod2=nod1->dr;

				nod1->dr=nod2->st;

				nod2->st=nod1;

				tata->st=nod2->dr;

				nod2->dr=tata;

				if(nod2->FactEch==-1)

					tata->FactEch=1;

				else

					if(nod2->FactEch==1)

						nod1->FactEch=-1;

					else

						nod1->FactEch=0;

				tata=nod2;


			}

			tata->FactEch=0;

			*H=F;

		}

	}

}

if(info>tata->info)

{


	tata->dr=inserare(info, tata->dr, H);

	//subarborele drept devine mai inalt

	switch(tata->FactEch)

	{


	case -1: 

		//subarborele stang este mai inalt

		tata->FactEch=0;

		*H=F;

    break;

	case 1:

		//subarborele drept este mai inalt

		nod1=tata->dr;

		if(nod1->FactEch==1)

		{

			printf("Rotatie simpla la stanga \n");

			tata->dr=nod1->st;

			nod1->st=tata;

			tata->FactEch=0;

			tata=nod1;

			tata->FactEch=0;


		}

		else

			//cazul nod1->FactEch==0 nu este posibil pentru ca am fi avut *H=F

			//ramane nod1->FactEch==-1

		{


			printf("Rotatie dubla la stanga \n");

			nod2=nod1->st;

			nod1->st=nod2->dr;

			nod2->dr=nod1;

			tata->dr=nod2->st;

			nod2->st=tata;

			if(nod2->FactEch==1)

				tata->FactEch=-1;

			else

				if(tata->FactEch==1)

					nod1->FactEch=1;

				else

					nod1->FactEch=0;

			tata=nod2;

		}

		tata->FactEch=0;

		*H=F;

	}

}


return tata;

}

void listare(struct nod *arbore, int nivel)

{


	int i;

	if(arbore)

	{

		listare(arbore->dr, nivel+1);

		printf("\n");

		for(i=0; i<nivel; i++)

			printf(" ");

		printf("%c", arbore->info);

		listare(arbore->st, nivel+1);

	}

}

struct nod *echilibraredreapta(struct nod *tata, int *H)

{

	struct nod *nod1, *nod2;

	switch(tata->FactEch)

	{


	case 1:

		tata->FactEch=0;

		break;

	case 0: 

		tata->FactEch=1;

		*H=F;

		break;

	case -1:

		//re echilibrare

		nod1=tata->dr;

		if(nod1->FactEch>=0)

		{


			printf("Rotatie simpla la stanga \n");

			tata->dr=nod1->st;

			nod1->st=tata;

			if(nod1->FactEch==0)

			{


				tata->FactEch=1;

				nod1->FactEch=-1;

				*H=F;

			}

			else

			{


				tata->FactEch=nod1->FactEch=0;

			}

			tata=nod1;

		}

		else

		{


			printf("Rotatie dubla la stanga \n");

			nod2=nod1->st;

			nod1->st=nod2->dr;

			nod2->dr=nod1;

			tata->dr=nod2->st;

			nod2->st=tata;

			if(nod2->FactEch==1)

				tata->FactEch=-1;

			else

				tata->FactEch=0;

			if(nod2->FactEch==-1)

				nod1->FactEch=1;

			else

				nod1->FactEch=0;

			tata=nod2;

			nod2->FactEch=0;


		}

	}

	return tata;

}

struct nod *echilibrarestanga(struct nod *tata, int *H)

{


	nod *nod1, *nod2;

	switch(tata->FactEch)

	{

	case 1:

		tata->FactEch=0;

		break;

	case 0:

		tata->FactEch=-1;

		*H=F;

      break;

	case -1:

		//re echilibrare

		nod1=tata->st;

		if(nod1->FactEch<=0)

		{


			printf("Rotatie simpla la dreapta \n");

			tata->st=nod1->dr;

			nod1->dr=tata;

			if(nod1->FactEch==0)

			{


				tata->FactEch=-1;

				nod1->FactEch=1;

				*H=F;

			}

			else{

				tata->FactEch=nod1->FactEch=0;

			}

			tata=nod1;

		}

		else

			{


				printf("Rotatie dubla la dreapta\n");

				nod2=nod1->dr;

				nod1->dr=nod2->st;

				nod2->st=nod1;

				tata->st=nod2->dr;

				nod2->dr=tata;

				if(nod2->FactEch==-1)

					tata->FactEch=1;

				else

					tata->FactEch=0;

				if(nod2->FactEch==1)

					nod1->FactEch=-1;

				else

					nod1->FactEch=0;

				tata=nod2;

				nod2->FactEch=0;

			}

		}

		return tata;

		}

	//inlocuieste informatia nodului temp in care a fost gasita cheia cu informatia celui mai din dreapta descendent al lui r(pe care apoi il sterge

struct nod *sterge(struct nod *r, nod *temp, int *H)

{


	nod *dnod=r;

	if(r->dr!=NULL)

	{


		r->dr=sterge(r->dr, temp, H);

		if(*H)

			r=echilibrarestanga(r, H);

	}

	else

	{


		dnod=r;

		temp->info=r->info;

		r=r->st;

		free(dnod);

		*H=T;

	}

		return r;


}

//sterge element cu cheia respectiva din  arbore

struct nod *stergeelement(struct nod *tata, char info, int *H)

{

 nod *temp;

 if(!tata)

 {


	 printf("Informatia/nodul nu exista \n");

	 return tata;

 }

 else

 {


	 if(info<tata->info)

	 {

		 tata->st=stergeelement(tata->st, info, H);

		 if(*H)

			 tata=echilibraredreapta(tata, H);

 }

	 else

		 if(info>tata->info)

		 {

			 tata->dr-stergeelement(tata->dr, info, H);

			 if(*H)

				 tata=echilibrarestanga(tata, H);


		 }

		 else

		 {


			 temp=tata;

			 if(temp->dr==NULL)

			 {

				 tata=temp->st;

				 *H=T;

				 free (temp);

		 }

			 else

				 if(temp->st==NULL)

				 {


					 tata=temp->dr;

					 *H=T;

					 free (temp);

				 }

				 else

				 {


					 temp->st=stergeelement(temp->st, info, H);

					 if(*H)

						 tata=echilibraredreapta(tata, H);

				 }

		 }

}

 return tata;

}

void main()

{

	int H;

	char info;

	char choice;

	struct nod *arbore=(struct nod* )malloc(sizeof(struct nod));

	arbore=NULL;

	printf("Tastati 'b' pentru terminare: \n");

	choice=getchar();

	while(choice!='b')

	{         fflush(stdin);

		printf("Informatia nodului (tip caracter: a, b, 1, 2, etc.): \n");

		scanf("%c", &info);

		arbore=inserare(info, arbore, &H);

        printf("Arborele este: \n");

		listare(arbore, 1);   fflush(stdin);

		printf("Tastati 'b' pentru terminare: \n");

		choice=getchar();

		}  fflush(stdin);

	while(1)

	{


	printf("Introduceti cheia pe care vreti sa o stergeti: \n");

	scanf("%c", &info);

	if(info=='b')

	break;

	arbore=stergeelement(arbore, info, &H);

	printf(" Arborele este: \n");

	listare(arbore, 1);

	}

	}

Please sign in to comment

You will be able to leave a comment after signing in



Sign In Now
 Share
Go to topic listing

  • Recently Browsing   0 members

    • No registered users viewing this page.
×
×
  • Create New...

Important Information

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.