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













ARBORI BALANSATI (B-Trees)

Informatica



loading...











ALTE DOCUMENTE

Linux
Tehnologia pentru retea Ethernet (I)
Retele de calculatoare
UTILIZAREA PROGRAMULUI OUTLOOK EXPRESS PENTRU POSTA ELECTRONICA partea 3
Model neuronal si arhitecturile retelei
Introducere in programarea orientata pe obiecte
CIRCUITE BASCULANTE ASTABILE
Servicii Internet de baza
Utilizarea aplicatiei FNUASS
Modificarea optiunilor de imprimare


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

KEY1(x),KEY2(x),...,KEYn(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 Cl(X),C2(X) ,... ,Cn(x)+l(X) la copiii (descendentii) lui x

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

k1£KEY1(x)£k2£KEY2(X)£ ... £KEY n(x)(x)£kn(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£ logt ((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 2th-1.

n ³ 1+ (t - 1)S2t-1 =1 + 2(t-1)((th-1)/(t-1))= 2th - 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> KEYi(x)

i=i+l

Sciclu

Daca i£n(x) si k = KEYi(x) atunci

rez = (x, i)

return

sdaca

Daca Frunza(x) atunci

rez = Nil

Return

    altfel

Cheama CIT_DISK(ci(x))

Cheama B_TREE_CAUT(ci(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 = ci(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

KEYi(z) = KEYi + t(y)

spentru

Daca nu Frunza(y) atunci

Pentru i=1,t

Ci(z) = Ci+t(z)

spentru

sdaca

n(y) = t-1

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

Ci+l(X) = Ci(x)

spentru

Ci+l(X)= z

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

KEYi+l(X) = KEYi(x)

spentru

KEYk(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

cl(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<KEYi(x)

KEYi+1(x) = KEYi(x)

i=i-1

Sciclu

KEYi+1(X) = k

n(x) = n(x) + 1

SCR_DISK(x)

atata timp cat i ³ 1 si k<KEYi(x)

i=i-1


sciclu

i=i+l

CIT_DISK(ci(x))

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

Cheama B_TREE_RUP(x,i,ci(x))

Daca k> KEYi( x) atunci

i=i+ 1

sdaca

sdaca

Cheama B_TREE_INS_NEPLIN(ci(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 ci(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=KEYi(x)), y=ci(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 ci+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 ci(x) radacina unui subarbore care

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

a.Daca ci(x) are numai t-l chei, dar are un frate alaturat (ci(x) sau c+1(x) care au t chei atunci ci(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 ci(x) si toti fratii lui alaturati (ci-1(x) sau ci+1(x)) au numai t-1 chei se unifica ci(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.


Document Info


Accesari: 1493
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 )