Probleme de informatică
  Clasa a IX-a
1. Elementele de bază ale limbajului C++ (instructiunile limbajului) (46)
2. Subprograme predefinite (1)
3. Tablouri (145)
4. Fişiere text (2)
5. Algoritmi elementari (106)
6. Probleme diverse (13)
  Clasa a X-a
1. Subprograme definite de utilizator (87)
2. Şiruri de caractere (47)
3. Înregistrări (26)
4. Recursivitate (57)
5. Combinatorica (0)
6. Alocarea dinamică a memoriei (2)
7. Liste înlănţuite (25)
8. Algoritmul lui Lee (1)
  Clasa a XI-a

1. Metoda "Divide et impera" (12)
2. Metoda Backtracking (85)
3. Metoda Greedy (6)
4. Programare dinamică (18)
5. Grafuri neorientate (37)
6. Grafuri orientate (38)
7. Arbori (33)

  Clasa a XII-a
1. Elemente de baza C# (32)
2. POO in C# (13)
3. C# - Windows Form Application (24)
4. Admitere UBB (18)

   Home Bacalaureat 2016   |   Variante bacalaureat 2009   |   Atestat  |   Olimpiada       
Noutăţi
Subiecte admitere la Facultatea de informatica UBB Cluj-Napoca
Subiecte bacalaureat 2010-2018
Bacalaureat 2018 - competenţe digitale
C# - Windows Form Application - exemple
Modele de proiecte de atestat
Bacalaureat 2018
Subiecte si rezolvări 2010-2018
Rezolvari variante bacalaureat 2009
Competenţe digitale
Examen atestat
Rezumat documentatie
php.doc
css.doc
exemple_php_si_css.rar
Modele de proiecte de atestat
Olimpiada
Clasele V-VI
Clasele VII-VIII
Clasa a IX-a
Clasa a X-a
Clasele XI-XII
Noţiuni teoretice
Metode de sortare
Metoda backtracking


Metode de sortare  

Sortarea folosind arbore binar de căutare (sau arbore binar ordonat)
Aşa cum sugerează numele sau, un arbore binar de căutare este organizat sub forma de arbore binar, aşa cum se observa în figura 1.12. Un astfel de arbore se poate reprezenta printr-o structura de date înlănţuită, în care fiecare nod este un obiect. Pe lângă un câmp cheie şi date adiţionale, fiecare obiect nod conţine câmpurile stânga, dreapta şi p care punctează spre (refera) nodurile corespunzătoare fiului stâng, fiului drept şi respectiv părintelui nodului. Daca un fiu sau un părinte lipseşte, câmpul corespunzător acestuia va conţine valoarea nil. Nodul rădăcină este singurul nod din arbore care are valoarea nil pentru câmpul părinte p.
Într-un arbore binar de căutare, cheile sunt întotdeauna astfel memorate încât ele satisfac proprietatea arborelui binar de căutare:
Fie x un nod dintr-un arbore binar de căutare. Daca y este un nod din subarborele stâng al lui x, atunci cheie[y] ≤ cheie[x]. Daca y este un nod din subarborele drept al lui x, atunci cheie[x] ≤ cheie[y].
Astfel, în figura 1.13(a) cheia rădăcinii este 5, iar cheile 2, 3 şi 5 din subarborele stâng nu sunt mai mari decât 5, pe când cheile 7 şi 8 din subarborele drept nu sunt mai mici decât 5. Aceeaşi proprietate se verifica pentru fiecare nod din arbore. De exemplu, cheia 3 din figura 1.13(a) nu este mai mica decât cheia 2 din subarborele sau stâng şi nu este mai mare decât cheia 5 din subarborele sau drept.

Figura 1.13 Arbori binari de căutare. Pentru orice nod x, cheile din subarborele stâng al lui x au valoarea mai mica sau egala cu cheie[x], iar cheile din subarborele drept al lui x au valoarea mai mare sau egala cu cheie[x]. Aceeaşi mulţime de valori se poate reprezenta prin arbori binari de căutare, diferiţi. Timpul de execuţie, în cazul cel mai defavorabil, pentru majoritatea operaţiilor arborilor de căutare este proporţional cu înălţimea arborelui. (a) Un arbore binar de căutare cu 6 noduri şi de înălţime 2. (b) Un arbore binar de căutare mai puţin eficient care conţine aceleaşi chei şi are înălţimea 4.

