Exemplu de structura de arbore:

a e4q21ql
/ \ b c
/ \ / \ d e f g
/ \ \ h i j
Exemple de arbori:

poligoane
/ \ triunghi patrulatere
/ \ \ dreptunghi romb oarecare
Definitie
Se numeste arbore cuplul format din V si E : T= (V,E) cu V o multime de noduri si E VxV o multime de arce, cu proprietatile:

1) nodul r V (nodul radacina) astfel Œncƒt j V, (j, r) E
2) x V\ArS , y V unic , astfel Œncƒt (y, x) E (Cu alte cuvinte, pentru toate nodurile radacina, un singur arc ce intra Œn nodul respectiv)
3) y V, un drum A r = x0, x1, x2, ... ,xn= yS , cu xi V si (xi, xi+1)
E (Sau arborele trebuie sa fie un graf conex: nu exista noduri izolate sau grupuri de noduri izolate).

Proprietate a arborelui

Daca T, T= (V, E) este un arbore si r V este radacina arborelui, atunci multimea T\ArS = (V', E'), cu
V' = V -ArS si E' = E -A (r, x)/(r, x) E S poate fi partitionata astfel
Œncƒt sa avem mai multi arbori, a caror reuniune sa fie T\ArS, si oricare ar fi doi arbori intersectati, sa dea multimea vida:
T\ArS= T1 T2 ... Tk , Ti Tj = .

Definitii

1) Daca avem (x, y) E , x predecesorul lui y (tata), y succesorul lui x (fiu) x
/ y

2) Fie E(x) = A y, (x, y) E S multimea succesorilor lui x.

Definim gradul lui x: degree(x) = ˆ E(x) ˆ = numarul de succesori
Definim gradul arborelui : degree(T) = maxA degree(x)S, x V unde y se mai numeste nod terminal, sau frunza, daca degree(y) = 0, adica daca nu are descendenti.
Stramosii unui nod sunt asa-numitii ancestors(x) : ancestors(x) =
Ar = x0, x1, x2, ..., xkS cu proprietatea ca
(xi, xi+1) E , i= A0,k - 1S si (xk, x) E
Nivelul unui nod : level(x) = ˆ ancestors(x) ˆ + 1
Adƒncimea arborelui : depth(T) = max A level (x) pentru x V

Exemplu:
A
/ | \
B C D
/ \ | / | \
E F G H I J
/ \ |
K L M

predecesor(E) = B succesor(C) = G
E(D) = AH, I, JS degree(D) = 3 degree(B) = 2 degree(F) = 0 degree(T) = 3 ancestors(L) = AA, B, ES level(L) = 4 , level(B) = 2 , level(A) = 1 depth(T) = 4

Reprezentarea arborilor

Reprezentarea prin liste generalizate

Se considera ca nodurile terminale sunt elemente atomice, iar nodurile de grad
1 sunt subliste. Deci, fie arborele de mai sus scris sub forma :

A( B (E (K, L), F), C (G), D (H (M), I, J)) cu reprezentarea:

Reprezentarea prin structuri Œnlantuite

Aceasta reprezentare are calitatea ca, atunci cƒnd conteaza ordinea descendentilor, ea poate surprinde structura diferita.

De exemplu: structura x este diferita de structura x
/ | \ / | \ vid y vid y vid vid

Metodele de reprezentare expuse permit sa putem identifica legatura nod-descendent (succesor). Dar, exista aplicatii Œn care este nevoie de legatura nod-predecesor. Asadar, pare utila reprezentarea arborelui sub forma nodului (data, parent):

Avƒnd adresa unui nod, se gasesc toti predecesorii, obtinƒndu-se o lista
Œnlantuita:

(Reprezentarea TATA):

Arbori binari

Un arbore binar este un arbore de grad maxim 2. In cazul acestor arbori, se pot defini aplicatii, instrumente Œn plus de operare. Arborii binari pot avea deci gradele 2, 1, 0:
A A A
/ \ / / \
B C B B C
/ \ \ / / \ / \
D E F C D E F G

Observatie: Arborele A este diferit de A
/ \ / \
B vid vid B

Structura de baza a unui arbore binar:

rad
/ \
/ \
/ \
/ \
/ \ / \
/ SAS \ / SAD \
/______ \ /_______\
SAS subarborele stƒng (binar)
SAD subarborele drept (binar)

