curs09.txt

STRUCTURI DE DATE SI ALGORITMI

				       Curs 9


Asadar, 宯 inserarea prin rotatie se obtine un arbore echilibrat cu ad僴cimea
egala cu ad僴cimea arborelui de dinainte de inserare. La inserarea unui nod
terminal 宯tr-un arbore AVL este necesara aplicarea a cel mult o rotatie asupra
unui nod. Trebuie, deci sa gasim nodul asupra caruia trebuie aplicata rotatia.
Reprezentam ramura parcursa de la radacina la nodul inserat:

                   x             bf = 1
                 /
               y                 bf = 0
                 \
                   z             bf = - 1 (bf = -2 dupa inserare)
                     \
                       w         bf = 0 (bf = 1 dupa inserare)
                     /
                   v             bf = 0 (bf = -1 dupa inserare)
                     \
		       nodul
                      inserat

S-a notat pentru fiecare nod bf  balance factor (factor de dezechilibrare):
bf(nod) = depth (lchild (nod))  depth (rchild (nod))
adica este diferenta dintre ad僴cimea subarborelui st僴g si ad僴cimea
subarborelui drept.
Calculam factorii de balansare dupa inserare.
Observatie: Pentru nodul terminal s-a schimbat ad僴cimea si factorul de
balansare; bf = -2 dupa inserare devine nod dezechilibrat. Trebuie aplicata,
deci, echilibrarea.

Definitie:
Se numeste nod critic primul nod cu bf  0 宯t僱nit la o parcurgere de jos
宯 sus a ramurii care leaga nodul inserat de radacina.

Observatie: Toate nodurile din ramura care sunt pe nivele inferioare nodului
critic vor capata bf = 1 sau 
bf = -1.

La nodul critic exista doua situatii:

1.Nodul critic va fi perfect balansat (bf = 0), daca dezechilibrul creat de
nodul inserat anuleaza dezechilibrul initial al nodului.In acest caz nu este
nevoie de rotatie (el completeaza un gol 宯 arbore).

2.Factorul de balansare devine bf = 2 sau bf = -2 atunci c僴d nodul inserat
mareste dezechilibrul arborelui (s-a inserat nodul 宯 subarborele cel mai mare)
In acest caz, se aplica o rotatie 宯 urma careia se schimba strucutra
subarborelui, astfel 宯c僼 noua radacina capata bf = 0, conserv僴du-se
ad僴cimea.
Concluzie: Problema conservarii proprietatii de echilibrare a arborelui se
rezolva aplic僴d o rotatie asupra nodului critic numai atunci c僴d inserarea
dezechilibreaza acest nod.
Costul suplimentar care trebuie suportat se materializeaza prin necesitatea
ca 宯 fiecare nod sa se memoreze factorul de dezechilibrare bf. Acesti factori
de dezechilibrare vor fi actualizati 宯 urma operatiilor de rotatie si inserare
 Operatia de stergere 宯tr-un AVL implica mai multe rotatii, ea nu se studiaza
宯 acest curs.

Exemplu: Se da arborele cu urmatoarea structura:
                       55
                    /     \
                  20       80
                /    \       \ 
              10     35       90
             /       /
            5      30

Sa se insereze nodurile 15, apoi 7 si sa se echilibreze arborele.
Inseram prima valoare 15. Comparam mai 宯t僫 cu 55 : e 宯 st僴ga lui,
s.a.m.d. p僴a c僴d gasim locul ei 宯 pozitia de mai jos. Pentru a doua valoare
de inserat, 7, nodul critic este 55. El este dezechilibrat st僴ga. Deci, va fi
echilibrat la valoarea 2. Este necesara aplicarea unei rotatii asupra radacinii

                        55
                     /      \
                   20        80
                /     \         \
              10       35       90
	     /   \     /
            5    15  30
             \
              7

