ARBORI BALANSATI (B-Trees)

ARBORI BALANSAŢI (B-Trees) .

În acest capitol :

Vom afla ce sunt arborii balansati

Vom calcula înaltimea arborilor balansati

Vom descrie operatiile cu arbori balansati

Arborii balansati sunt arbori de cautare destinati sa lucreze eficient pe discuri magnetice; ei sunt realizati urmarind aceleasi idei si scopuri ca si arborii rosu-negrii dar sunt superiori acestora în minimizarea timpului pentru intrare-iesire .

Diferenta esentiala este ca, în arborii balansati, un nod poate avea mai multi descendenti (pâna la sute). Asemanarea este ca înaltimea arborelui este O(log n) desi baza logaritmului (mult mai mare) da o înaltime corespunzator mai mica. Aceasta este important pentru ca operatiile asupra arborelui, cum ar fi cautarea, inserarea si stergerea au complexitati proportionale cu înaltimea arborelui.

Se vede din figura 10.1 cum arborii balansati generalizeaza arborii binari de cautare.

Fig.10.

Cheile sunt consoane. Un nod contine n(x) chei si are n(x) + 1 descendenti. Toate frunzele au aceeasi adancime. Nodurile albe marcheza drumul pentru cautarea literei R.

10.1 Structura datelor în memoria pe disc.

Avem la dispozitie multe tehnologii de memorare a datelor. Memoria principala este realizata pe cipuri de siliciu. Aceasta memorie a crescut si s-a ieftinit de-a lungul timpului, totusi ea ramâne mai mica si mai scumpa decât memoria pe medii magnetice desi mult mai rapida.

Timpul unor operatii pe calculator ce includ citiri si scrieri pe disc depind de:

- numarul de accese la disc

- timpul de lucru al procesorului.

Folosim arbori balansati în aplicatii în care datele nu pot intra în memoria Principala. Algoritmii continuti în acest capitol copiaza anumite pagini de memorie de pe disc în memoria principala si, pe cele care s-au modificat, le rescrie (înapoi pe disc). Modelul, din acest punct de vedere, este urmatorul:

Fie x un pointer catre un obiect. Daca obiectul se afla în memoria principala, ne vom referi la câmpuri ca de obicei (ex.KEY(x)). Daca obiectul se afla pe disc, vom face mai întâi o operatie de citire CIT_DISK(x) a obiectului x si apoi ne putem referi la câmpurile lui. Daca s-au efectuat modificari ale câmpurilor lui x ele vor fi actualizate pe disc prin scriere SCR_DISK(x).

fig. 10.2.

Figura 10.2 contine un exemplu de arbore balansat care are mai mult de un miliard de chei.

Ca sa micsoram numarul de accese la disc trebuie sa marim dimensiunea nodului. În general un nod va fi memorat pe o pagina întreaga. Aceasta înseamna un factor de ramificare între 50 si 2000.

10.2. Definitia arborilor balansati.

Vom considera, ca si mai înainte, ca "informatia satelit" asociata cu o cheie este memorata în acelasi nod cu cheia si este "mutata" odata cu mutarea cheii.

Un arbore balansat (echilibrat) T este un arbore cu radacina Rad(T) cu urmatoarele proprietati :

1.Fiecare nod are urmatoarele câmpuri:

a) n( x) numarul de chei de stocate în x

b) cele n( x) chei memorate în ordine crescatoare

KEY₁(x),KEY₂(x),...,KEY_n(x)(x).

c)F(x) cu valoare adevarat daca x este frunza si fals daca x nu este frunza

d) Daca x este nod intern (Frunza(x) este fals) atunci x mai contine n(x)+ 1

pointeri C_l(X),C₂(X) ,... ,C_n(x)+l(X) la copiii (descendentii) lui x

2.Cheile din x separa cheile din descendenti adica daca k_j este o cheie oarecare din descendentul de la adresa C_j( x) cu j atunci

k₁ KEY₁(x) k₂ KEY₂(X) KEY _n(x)(x) k_n(x)+l

3.Fiecare frunza are aceeasi "adâncime" care este înaltimea arborelui.

4.Exista un numar maxim si un numar minim de chei pe care le poate contine un nod care sunt în legatura cu t 2 numit gradul minim al lui T.

a)Fiecare nod, în afara de radacina, are cel putin t-1 chei si deci, daca este intern, are cel putin t descendenti. Daca arborele este nevid, radacina trebuie sa aiba cel putin o cheie .