Definitii

1) Se numeste arbore binar strict arborele pentru care oricare ar fi un nod x V degree(x) = 2 , sau degree(x) = 0.

Exemplu: a
/ \ b c
/ \ / \ d e f g
/ \ h i

2) Se numeste arbore binar complet un arbore binar strict pentru care y cu: degree(y) = 0 (frunza) level(y) = depth(T)
Cu alte cuvinte, nodurile terminale apartin ultimului nivel din arbore.

Exemplu: a
/ \ b c
/ \ / \ d e f g
/ \ / \ / \ / \ h i j k l m n o

Relatii Œntre numarul de noduri si structura unui arbore binar

Lema 1

Numarul maxim de noduri de pe nivelul i al unui arbore binar este egal cu 2i-1.

Demonstratia se face prin inductie:
La nivelul 1 avem 20 = 1 nod = rad (radacina A). Presupunem conform metodei
P(n): pe nivelul n avem 2n-1 noduri. Demonstram pentru P(n+1): se observa ca toate nodurile de pe nivelul n+1 sunt noduri descendente de pe nivelul n.
Notƒnd niv(i) numarul de noduri de pe nivelul i, niv(n+1) 2úniv(n) 22n-1 = 2n .

Lema 2

Numarul maxim de noduri ale arborelui binar de adƒncime h este egal cu 2h -1.

Demonstratie:
Numarul total de noduri este egal cu:
(progresie geometrica)

Observatie: Numarul maxim de noduri pentru arborele binar se atinge Œn situatia unui arbore binar complet.
2h -1 = numarul de noduri Œn arborele binar complet de adƒncime h

Lema 3

Notam cu: n2 numarul de noduri de grad 2 din arborele binar; n1 numarul de noduri de grad 1 din arborele binar; n0 numarul de noduri terminale (frunze) din arborele binar;
In orice arbore binar, n0 = n2 +1 (nu depinde de n1).

Demonstratie: fie n = n0 + n1 + n2 (numarul total de noduri); conform definitiei, fiecare nod are un singur predecesor numarul de muchii ˆ E ˆ = n - 1. Acelasi numar de muchii ˆ E ˆ = 2 n2 + n1.
Deci, n - 1 = 2n2 + n1 , Œnlocuind, n0 + n1 +n2 -1 = 2n2 + n1 n0 = n2 + 1 ceea ce trebuia de demonstrat.
Rezulta ca Œntr-o expresie numarul de operatori binari si unari este egal cu numarul de operanzi + 1.

Lemele se folosesc pentru calcule de complexitate.

Operatii asupra arborilor binari

Operatii curente: selectia cƒmpului de date dintr-un nod si selectia descendentilor; inserarea unui nod; stergera unui nod.

Traversarea arborilor binari (A.B.)
Traversarea consta Œn "vizitarea" tuturor nodurilor unui arbore Œntr-un scop anume, de exemplu, listare, testarea unei conditii pentru fiecare nod, sau alta prelucrare. O traversare realizeaza o ordonare a nodurilor arborelui
(un nod se prelucreaza o singura data).
Strategii de traversare: traversare Œn preordine: prelucrare Œn ordinea: rad, SAS, SAD; traversare Œn inordine: prelucrare Œn ordinea: SAS, rad, SAD; traversare Œn postordine: prelucrare Œn ordinea: SAS, SAD, rad.

rad
/ \
SAS SAD

Exemplu de traversare: a
/ \ b c
/ \ \ d e f
/ \ g h

preordine : A B D F G H C F inordine : D B G E H A C F postordine : D G H E B F C A

Functii de parcurgere (in pseudocod)
Facem notatiile: p pointer la un nod lchild(p) pointer la succesorul stƒng (p stg) rchild(p) pointer la succesorul drept (p drt) data(p) informatia memorata Œn nodul respectiv (p data)

In C++ avem:

struct NodA
Atom data;
Nod* stg;
Nod* dr;
S;
Nod* p;

Procedurile de parcurgere sunt:

preorder(t)
A if(t==0) return else |½ print (data(t)) // vizitarea uni nod
| preorder (lchild(t)) // parcurgerea | // subarborilor
|_ preorder (rchild(t))
S

