Arborii binari de cautare

26
ARBORI BINARI DE CĂUTARE

Transcript of Arborii binari de cautare

Page 1: Arborii binari de cautare

ARBORI BINARI DE CĂUTARE

Page 2: Arborii binari de cautare

Arborii binari de cautare sunt des folositi pentru memorarea si regasirea rapida a unor informatii, pe baza unei chei. Fiecare nod al arborelui trebuie sa contina o cheie distincta.

Page 3: Arborii binari de cautare

Un asemenea arbore poate fi reprezentat de o structura de date înlantuita în care fiecare nod este un obiect. Într-un nod x avem |KEY | ADR | LS | LD | P | KEY(x) însemna valoarea cheii din nodul x, informatia de lânga KEY se mai numeste si informatie satelit (SAT), legatura la copilul din stânga, legatura la copilul din dreapta, si parintele nodului x. Daca un copil sau un parinte lipsesc, câmpul corespunzator va contine NIL. Fie un arbore care contine aceleasi chei cu cel din fig.8.l dar cu înaltimea 4 si mai putin eficient a carui reprezentare o gasiti în figura 8.2.

Page 4: Arborii binari de cautare

Definitie Un arbore binar de cautare este un arbore binar care satisface conditia:

a)       Pentru orice nod y care se afla într-un subarbore stâng al nodului x

KEY(y) ~ KEY(x)

b)      Pentru orice nod y care se afla într-un subarbore drept al nodului x

KEY(x) ~ KEY(y)

Aceasta proprietate a unui arbore binar de cautare ne permite sa extragem toate cheile sortate cu ajutorul unui simplu algoritm recursiv printr-o parcurgere în inordine.

INORD_PARC (x)

Daca LS(x) ¹ NIL atunci

Cheama INORD_P ARC(LS(x))

Scrie KEY (x)

Cheama INORD_P ARC(LD(x))

Page 5: Arborii binari de cautare

Structura unui nod al unui arbore binar de cautare este urmatoarea:

typedef struct tip_nod TIP_NOD;

În cele ce urmeaza, radacina arborelui se considera ca o variabila globala:

TIP_NOD *rad;

Structura arborelui de cautare depinde de ordinea de inserare

a nodurilor.

Page 6: Arborii binari de cautare

Constructia unui arbore binar de cautare se face prin inserarea a câte unui nod de cheie key.Algoritmul de inserare este urmatorul:

a) Daca arborele este vid, se creeaza un nou nod care este radacina, cheia având valoarea key, iar subarborii stâng si drept fiind vizi.

b) Daca cheia radacinii este egala cu key atunci inserarea nu se poate face întrucât exista deja un nod cu aceasta cheie.

Page 7: Arborii binari de cautare

c) Daca cheia key este mai mica decât cheia radacinii, se reia algoritmul pentru subarborele stâng (pasul a).

d) Daca cheia key este mai mare decât cheia radacinii, se reia algoritmul pentru subarborele drept (pasul a).

Page 8: Arborii binari de cautare

FUNCTIA NERECURSIVA DE INSERARE VA AVEA URMATORUL ALGORITM:VOID INSERARE_NERECURSIVA (INT KEY)/* ARBORELE NEFIIND VID SE CAUTA NODUL TATA PENTRU NODUL P */Q=RAD; /* RAD ESTE RADACINA ARBORELUI VARIABILA GLOBALA */FOR ( ; ; )ELSE Q=Q->STG;}ELSE IF (KEY>Q->CHEIE)ELSE Q=Q->DR;}        ELSE}   }

Page 9: Arborii binari de cautare

CAUTAREA UNUI NOD DE CHEIE DATA KEY ÎNTR-UN ARBORE BINAR DE CAUTARE.CAUTAREA ÎNTR-UN ARBORE BINAR DE CAUTARE A UNUI NOD DE CHEIE DATA SE FACE DUPA UN ALGORITM ASEMANATOR CU CEL DE INSERARE.NUMARUL DE CAUTARI OPTIM AR FI DACA ARBORELE DE CAUTARE AR FI TOTAL ECHILIBRAT (NUMARUL DE COMPARATII MAXIM AR FI LOG 2 N – UNDE N ESTE NUMARUL TOTAL DE NODURI).CAZUL CEL MAI DEFAVORABIL ÎN CEEA CE PRIVESTE CAUTAREA ESTE ATUNCI CÂND INSERAREA SE FACE PENTRU NODURILE AVÂND CHEILE ORDONATE CRESCATOR SAU DESCRESCATOR. ÎN ACEST CAZ, ARBORELE DEGENEREAZA ÎNTR-O LISTA.