Facem o identificare cu unul din desenele de echilibrare prezentate 宯 cursul
anterior. Se asociaza nodurile:	
          55->A
          20->B etc.   =>

                     20  ----------> noduri implicate 
                  /      \                   宯
                10        55  ------> rotatie
              /    \     /   \
             5     15  35    80
              \       /         \
               7    30          90

In urma unei rotatii simple, factorii de dezechilibru implicati 宯 rotatie
devin zero.
Fie o a treia valoare de inserat 3, apoi a patra 9:
Nodul critic pentru 3 este 5, iar pentru 9 este este 10. Dupa rotatia aplicata
(T2D, T2S  vizi), rezulta arborele:
                             20
                        /          \
                      7             55
                    /    \         /   \
                   5     10       35   80
                 /      /  \     /        \
                3     9    15   30        90

La rotatia dubla, daca nodul 9 a fost inserat 宯 subarborele T2S,
      B are bf = 0      |
      A are bf = -1     |       exceptie fac僴d nodul C  nodul de inserat
La rotatia dubla, daca nodul 9 a fost inserat 宯 subarborele T2D,
      B are bf = 1      |
      A are bf = 0      |       exceptie fac僴d nodul C  nodul de inserat

Reprezentarea implicita a arborilor binari
In acest mod de reprezentare se reprezinta arborele printr-un tablou. Fie un
arbore binar complet:
                      a
                 /          \
             b                c
          /     \           /    \
        d         e        f       g
      /   \     /   \    /   \   /   \
     h     i  j      k  l     m  n    o

care are 4 nivele, deci 24 - 1 = 15 noduri.
Asociem acestui arbore un vector V:

structurat astfel: radacina, nivelul 1 de la st僴ga la dreapta, nodurile
nivelului 2 de la st僴ga la dreapta, etc, despartite de linii duble.

Lema
Daca 宯 vectorul V un nod x este reprezentat prin elementul de vector V(i), atunci:
1. left_child(x) este reprezentat 宯 elementul de vector V [2鷌];
2. right_child(x) este reprezentat 宯 elementul de vector V [2鷌 + 1];
3. parent(x) este reprezentat 宯 elementul de vector V [[i/2]]
cu observatia ca paranteza patrata interioara este partea 宯trega.
Demonstratie: 
Se face inductie dupa i:
Pentru i = 1  => V[1]  radacina
              => V[2]  left_child(rad)
              => V[3]  right_child(rad)
Presupunem adevarata lema pentru elementul V[i]=>V[2i]  left_child
						V[2i + 1]  right_child
Elementul V[i + 1] este nodul urmator (de pe acelsi nivel sau de pe nivelul urmator) 宯tr-o parcurgere binara.
	V[i + 1] => left_child 宯 V[2i + 2] = V[2(i + 1)]
			right_child 宯 V[2i + 3] = V[2(i + 1) + 1]
Daca avem un arbore binar care nu este complet, reprezentarea lui implicita se
obtine complet僴du-se structura arborelui cu noduri fictive p僴a la obtinerea
unui arbore binar complet.

Arbori heap (heap  gramada)

Definitie:
Se numeste arbore heap  un arbore binar T = (V, E) cu urmatoarele proprietati:
1) functia key : V  R care asociaza fiecarui nod o cheie.
2) un nod v  V cu degree(v) > 0 (nu este nod terminal), atunci:
  key(v) > key(left_child(v)), daca  left_child(v)
  key(v) > key(right_child(v)), daca  right_child(v)
(Pentru fiecare nod din arbore, cheia nodului este mai mare dec僼 cheile
descendentilor).

Exemplu:                    99
                          /    \
                        50      30
                      /   \    /   \
                     45    20 25   23

Observatie: De obicei functia cheie reprezinta selectia unui subc僲p din c僲pul
de date memorate 宯 nod.
Aplicatii ale arborilor heap
 Coada cu prioritate;
 Algoritmul Heap_Sort

Arborii heap nu se studiaza complet 宯 acest curs.