inorder(t)
A if(t!=0) |½ inorder (lchild(t))
| print (data(t))
|_ inorder (rchild(t))
S

postorder(t)
A if(t!=0) |½ postorder (lchild(t))
| postorder (rchild(t))
|_ print(data(t))
S

Binarizarea arborilor oarecare

Lema 1

Daca T este un arbore de grad k cu noduri de dimensiuni egale (k pointeri Œn fiecare nod), arborele avƒnd n noduri reprezentarea va contine n (k - 1) + 1 pointeri cu valoare zero (nuli).

Demonstratie: Numarul total de pointeri utilizati Œn reprezentare este nk

Numarul total de pointeri nenuli este egal cu numarul de arce nk - (n - 1) = n(k - 1) + 1

nr.poineri nuli n(k-1)+1 n-1
------------------- = --------- = 1 - ------- nr.total de pionteri nk nk

raportul este maxim pentru k = 2.
Rezulta ca cea mai eficienta reprezentare (Œn structura Œnlantuita) este reprezentarea Œn arbori binari.
Arborele binar de cautare (BST)
Arborele binar de cautare reprezinta o solutie eficienta de implementare a structurii de date numite "dictionar". Vom considera o multime "atomi".
Pentru fiecare element din aceasta multime avem: a atomi, este definita o functie numita cheie de cautare: key(a)a partine lui k cu proprietatea ca doi atomi distincti au chei diferite de cautare: a1!=a2=> key(a1)!=key(a2).

Exemplu: (abreviere, definitie) ("BST","Binary Search Tree")
("LIFO","Last In First Out") key(a) = a.abreviere

Un dictionar este o colectie S de atomi pentru care se definesc operatiile: insert(S,a) insereaza atomul a Œn S daca nu exista deja; delete(S,k) sterge atomul cu cheia k din S daca exista; search(S,k) cauta atomul cu cheia k Œn S si-l returneaza sau determina daca nu este.

O solutie imediata ar fi retinerea elementelor din S Œntr-o lista Œnlantuita, iar operatiile vor avea complexitatea O(n).

Tabelele Hashing
Acestea sunt o alta solutie pentru a retine elementele din S. Complexitatea pentru arborele binar de cautare Œn cazurile: cel mai defavorabil: O(n); mediu: O(log n).
Un arbore binar de cautare este un arbore T ale carui noduri sunt etichetate cu atomii continuti la un moment dat Œn dictionar.
T = (V, E) , ˆVˆ = n. (n atomi Œn dictionar)

Considerƒnd r V (radacina arborelui), Ts subarborele stƒng al radacinii si
Td subarborele drept al radacinii, atunci structura acestui arbore este definita de urmatoarele proprietati:
1) un nod x Ts atunci key(data(x)) < key(data(r));
2) x Td atunci key(data(x)) > key(data(r));
3) Ts si Td sunt BST.

Observatii:
1) Consideram ca pe multimea k este definita o relatie de ordine (de exemplu lexico-grafica);
2) Pentru oricare nod din BST toate nodurile din subarborele stƒng sunt mai mici decƒt radacina si toate nodurile din subarborele drept sunt mai mari decƒt radacina.

Exemple: 15 15
/ \ / \
7 25 10 25
/ \ / \ / \ /
2 13 17 40 2 17 13
/ / \
9 27 99 este BST nu este BST.

3) Inordine: viziteaza nodurile Œn ordine crescatoare a cheilor:
2 7 9 13 15 17 25 27 40 99
Functii:
1)Search: search(rad,k) // rad pointer la radacina arborelui
A // k cheia de cautare a arborelui cautat if (rad = 0) then return NULL else if key (data (rad)) > k then return search (lchild (rad)) else if key (data (rad)) < k then return search (rchild (rad)) else return rad
S
2)Insert:
Se va crea un nod Œn arbore care va fi plasat la un nou nod terminal.
Pozitia Œn care trebuie plasat acesta este unic determinata Œn functie de valoarea cheii de cautare.
Exemplu: vom insera 19 Œn arborele nostru:

15
/ \
7 25
/ \ / \
2 13 17 40
/ \ / \
9 19 27 99

