Arbori binari de cautare

ARBORI BINARI DE CAUTARE

Continutul lucrarii

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

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;

In 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.

Inserarea intr-un arbore binar de cautare.

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

a)         Daca arborele este vid, se creeaza un nou nod care este radacina, cheia avand valoarea key, iar subarborii stang si drept fiind vizi.

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

c)          Daca cheia key este mai mica decat cheia radacinii, se reia algoritmul pentru subarborele stang (pasul a).

d)         Daca cheia key este mai mare decat 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

}

Cautarea unui nod de cheie data key intr-un arbore binar de cautare.

Cautarea intr-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 in ceea ce priveste cautarea este atunci cand inserarea se face pentru nodurile avand cheile ordonate crescator sau descrescator. In acest caz, arborele degenereaza intr-o lista.

Algoritmul de cautare este redat prin functia urmatoare:

TIP_NOD *cautare (TIP_NOD *rad, int key)

/* functia returneaza adresa nodului in caz de gasire sau 0 in 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.

Stergerea unui nod de cheie data intr-un arbore binar de cautare

In 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. In acest caz, in nodul tata, adresa nodului

fiu de sters (stang sau drept) devine zero.

b)         Nodul de sters este un nod cu un singur descendent. In acest caz, in nodul tata,

adresa nodului fiu de sters se inlocuieste cu adresa descendentului nodului fiu de sters.

c)          Nodul de sters este un nod cu doi descendenti. In acest caz, nodul de sters se inlocuieste cu nodul cel mai din stanga al subarborelui drept sau cu nodul cel mai din dreapta al subarborelui stang.

Algoritmul de stergere a unui nod contine urmatoarele etape:

cautarea nodului de cheie key si a nodului tata corespunzator;

determinarea cazului in care se situeaza nodul de sters.

Stergerea unui arbore binar de cautare

Stergerea unui arbore binar de cautare consta in parcurgerea in postordine a arborelui si stergerea nod cu nod, conform functiei urmatoare:

void stergere_arbore(TIP_NOD *rad)

Traversarea unui arbore binar de cautare

Ca orice arbore binar, un arbore binar de cautare poate fi traversat in cele trei moduri: in preordine, in inordine si in 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);

Arbori binari de cautare optimali

Lungimea drumului de cautare a unui nod cu cheia x, intr-un arbore binar de cautare, este nivelul h_i al nodului in care se afla cheia cautata, in caz de succes sau 1 plus nivelul ultimului nod intalnit pe drumul cautarii fara succes.

Fie S = multimea cheilor ce conduc la cautarea cu succes (c₁ < c₂ < < c_n).

Analiza: Documente specifice operatiilor cu numerar Eseu: Forma de contabilitate utilizata la o societate comerciala

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 in 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 in 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, in loc de p_i si q_i se pot folosi frecventele aparitiei cautarilor respective in 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;

Exemple

Primul program prezinta toate functiile descrise in lucrare asupra unui arbore de cautare. Un nod contine drept informatie utila numai cheia, care este un numar intreg.

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 PREORDINEn');

preordine(rad,0);

getch();

printf('nVIZITAREA IN INORDINEn');

inordine(rad,0);

getch();

printf('VIZITAREA IN POSTORDINEn');

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 Gn');

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

getch();

printf('nMATRICEA Cn');

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

getch();

printf('nMATRICEA Rn');

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

getch();

printf('c[0][nr.]=%ld g[0][nr.]=%ldn',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=%6fn',drum_mediu);

getch();

radacina=constr_arbore(0,n);

inordine(radacina,0);

getch();

}

Mersul lucrarii

De la tastatura se citesc cuvinte ( siruri de caractere ). Sa se scrie un program care creeaza un arbore de cautare, care contine in noduri cuvintele si frecventa lor de aparitie. Sa se afiseze apoi cuvintele in ordine lexicografica crescatoare si frecventa lor de aparitie.

Sa se implementeze operatia de interclasare a doi arbori de cautare.

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 in orice ordine).

Se considera doua liste liniare simplu inlantuite cu campurile de informatie utila continand numere intregi. Sa se construiasca o lista care contine reuniunea celor doua liste si in care elementele sunt ordonate crescator. Se va folosi o structura intermediara de tip arbore de cautare. Elementele comune vor apare a o singura data.

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 permitandu-se folosirea sabloanelor, spre exemplu * pentru orice subsir sau ? pentru orice caracter.

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:

creeaza arborele de cautare;

cauta un nod dupa campul nume medicament si actualizeaza campurile de informatie;

tipareste medicamentele in ordine lexicografica;

elimina un nod identificat prin nume medicament;

creeaza un arbore de cautare cu medicamentele care au data de expirare mai veche decat o data specificata de la terminal.

Se va crea un arbore binar de cautare optimal care va avea in noduri cuvintele cheie folosite in limbajul C. Frecventele p_i si q_i se vor da in functie de folosirea cuvintelor cheie in programele exemplu din lucrare.