b)Fiecare nod poate contine cel mult 2t-1 chei (un nod intern are cel mult 2t descendenti). Spunem ca un nod este plin, daca are exact 2t-1 chei.

Cel mai simplu arbore balansat este cu t = 2 unde fiecare nod poate avea 2, 3 sau 4 descendenti.

Înaltimea unui arbore balansat.

Teorema

Daca n 1 este numarul de chei dintr-un arbore balansat cu înaltimea h si gradul minim t 2 atunci h log_t ((n+1)/2).

Demonstratie.

O sa pornim în demonstratie de la un arbore cu numar maxim de chei ca în exemplul urmator.

Figl0.3

Daca arborele are înaltimea h, atunci numarul de noduri este minim când radacina contine o cheie si celelalte noduri contin t-1 chei. În acest caz sunt 2 noduri la primul nivel, 2t la al doilea nivel, si asa mai departe pâna la nivelul h unde sunt 2t^h-1.

n 1+ (t - 1)S2^t-1 =1 + 2(t-1)((t^h-1)/(t-1))= 2t^h - 1

^i=1,h

10.3 Operatii în arbori balansati.

Pentru urmatorii algoritmi vom presupune ca radacina arborelui este în memoria principala, deci nu avem CIT_DISK pentru ea, dar este nevoie de SCR_DISK daca avem actualizari ale câmpurilor radacinii. Mai presupnem ca orice alt nod are nevoie sa fie citit ca sa avem acces la câmpurile lui.

Cautarea în arborii balansati.

Algoritmul este recursiv si se apeleaza prima data cu B_TREE_CAUT(Rad(T), k ,rez), unde k este cheia cautata, rez contine rezultatul cautarii adica perechea (y,i) care înseamna ca nodul y are a i-a cheie KEY(y)=k sau rez=Nil daca cheia nu este în arbore.

B- TREE- CAUT( x,k,rez)

i=l

atât timp cat i<n(x) si k> KEY_i(x)

i=i+l

Sciclu

Daca i n(x) si k = KEY_i(x) atunci

rez = (x, i)

return

sdaca

Daca Frunza(x) atunci

rez = Nil

Return

altfel

Cheama CIT_DISK(c_i(x))

Cheama B_TREE_CAUT(c_i(x), k, rez)

return

sdaca

b.Constructia unui arbore balansat.

Pentru aceasta vom creea mai întâi un arbore vid si vom insera pe rând în el noile chei. Avem nevoie mereu de locuri libere pe disc pe care le fumizeaza ALOC_NOD().

B_TREE_CRE(T)

x = ALOC_NOD( )

Frunza(x) = True

n(x) = 0

SCR_DISK(x)

Rad(T) = x

Return

Daca un nod este plin, ca sa putem insera în continuare, el trebuie rupt în doua, ca în figura 10.4:

Fig.l0.4

Nodul plin are 2t - 1 chei si cheia din mijloc (indice t) se duce în parinte, presupus neplin.

Daca se face ruperea radacinii atunci arborele creste în înaltime cu 1. Procedura B_TREE_RUP are ca intrare un nod intern neplin - x (aflat deja în memoria principala), un index - i si un nod y = c_i(x) care este un descendent plin al lui x.

B_TREE_RUP(x, k, y)

z = ALOC_NOD( )

Frunza(z) = Frunza(y)

n(z) = t-1

Pentru i = 1, t-1

KEY_i(z) = KEY_{i + t}(y)

spentru

Daca nu Frunza(y) atunci

Pentru i=1,t

C_i(z) = C_i+t(z)

spentru

sdaca

n(y) = t-1

Pentru i = n(x)+1,k+l,-1

C_i+l(X) = C_i(x)

spentru

C_i+l(X)= z

Pentru i = n(x), k, -1

KEY_i+l(X) = KEY_i(x)

spentru

KEY_k(x)=KEY _t(y)

n(x) = n(x) +1

SCR_D ISK( x)

SCR_DISK(y)

SCR_DISK(z)

return

Inserarea în arborii balansati.

Putem sa construim acum inserarea care începe cu cazul în care radacina este plina exemplificat în figura 10.5.

Fig.10.5

Cheia k trebuie inserata în arborele T, la locul ei.

B-TREE_INSERT(T, k)

r=Rad(T)

daca n(r) = 2t-1 atunci

s = ALOC_NOD( )

Rad(T) = s

Frunza(T) = False

n(s) = 0