insert(rad,a) // rad referinta la pointerul la radacina // arborelui
A if (rad= 0) then rad= make_nod(a) else if key (data (rad)) > key(a) then insert(lchild(rad),a) else if key (data(rad)) < key(a)then insert (rchild (rad),a)
S
Functia make_nod creaza un nou nod:

make_nod(a)
A p= get_sp() // alocare de memorie pentru un nod nou data(p)= a lchild(p)= 0 rchild(p)= 0 return(p)
S

Observatie:
1)La inserarea unui atom deja existent Œn arbore, functia insert nu modifica structura arborelui. Exista probleme Œn care este utila contorizarea numarului de inserari a unui atom Œn arbore.
2)Functia insert poate returna pointer la radacina facƒnd apeluri de forma p= insert(p,a).
3)Delete:

delete(rad,k) // rad referinta la pointer la radacina
A // k cheia de cautare a atomului care trebuie sters de noi if rad = 0 then return // nodul cu cheia k nu se afla // Œn arbore else if key(data(rad)) > k then delete(lchild(rad),k) else if key(data(rad)) < k then delete(rchild(rad),k) else delete_root(rad)
S
Stergerea radacinii unui BST.:
1) rad=>arbore vid
2)a) rad sau b) rad => a) SAS sau b) SAD
/ \
SAS SAD

delete_root(rad) // rad referinta la pointer la radacina
A if lchild(rad)=0 then
| p= rchild(rad)
| ret_sp(rad)
|_ rad= p else if rchild(rad)= 0 then
| p= lchild(rad)
| ret_sp(rad)
|_ rad= p else | p= remove_greatest(lchild(rad))
| lchild(p)= lchild(rad)
| rchild(p)= rchild(rad)
| ret_sp(rad)
|_ rad= p
S
15
/ \
7 25
/ \ / \
2 13 17 40
/ /
9 27
/ \
26 33

Detasarea din structura arborelui BST a celui mai mare nod (remove_greatest):
Pentru a gasi cel mai mare nod dintr-un arbore binar de cautare, se Œnainteaza
Œn adƒncime pe ramura dreapta pƒna se gaseste primul nod care nu are descendent dreapta. Acesta va fi cel mai mare.
Vom trata aceasta procedura recursiv:
Caz1: rad=>se returneaza pointer la radacina si arborele rezultat va fi vid.
Caz2: rad=> se returneaza pointer la radacina si arborele rezultat va fi format doar din SAS subarborele stƒng (SAS).
Caz3: rad=>functia returneaza pointer la cel mai mare nod din SAD, iar rezultatul va fi SAS arborele care este fomat din radacina,SAS si SAD cel mai mare nod.

remove_greatest(rad) //rad -referinta la pointer la //radacina: un pointer la radacina de poate //fi modificat de catre functie
A if rchild (rad)= 0 then | p= rad
| rad= lchild (rad)
|_ return(p) else return (remove_greatest (rchild(rad)))
S

Observatie:

Functia remove_greatest modifica arborele indicat de parametru, Œn sensul eliminarii nodului cel mai mare, si Œntoarce pointer la nodul eliminat.

Demonstratia eficientei (complexitate)

Complexitatea tuturor functiilor scrise depinde de adƒncimea arborelui.
In cazul cel mai defavorabil, fiecare functie parcurge lantul cel mai lung din arbore. Functia de cautare are, Œn acest caz, complexitatea O(n).
Structura arborelui BST este determinata de ordinea inserarii.
De exemplu, ordinea 15 13 12 11 este alta decƒt 15 12 11 13 .
Studiem un caz de complexitate medie:

Crearea unui BST pornind de la secventa de atomi (a1 a2 ... an)

gen_BST (va fi Œn programul principal)
| rad= 0
| for i= 1 to n
| insert (rad, ai)

Calculam complexitatea medie a generarii BST:
Complexitatea Œn cazul cel mai defavorabil este:
Notam cu T(k) numarul de comparatii mediu pentru crearea unui BST pornind de la o secventa de k elemente la intrare. Ordinea celor k elemente se considera aleatoare.
Pentru problema T(n) avem de creat secventa (a1 a2 ... an) cu observatia ca a1 este radacina arborelui. Ca rezultat, Œn urma primei operatii de inserare pe care o facem, rezulta:

a1
/ \ a1 ai
(ai<a1) (ai>a1)

