Documente online.
Username / Parola inexistente
  Zona de administrare documente. Fisierele tale  
Am uitat parola x Creaza cont nou
  Home Exploreaza






ARBORI BINARI DE CAUTARE

Informatica











ALTE DOCUMENTE

COMPARAREA ALTERNATIVELOR ĪN VEDEREA LUĂRII DECIZIEI OPTIME
Versiunea: 317+
Aplicatia ExaCost
WINDOWS XP PROFESSIONAL
bilete informatica
Evaluarea riscurilor sistemului informatic
Accesul la baze de date folosind JDBC
MOUSE - UL - tipuri de mous-uri
CONVENTIE DE LICENTA A UTILIZATORULUI FINAL DE SOFTWARE "ABC Alfabetul distractiv"(CLUF)
MICROPROCESOARELE


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

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

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.

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.


Greutatea arborelui Aij este:


care se poate calcula astfel:


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


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;

}

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 pi si qi se vor da īn functie de folosirea cuvintelor cheie īn programele exemplu din lucrare.


Document Info


Accesari: 2059
Apreciat:

Comenteaza documentul:

Nu esti inregistrat
Trebuie sa fii utilizator inregistrat pentru a putea comenta


Creaza cont nou

A fost util?

Daca documentul a fost util si crezi ca merita
sa adaugi un link catre el la tine in site

Copiaza codul
in pagina web a site-ului tau.

 


Copyright © Contact (SCRIGROUP Int. 2014 )