Page 10: Arborii binari de cautare

ALGORITMUL DE CAUTARE ESTE REDAT PRIN FUNCTIA URMATOARE:TIP_NOD *CAUTARE (TIP_NOD *RAD, INT KEY)/* FUNCTIA RETURNEAZA ADRESA NODULUI ÎN CAZ DE GASIRE SAU 0 ÎN CAZ CA NU EXISTA UN NOD DE CHEIA KEY */   RETURN 0; /* NU EXISTA NOD DE CHEIE KEY */  }APELUL DE CAUTARE ESTE:P=CAUTARE (RAD, KEY);RAD FIIND POINTERUL SPRE RADACINA ARBORELUI.

Page 11: Arborii binari de cautare

ÎN CAZUL STERGERII UNUI NOD, ARBORELE TREBUIE SA-SI PASTREZE STRUCTURA DE ARBORE DE CAUTARE.LA STERGEREA UNUI NOD DE CHEIE DATA INTERVIN URMATOARELE CAZURI:A)           NODUL DE STERS ESTE UN  NOD FRUNZA. ÎN ACEST CAZ, ÎN NODUL TATA, ADRESA NODULUI FIU DE STERS (STÂNG SAU DREPT) DEVINE ZERO.B)           NODUL DE STERS ESTE UN  NOD CU UN SINGUR DESCENDENT. ÎN ACEST CAZ, ÎN NODUL TATA,ADRESA NODULUI FIU DE STERS SE ÎNLOCUIESTE CU ADRESA DESCENDENTULUI NODULUI FIU DE STERS.C)           NODUL DE STERS ESTE UN NOD CU DOI DESCENDENTI. ÎN ACEST CAZ, NODUL DE STERS SE ÎNLOCUIESTE CU NODUL CEL MAI DIN STÂNGA AL SUBARBORELUI DREPT SAU CU NODUL CEL MAI DIN DREAPTA AL SUBARBORELUI STÂNG.

Page 12: Arborii binari de cautare

ALGORITMUL DE STERGERE A UNUI NOD CONTINE URMATOARELE ETAPE:-    CAUTAREA NODULUI DE CHEIE KEY SI A NODULUI TATA CORESPUNZATOR;-    DETERMINAREA CAZULUI ÎN CARE SE SITUEAZA NODUL DE STERS.

Page 13: Arborii binari de cautare

STERGEREA UNUI ARBORE BINAR DE CAUTARE CONSTA ÎN PARCURGEREA ÎN POSTORDINE A ARBORELUI SI STERGEREA NOD CU NOD, CONFORM FUNCTIEI URMATOARE:VOID STERGERE_ARBORE(TIP_NOD *RAD)}

Page 14: Arborii binari de cautare

CA ORICE ARBORE BINAR, UN ARBORE BINAR DE CAUTARE POATE FI TRAVERSAT ÎN CELE TREI MODURI: ÎN PREORDINE, ÎN INORDINE SI ÎN POSTORDINE CONFORM FUNCTIILOR DE MAI JOS:VOID PREORDINE (TIP_NOD *P)           }VOID INORDINE (TIP_NOD *P)              }   VOID POSTORDINE (TIP_NOD *P)   }APELUL ACESTOR FUNCTII SE VA FACE ASTFEL:PREORDINE(RAD);INORDINE(RAD);POSTORDINE(RAD);

Page 15: Arborii binari de cautare

LUNGIMEA DRUMULUI DE CAUTARE A UNUI NOD CU CHEIA X, ÎNTR-UN ARBORE BINAR DE CAUTARE, ESTE NIVELUL HI AL NODULUI ÎN CARE SE AFLA CHEIA CAUTATA, ÎN CAZ DE SUCCES SAU 1 PLUS NIVELUL ULTIMULUI NOD ÎNTÂLNIT PE DRUMUL CAUTARII FARA SUCCES.FIE S = MULTIMEA CHEILOR CE CONDUC LA CAUTAREA CU SUCCES (C1 < C2 < ... < CN).FIE PI PROBABILITATEA CAUTARII CHEII CI (I=1,2,...,N).DACA NOTAM CU C, MULTIMEA CHEILOR POSIBILE, ATUNCI C S REPREZINTA MULTIMEA CHEILOR CE CONDUCE LA CAUTAREA FARA SUCCES. ACEASTA MULTIME O PARTITIONAM ÎN SUBMULTIMILE:K0 – MULTIMEA CHEILOR MAI MICI CA C1;KN – MULTIMEA CHEILOR MAI MARI CA CN;KI (I=1,2,...,N) – MULTIMEA CHEILOR ÎN INTERVALUL (CI, CI+1).FIE QI PROBABILITATEA CAUTARII UNEI CHEI DIN MULTIMEA KI.