Nu vom considera numararea operatiilor Œn ordinea Œn care apar ele, ci consideram numarul de operatii globale. Dupa ce am inserat a1, pentru inserarea fiecarui element Œn SAS sau SAD a lui a1, se face o comparatie cu a1.
Deci:
T(n)= (n - 1) + val.med.SAS + val.med.SAD val.med.SAS = valoarea medie a numarului de comparatii necesar pentru a construi subarborele stƒng SAS val.med.SAD = valoarea medie a numarului de comparatii necesar pentru a construi subarborele drept SAD

Notam:
Ti(n) = numarul mediu de comparatii necesar pentru construirea unui BST cu n noduri atunci cƒnd prima valoare inserata (a1) este mai mare decƒt i-1 dintre cele n valori de inserat. Putem scrie:

Deci:

Deci:

Complexitatea acestei functii este: O(nln n) (vezi curs 5 complexitatea medie a algoritmului Quick-Sort)
Arbori binari de cautare dinamic echilibrati (AVL)
Definitie
Un arbore binar este echilibrat daca si numai daca, pentru fiecare nod din arbore, diferenta dintre adƒncimile SAS si SAD Œn modul este 1.

Exemple: a a
/ \ / \ b c b c
/ \ / \ / \ \ d e f g d e f
/ \ g h arbore binar arbore binar complet echilibrat echilibrat

Adƒncimea unui arbore echilibrat cu n noduri este O(ln n).
Se completeaza operatiile insert si delete cu niste prelucrari care sa pastreze proprietatile de arbore binar echilibrat pentru arborele binar de cautare.
Arborele binar echilibrat este un BST echilibrat, proprietatea de echilibrare fiind conservata de insert si delete. Efortul, Œn plus, pentru completarea operatiilor insert si delete nu schimba complexitatea arborelui binar echilibrat.
Transformarea structurii arborelui dupa inserare pentru a conserva proprietatea de arbore binar echilibrat
Modificarile care se vor face se vor numi rotatii.

Caz 1: Fie arborele echilibrat
A
/ \
B T3 h = depth(T1) = depth(T2) = depth(T3)
/ \
T1 T2

Consideram arborii T1, T2, T3 echilibrati. Inserƒnd un nod prin rotatie simpla, rezulta structurile rotit simplu la dreapta si rotit simplu la stƒnga imaginea oglinda a rotatiei dreapta:
A A
/ \ / \
B T3 T3 B
/ \ / \
T1 T2 T2 T1

Caz 2: Inserarea se face prin rotatii duble:
A A
/ \ / \
B T3 T3 B
/ \ / \
T1 T2 T2 T1 rotatie dubla rotatie dubla la dreapta la stƒnga
Fie primul caz:
A
/ \
B T3
/ \
T1 T2 este BST: T1 < B < T2 < A < T3

Toti arborii care respecta Œn continuare aceasta conditie vor fi BST.
Ridicƒnd pe B Œn sus, si notƒnd cu // legaturile neschimbate, rezulta:
B
// \
// A
T1 / \\
____________T2___T3_________ pe aceeasi linie

care este un BST , deci este arbore echilibrat, si are aceeasi adƒncime (!!!) cu arborele initial (de dinainte de inserare). Nodurile superioare nu sunt afectate. Rationament analog pentru imaginea oglinda.

Fie cazul 2: Pentru rotatia dubla se detaliaza structura arborelui T2.
Nu se poate sparge arborele initial ca Œn cazul 1.
A
/ \\
B \\
// \ T3
// C
// / \
T1 T2S T2D depth(T1) = depth(T3) = h depth(T2S) = depth(T2D) = h - 1

In urma inserarii, unul dintre arborii T2S si T2D Œsi mareste adƒncimea.
Aplicam aceiasi tehnica:
T1 < B < T2S < C < T2D < A < T3