c_l(S) = r

cheama B_TREE_RUP(s, 1, r)

cheama B_TREE_INS_NEPLIN(s,k)

altfel

cheama B- TREE_INS_NEPLIN (r,k)

Sdaca

Return

Procedura B_TREE_INS_NEPLIN parcurge arborele în jos pâna la locul unde trebuie facuta inserarea.

B- TREE_INS_NEPLIN(x, k)

i = n(x)

Daca Frunza(x) atunci 

atata timp cat i 1 si k<KEY_i(x)

KEY_i+1(x) = KEY_i(x)

i=i-1

Sciclu

KEY_i+1(X) = k

n(x) = n(x) + 1

SCR_DISK(x)

atata timp cat i 1 si k<KEY_i(x)

i=i-1

sciclu

i=i+l

CIT_DISK(c_i(x))

Daca n(c_i(x))=2t-l atunci

Cheama B_TREE_RUP(x,i,c_i(x))

Daca k> KEY_i( x) atunci

i=i+ 1

sdaca

sdaca

Cheama B_TREE_INS_NEPLIN(c_i(x), k)

return

Exemple de inserari

Mai multe cazuri sunt reprezentate în figura 10.6.:

(a)  arborele initial

(b) este inserat B

( c ) este inserat Q

(d)    

este inserat L

( e) este inserat F

Fig.10.6.

stergerea unei chei dintr-un arbore balansat.

Aceasta este o operatie similara cu inserarea, dar ceva mai complicata. B_TREE_STERG(x, k) sterge din subarborele T începând în nodul x, cheia k. Grija este ca numarul de chei din nodurile parcurse (altul decât radacina) sa fie t (gradul minim), adica cu 1 mai mult decât de obicei ca sa putem sterge o cheie. Asa ca, uneori, o anumita cheie trebuie sa coboare într-un nod descendent înainte de a-l parcurge. Daca în acest mod radacina x ramâne fara chei atunci singurul descendent c_i(x) va fi noua radacina si x dispare, micsorând astfel înaltimea arborelui cu 1.

Figura 10.7. ilustreaza diversele situatii care se pot întâlni la stergere.

(a) arborele initial

(b ) stergerea lui F: cazul 1

(c) stergerea lui M: cazul2a

(d) stergerea lui G: cazul 2c

(e) stergerea lui D: cazul 3b

(e') arborele scade în înaltime

(e) stergerea lui B : cazul 3a

Contrar obiceiului dam aici numai câteva idei ale algoritmului de stergere:

1.Daca cheia k este în nodul x si x este frunza atunci se sterge pur si simplu k din cheile lui x.

2.Daca cheia k este în nodul x (intern) atunci :

a.Daca descendentul y, care precede k în x (k=KEY_i(x)), y=c_i(x)) are cel putin t chei atunci se gaseste k' care precede pe k si se înlocuieste k cu k' în x (stergând k' din y)

b.Daca z este descendentul care urmeaza pe k se procedeaza simetric cu cazul a.

c.În alt caz (deci când si y si z au t-1 chei adica numarul minim) sterge k din x si adresa c_i+1(x) (catre z) iar cheile k si cele din z se introduc împreuna cu pointerii în y continuând stergerea recursiv cu B_TREE_STERG(y, k).

3.Daca k nu este în nodul intern se determina c_i(x) radacina unui subarbore care

trebuie sa-l contina pe k. Daca c_i(X) are numai t-l chei se executa 3.a. sau 3.b. apoi se reia recursiv pasul 3.

a.Daca c_i(x) are numai t-l chei, dar are un frate alaturat (c_i(x) sau c₊₁(x) care au t chei atunci c_i(x) primeste o noua cheie coborâta din x, urmând sa se completeze numarul de chei cu cheia potrivita din fratele care avea t chei.

b.Daca c_i(x) si toti fratii lui alaturati (c_i-1(x) sau c_i+1(x)) au numai t-1 chei se unifica c_i(x) cu unul dintre fratii alaturati coborând o cheie din x ca cheie mediana în noul nod. (Actiunea este exact inversa ruperilor si determina eliminarea ei si crearea unei noi radacini, aceasta însemnând micsorarea înaltimii arborelui cu o unitate.

Întrebari si exercitii la capitolul 10.

Exercitiul 1.

Construiti un arbore balansat cu t=3 si înaltime =3.

Exercitiul 2.

Ilustrati, pe arborele de mai sus, inserarea si stergerea unui nod.