Page 16: Arborii binari de cautare

CAUTAREA PENTRU ORICE CHEIE DIN KI SE FACE PE ACELASI DRUM; LUNGIMEA DRUMULUI DE CAUTARE VA FI H’

I.

NOTAM CU L COSTUL ARBORELUI, CARE REPREZINTA LUNGIMEA MEDIE DE CAUTARE:CU CONDITIA:

SE NUMESTE ARBORE OPTIMAL, UN ARBORE BINAR DE CAUTARE CARE PENTRU ANUMITE VALORI PI, QI DATE REALIZEAZA UN COST MINIM.ARBORII OPTIMALI DE CAUTARE NU SUNT SUPUSI INSERARILOR SI ELIMINARILOR.

Page 17: Arborii binari de cautare

SE NUMESTE ARBORE OPTIMAL, UN ARBORE BINAR DE CAUTARE CARE PENTRU ANUMITE VALORI PI, QI DATE REALIZEAZA UN COST MINIM.ARBORII OPTIMALI DE CAUTARE NU SUNT SUPUSI INSERARILOR SI ELIMINARILOR.DIN PUNCT DE VEDERE AL MINIMIZARII FUNCTIEI L, ÎN LOC DE PI SI QI SE POT FOLOSI FRECVENTELE  APARITIEI CAUTARILOR RESPECTIVE ÎN CAZUL UNOR DATE DE TEST.SE NOTEAZA CU AIJ ARBORELE OPTIMAL CONSTRUIT CU NODURILE CI+1, CI+2, ..., CJ.

Page 18: Arborii binari de cautare

GREUTATEA ARBORELUI AIJ ESTE:

CARE SE POATE CALCULA ASTFEL:

REZULTA CA COSTUL ARBORELUI OPTIMAL AIJ SE VA PUTEA CALCULA ASTFEL:

Page 19: Arborii binari de cautare

FIE RIJ VALOAREA LUI K PENTRU CARE SE OBTINE MINIMUL DIN RELATIA LUI CIJ. NODUL CU CHEIA C[RIJ] VA FI RADACINA SUBARBORELUI OPTIMAL AIJ, IAR SUBARBORII SAI VOR FI AI,K-1 SI AKJ.CALCULUL VALORILOR MATRICEI C ESTE DE ORDINUL O(N3). S-A DEMONSTRAT CA SE POATE REDUCE ORDINUL TIMPULUI DE CALCUL LA O(N2).CONSTRUIREA SE FACE CU AJUTORUL FUNCTIEI URMATOARE:TIP_NOD *CONSTR_ARBORE_OPTIMAL(INT I, INT J)RETURN P;}

Page 20: Arborii binari de cautare

PRIMUL PROGRAM PREZINTA TOATE FUNCTIILE DESCRISE ÎN LUCRARE ASUPRA UNUI ARBORE DE CAUTARE. UN NOD CONTINE DREPT INFORMATIE UTILA NUMAI CHEIA, CARE ESTE UN NUMAR ÎNTREG.AL DOILEA PROGRAM CONTINE FUNCTIILE PRINCIPALE ASUPRA UNUI ARBORE BINAR DE CAUTARE OPTIMAL.

Page 21: Arborii binari de cautare

EXEMPLUL NR.1 (ARBORI DE CAUTARE)#INCLUDE <STDIO.H>#INCLUDE <CONIO.H>#INCLUDE <ALLOC.H>TYPEDEF STRUCT TIP_NOD TIP_NOD;TIP_NOD *RAD;VOID PREORDINE(TIP_NOD *P, INT NIVEL)}VOID INORDINE(TIP_NOD *P, INT NIVEL)}VOID POSTORDINE(TIP_NOD *P, INT NIVEL)}VOID INSERARE(INT KEY)  Q=RAD;  FOR(;;)                                                    ELSE Q=Q->STG;                                            }            ELSE IF (KEY > Q->CHEIE)                                                        ELSE Q=Q->DR;                                                    }                     ELSE }            }TIP_NOD *INSERARE_REC(TIP_NOD *RAD,INT KEY)  ELSE              }   };