Incepem cu C:
C
/ \
B A
// \ / \\
// T2S T2D \\
______T1___________________ T3_____________________ la acelasi nivel
Rezulta un BST echilibrat, de aceeaai adƒncime cu arborele initial. Rotatiile sunt duble, Œn sensul ca s-a facut o rotatie simpla B la stƒnga cu o rotatie simpla A la dreapta.
Operatiile care trebuiesc facute Œn cazul 1 (rotatie simpla la dreapta): r- pointer la nodul radacina (A) a- pointer la radacina p = lchild(r) b = lchild(a) lchild(r) = rchild(p) lchild(a) = rchild(b) rchild(p) = r rchild(b) = a r = p a = b
Operatiile care trebuiesc facute Œn cazul 2 (rotatie dubla) b = lchild(a) c = rchild(b) lchild(a) = rchild(c) rchild(b) = lchild(c) rchild(c) = a lchild(c) = b a = c // se schimba radacina arborelui.
Asadar, Œn inserarea prin rotatie se obtine un arbore echilibrat cu adƒncimea egala cu adƒncimea arborelui de dinainte de inserare. La inserarea unui nod terminal Œntr-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ƒncimea subarborelui stƒng si adƒncimea subarborelui drept.
Calculam factorii de balansare dupa inserare.
Observatie: Pentru nodul terminal s-a schimbat adƒncimea 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 Œntƒlnit la o parcurgere de jos
Œn 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 Œn arbore).

2.Factorul de balansare devine bf = 2 sau bf = -2 atunci cƒnd nodul inserat mareste dezechilibrul arborelui (s-a inserat nodul Œn subarborele cel mai mare)
In acest caz, se aplica o rotatie Œn urma careia se schimba strucutra subarborelui, astfel Œncƒt noua radacina capata bf = 0, conservƒndu-se adƒncimea.
Concluzie: Problema conservarii proprietatii de echilibrare a arborelui se rezolva aplicƒnd o rotatie asupra nodului critic numai atunci cƒnd inserarea dezechilibreaza acest nod.
Costul suplimentar care trebuie suportat se materializeaza prin necesitatea ca Œn fiecare nod sa se memoreze factorul de dezechilibrare bf. Acesti factori de dezechilibrare vor fi actualizati Œn urma operatiilor de rotatie si inserare
Operatia de stergere Œntr-un AVL implica mai multe rotatii, ea nu se studiaza
Œn 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 Œntƒi cu 55 : e Œn stƒnga lui, s.a.m.d. pƒna cƒnd gasim locul ei Œn pozitia de mai jos. Pentru a doua valoare de inserat, 7, nodul critic este 55. El este dezechilibrat stƒnga. 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 Œn cursul anterior. Se asociaza nodurile:
55->A
20->B etc. =>

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

In urma unei rotatii simple, factorii de dezechilibru implicati Œn 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 Œn subarborele T2S,
B are bf = 0 |
A are bf = -1 | exceptie facƒnd nodul C nodul de inserat
La rotatia dubla, daca nodul 9 a fost inserat Œn subarborele T2D,
B are bf = 1 |
A are bf = 0 | exceptie facƒnd 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ƒnga la dreapta, nodurile nivelului 2 de la stƒnga la dreapta, etc, despartite de linii duble.

Lema
Daca Œn vectorul V un nod x este reprezentat prin elementul de vector V(i), atunci:
1. left_child(x) este reprezentat Œn elementul de vector V a2úii;
2. right_child(x) este reprezentat Œn elementul de vector V a2úi + 1i;
3. parent(x) este reprezentat Œn elementul de vector V aai/2ii cu observatia ca paranteza patrata interioara este partea Œntrega.
Demonstratie:
Se face inductie dupa i:
Pentru i = 1 => Va1i radacina
=> Va2i left_child(rad)
=> Va3i right_child(rad)
Presupunem adevarata lema pentru elementul Vaii=>Va2ii left_child
Va2i + 1i right_child
Elementul Vai + 1i este nodul urmator (de pe acelsi nivel sau de pe nivelul urmator) Œntr-o parcurgere binara.
Vai + 1i => left_child Œn Va2i + 2i = Va2(i + 1)i right_child Œn Va2i + 3i = Va2(i + 1) + 1i
Daca avem un arbore binar care nu este complet, reprezentarea lui implicita se obtine completƒndu-se structura arborelui cu noduri fictive pƒna 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ƒt cheile descendentilor).

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

Observatie: De obicei functia cheie reprezinta selectia unui subcƒmp din cƒmpul de date memorate Œn nod.
Aplicatii ale arborilor heap
Coada cu prioritate;
Algoritmul Heap_Sort

Arborii heap nu se studiaza complet Œn acest curs.