ARBORI BINARI DE CAUTARE

ARBORI BINARI DE CĂUTARE

1.   &nb 18118t1915s sp;  Continutul lucrarii

Īn lucrare sunt prezentate principalele operatii asupra arborilor binari de cautare: inserare, cautare, stergere, traversare. De asemenea sunt prezentati arborii binari de cautare optimali.

2.   &nb 18118t1915s sp;  Consideratii teoretice

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.

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.

2.1.   &nb 18118t1915s sp;  Inserarea īntr-un arbore binar 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)   &nb 18118t1915s sp;   &nb 18118t1915s sp;   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)   &nb 18118t1915s sp;   &nb 18118t1915s sp;   Daca cheia radacinii este egala cu key atunci inserarea nu se poate face īntrucāt exista deja un nod cu aceasta cheie.

c)   &nb 18118t1915s sp;   &nb 18118t1915s sp;   Daca cheia key este mai mica decāt cheia radacinii, se reia algoritmul pentru subarborele stāng (pasul a).

d)   &nb 18118t1915s sp;   &nb 18118t1915s sp;   Daca cheia key este mai mare decāt cheia radacinii, se reia algoritmul pentru subarborele drept (pasul a).

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

}

2.2   &nb 18118t1915s sp; 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 ₂ 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.

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.

2.3   &nb 18118t1915s sp; stergerea unui nod de cheie data īntr-un arbore binar 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)   &nb 18118t1915s sp;   &nb 18118t1915s sp;   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)   &nb 18118t1915s sp;   &nb 18118t1915s sp;   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)   &nb 18118t1915s sp;   &nb 18118t1915s sp;   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.

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.

2.4   &nb 18118t1915s sp; stergerea unui arbore binar 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)

2.5   &nb 18118t1915s sp; Traversarea unui arbore binar 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);

2.6   &nb 18118t1915s sp; Arbori binari de cautare optimali

Lungimea drumului de cautare a unui nod cu cheia x, īntr-un arbore binar de cautare, este nivelul h_i 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 (c₁ < c₂ < ... < c_n).

Fie p_i probabilitatea cautarii cheii c_i (i=1,2,...,n).

Daca notam cu C, multimea cheilor posibile, atunci CS reprezinta multimea cheilor ce conduce la cautarea fara succes. Aceasta multime o partitionam īn submultimile:

k₀ - multimea cheilor mai mici ca c₁;

k_n - multimea cheilor mai mari ca c_n;

k_i (i=1,2,...,n) - multimea cheilor īn intervalul (c_i, c_i+1).

Fie q_i probabilitatea cautarii unei chei din multimea k_i.

Cautarea pentru orice cheie din k_i 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 p_i, q_i 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 p_i si q_i se pot folosi frecventele aparitiei cautarilor respective īn cazul unor date de test.

Se noteaza cu A_ij arborele optimal construit cu nodurile c_i+1, c_i+2, ..., c_j.

Greutatea arborelui A_ij este:

care se poate calcula astfel:

Rezulta ca costul arborelui optimal A_ij se va putea calcula astfel:

Fie r_ij valoarea lui k pentru care se obtine minimul din relatia lui c_ij. Nodul cu cheia c[r_ij] va fi radacina subarborelui optimal A_ij, iar subarborii sai vor fi A_i,k-1 si A_kj.

Calculul valorilor matricei C este de ordinul O(n³). S-a demonstrat ca se poate reduce ordinul timpului de calcul la O(n²).

Construirea se face cu ajutorul functiei urmatoare:

TIP_NOD *constr_arbore_optimal(int i, int j)

return p;

2.7   &nb 18118t1915s sp; Exemple

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.

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

}

};

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)

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();

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++)

}

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)

/*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();

}

3.   &nb 18118t1915s sp;  Mersul lucrarii

3.1   &nb 18118t1915s sp;   &nb 18118t1915s sp; De la tastatura se citesc cuvinte ( siruri de caractere ). Sa se scrie un program care creeaza un arbore de cautare, care contine īn noduri cuvintele si frecventa lor de aparitie. Sa se afiseze apoi cuvintele īn ordine lexicografica crescatoare si frecventa lor de aparitie.

3.2   &nb 18118t1915s sp;   &nb 18118t1915s sp; Sa se implementeze operatia de interclasare a doi arbori de cautare.

3.3   &nb 18118t1915s sp;   &nb 18118t1915s sp; Sa se verifice daca operatia de stergere a unui nod dintr-un arbore de cautare este comutativa ( stergerea nodurilor x si y se poate face īn orice ordine).

3.4   &nb 18118t1915s sp;   &nb 18118t1915s sp; Se considera doua liste liniare simplu īnlantuite cu cāmpurile de informatie utila continānd numere īntregi. Sa se construiasca o lista care contine reuniunea celor doua liste si īn care elementele sunt ordonate crescator. Se va folosi o structura intermediara de tip arbore de cautare. Elementele comune vor apare a o singura data.

3.5   &nb 18118t1915s sp;   &nb 18118t1915s sp; Se considera un arbore de cautare care contine elemente cu informatia utila de tip sir de caractere. Sa se scrie o functie de cautare, inserare si stergere a sirului de caractere permitāndu-se folosirea sabloanelor, spre exemplu * pentru orice subsir sau ? pentru orice caracter.

3.6   &nb 18118t1915s sp;   &nb 18118t1915s sp; Informatiile pentru medicamentele unei farmacii sunt: nume medicament, pret, cantitate, data primirii, data expirarii.

Evidenta medicamentelor se tine cu un program care are drept structura de date un arbore de cautare dupa nume medicament. Sa se scrie programul care executa urmatoarele operatii:

-   &nb 18118t1915s sp;    creeaza arborele de cautare;

-   &nb 18118t1915s sp;    cauta un nod dupa cāmpul nume medicament si actualizeaza cāmpurile de informatie;

-   &nb 18118t1915s sp;    tipareste medicamentele īn ordine lexicografica;

-   &nb 18118t1915s sp;    elimina un nod identificat prin nume medicament;

-   &nb 18118t1915s sp;    creeaza un arbore de cautare cu medicamentele care au data de expirare mai veche decāt o data specificata de la terminal.

3.7   &nb 18118t1915s sp;   &nb 18118t1915s sp; Se va crea un arbore binar de cautare optimal care va avea īn noduri cuvintele cheie folosite īn limbajul C. Frecventele p_i si q_i se vor da īn functie de folosirea cuvintelor cheie īn programele exemplu din lucrare.