Page 22: Arborii binari de cautare

    RETURN RAD;}TIP_NOD * CAUTARE(TIP_NOD *RAD, INT KEY)  RETURN 0; /* NU EXISTA NOD DE CHEIE KEY */   }TIP_NOD *STERGERE_NOD(TIP_NOD *RAD,INT KEY)               ELSE       }     IF(P==0)      /* S-A GASIT NODUL P DE CHEIE KEY */      IF(P->STG==0) NOD_INLOCUIRE=P->DR; /* NODUL DE STERS P NU ARE FIU STING */ELSE IF(P->DR==0) NOD_INLOCUIRE=P->STG;    /*NODUL DE STERS P  NU ARE FIU DREPT*/      ELSE                IF(TATA_NOD_INLOCUIRE!=P)                                        NOD_INLOCUIRE->STG=P->STG;              }        FREE(P);        PRINTF("\NNODUL DE CHEIE=%D A FOST STERS!\N",KEY);       IF(TATA_P==0)  RETURN NOD_INLOCUIRE; /*S-A STERS CHIAR RADACINA INITIALA */       ELSE}VOID STERGERE_ARBORE(TIP_NOD *RAD)}

Page 23: Arborii binari de cautare

VOID MAIN(VOID)  PRINTF("\NVIZITAREA IN PREORDINE\N");  PREORDINE(RAD,0);  GETCH();  PRINTF("\NVIZITAREA IN INORDINE\N");  INORDINE(RAD,0);  GETCH();  PRINTF("VIZITAREA IN POSTORDINE\N");  POSTORDINE(RAD,0);  GETCH();  FFLUSH(STDIN);  PRINTF("\N DORITI SA CAUTATI UN NOD DA=D/D NU= ALT CARACTER :");  SCANF("%C",&CH);  WHILE((CH=='D')||(CH=='D'))                              FFLUSH(STDIN);  PRINTF("\N DORITI SA STERGET UN NOD DA=D/D NU= ALT CARACTER :");  SCANF("%C",&CH);  WHILE((CH=='D')||(CH=='D'))                            PRINTF("STERGETI ARBORELE CREAT ? DA=D/D NU=ALT CARACTER  "); FFLUSH(STDIN); SCANF("%C",&CH); IF((CH=='D')||(CH=='D')) GETCH();}.

Page 24: Arborii binari de cautare

EXEMPLUL NR.2 (ARBORI OPTIMALI)           #INCLUDE <STDIO.H>           #INCLUDE <CONIO.H>           #INCLUDE <ALLOC.H>           #DEFINE NMAX 25           TYPEDEF STRUCT TIP_NOD TIP_NOD;           CHAR CHEI[NMAX];  /* CHEILE C1,C2,...,CN */           INT P[NMAX];/* FRECVENTA DE CAUTARE A CHEILOR */           INT Q[NMAX]; /* FRECVENTA DE CAUTARE INTRE CHEI */           INT R[NMAX][NMAX]; /* RADACINILE SUBARBORILOR OPTIMALI */           VOID CALCUL(INT NR,FLOAT *DR_MED)                       /* CALCULUL MATRICEI C */             FOR(I=0;I<=NR;I++)                         C[I][I]=G[I][I];             FOR(I=0;I<=NR-1;I++)                                     /*CALCUL C[I][L+I] */             FOR(L=2;L<=NR;L++)                        FOR(I=0;I<=NR-L;I++)                                                                                     }

Page 25: Arborii binari de cautare

                                           C[I][L+I]=MIN+G[I][L+I];                                           R[I][L+I]=M;                                         }                        PRINTF("\NMATRICEA G\N");                        FOR(I=0;I<=NR;I++)                                                          GETCH();                        PRINTF("\NMATRICEA C\N");                        FOR(I=0;I<=NR;I++)                                                          GETCH();                        PRINTF("\NMATRICEA R\N");                        FOR(I=0;I<=NR;I++)                                                          GETCH();                        PRINTF("C[0][NR.]=%LD  G[0][NR.]=%LD\N",C[0][NR.],G[0][NR.]);                        GETCH();                        *DR_MED=C[0][NR.]/(FLOAT)G[0][NR.];          }           TIP_NOD* CONSTR_ARBORE(INT I,INT J)            /* CONSTRUIREA ARBORELUI OPTIMAL */                       RETURN P;           }           VOID INORDINE(TIP_NOD *P,INT NIVEL)                      }             VOID MAIN(VOID)

Page 26: Arborii binari de cautare

                      /*CITIREA FRECVENTELOR DE CAUTARE INTRE CHEI */                 FOR(I=0;I<=N;I++)                                       CALCUL(N,&DRUM_MEDIU);                   PRINTF("DRUMUL MEDIU=%6F\N",DRUM_MEDIU);                   GETCH();                   RADACINA=CONSTR_ARBORE(0,N);                   INORDINE(RADACINA,0);                  GETCH();            }