Proprietatea arborelui binar de căutare ne permite să tipărim toate cheile în ordine crescătoare cu ajutorul unui algoritm recursiv simplu, numit traversarea arborelui în inordine.
Numele acestui algoritm deriva din faptul că cheia rădăcinii unui subarbore se tipăreşte între valorile din subarborele sau stâng şi cele din subarborele sau drept. (Similar, o traversare a arborelui în preordine va tipări cheia rădăcinii înaintea cheilor din subarbori, iar o traversare a arborelui în postordine va tipări cheia rădăcinii dupa cheile din subarbori). Pentru a folosi procedura următoare în scopul tipăririi tuturor elementelor din arborele binar de căutare T o vom apela cu Arbore-Traversare-Inordine(radacina[T]).


Subalgoritm Arbore-Traversare-Inordine(x)
1: daca x ¹ nil atunci
2:       Arbore-Traversare-Inordine(stânga[x])
3:       afiseaza cheie[x]
4:       Arbore-Traversare-Inordine(dreapta[x])

Spre exemplu, traversarea în inordine a arborelui afişează cheile fiecăruia dintre arborii binari de căutare din figura 1.13 în ordinea 2, 3, 5, 5, 7, 8. Corectitudinea algoritmului se demonstrează prin inducţie folosind direct proprietatea arborelui binar de căutare. Deoarece dupa apelul iniţial procedura se apelează recursiv de exact doua ori pentru fiecare nod din arbore – o data pentru fiul sau stâng şi încă o data pentru fiul sau drept – rezulta că este nevoie de un timp Θ(n) pentru a traversa un arbore binar de căutare cu n noduri.
Crearea arborelui de căutare se realizează prin inserarea de chei noi. Vom folosi procedura Arbore-Insereaza pentru a insera o noua valoare v într-un arbore binar de căutare T. Procedurii i se transmite un nod z pentru care cheie[z] = v, stânga[z] = nil şi dreapta[z] = nil. Ea va modifica arborele T şi unele dintre câmpurile lui z astfel încât z va fi inserat pe poziţia corespunzătoare în arbore.


Subalgoritm Arbore-Insereaza(T, z)
1: y ← nil
2: x ← radacina[T]
3: cât timp x ¹ nil executa
4:         y ← x
5:        daca cheie[z] < cheie[x] atunci
6:               x ← stânga[x]
7:        altfel
8:               x ←  dreapta[x]
9: p[z] ← y
10: daca y = nil atunci
11:          radacina[T] ← z
12: altfel daca cheie[z] < cheie[y] atunci
13:                  stânga[y] ← z
14:          altfel
15:                 dreapta[y] ← z

Algoritmul poate fi uşor implementat şi recursiv.
În cazul cel mai favorabil arborele construi astfel va avea toate frunzele pe 2 nivele consecutive, iar în cel mai defavorabil fiecare nod va fi pe un nivel, ca în figura de mai jos.
 
Figura 1.14 Cazul cel mai favorabil (a) şi cel mai defavorabil (b)

Crearea şi utilizarea unui arbore binar de căutare se poate face şi doar cu cele două legături stânga şi dreapta, fără legătura spre nodul părinte.




  Clasa a IX-a
1. Elementele de bază ale limbajului C++ (instructiunile limbajului) (46)
2. Subprograme predefinite (1)
3. Tablouri (145)
4. Fişiere text (2)
5. Algoritmi elementari (106)
6. Probleme diverse (13)
  Clasa a X-a
1. Subprograme definite de utilizator (87)
2. Şiruri de caractere (47)
3. Înregistrări (26)
4. Recursivitate (57)
5. Combinatorica (0)
6. Alocarea dinamică a memoriei (2)
7. Liste înlănţuite (25)
8. Algoritmul lui Lee (1)
  Clasa a XI-a

1. Metoda "Divide et impera" (12)
2. Metoda Backtracking (85)
3. Metoda Greedy (6)
4. Programare dinamică (18)
5. Grafuri neorientate (37)
6. Grafuri orientate (38)
7. Arbori (33)

  Clasa a XII-a
1. Elemente de baza C# (32)
2. POO in C# (13)
3. C# - Windows Form Application (24)
4. Admitere UBB (18)

Calculatoare si accesorii second hand
Copyright 2009-2017 Muresan Vasile Ciprian - mcip.ro