Arbori-B. Tehnici de insertie si suprimare

1. Scopul lucrarii este prezentarea structurii de arbore-B si a operatiilor principale ce se pot efectua folosind aceasta structura.

2. Aspecte teoretice

2.1. Prezentare

In cazurile in care este nevoie de arbori de foarte mari dimensiuni, in care se realizeaza cautari, inserari si suprimari dese, si pentru care dimensiunile memoriei centrale sunt insuficiente, se poate utiliza o alta categorie de arbori, arborii pe pagini. Aceasta sugereaza faptul ca un arbore poate fi divizat in subarbori si ca acestia pot fi reprezentati ca unitati la care accesul se realizeaza deodata. Aceste subunitati se vor numi pagini.

Arborii-B sunt arbori pe pagini. Structura lor a fost propusa de catre R. Bayer si ei au urmatoarele caracteristici :

fiecare pagina contine cel mult 2*n noduri (chei), unde n este o constanta a intregii structuri;

fiecare pagina, cu exceptia uneia singure, numita pagina radacina, contine cel putin n noduri;

fiecare pagina este fie o pagina terminala (caz in care nu are descendenti), fie are m+1 pagini-descendent, unde m reprezinta numarul de chei in pagina;

toate paginile terminale apar la acelasi nivel.

In cadrul unei pagini, nodurile sunt ordonate in functie de chei. Nodurile apar in pagini in asa fel incat, daca structura se liniarizeaza prin inserarea descendentilor printre stramosii lor, nodurile vor fi ordonate crescator in functie de chei.

Factorul de utilizare a memoriei este de cel putin 50%, deoarece orice pagina este cel putin pe jumatate plina, si, in plus, schema preconizata necesita algoritmi pentru cautare, insertie si stergere mai simpli in comparatie cu alte metode (de exemplu, AVL).

In figura 6.1 este reprezentat un arbore-B de ordinul 2 (n = 2) cu 3 niveluri, in care toate paginile au 2, 3 sau 4 noduri (n = 2, respectiv 2*n = 4), cu exceptia paginii radacina, care poate contine si doar un nod.

2.2. Cautarea unui nod

Cautarea unui nod cu cheia x incepe intr-o pagina ca si cea din figura 6.2, unde p_i reprezinta adresa paginii-fiu i, iar k_i - cheia nodului i. Presupunand ca pagina a fost transferata in memoria centrala, se poate folosi o metoda conventionala de cautare a lui x printre cheile k₁, k₂, . , k_m.

Daca cheia x nu se gaseste, se va ajunge intr-una din urmatoarele situatii:

k_i < x < k_i+1, pentru 1≤i<m cautarea se continua in pagina p_i;

k_m < x cautarea continua in pagina p_m

x < k₁ cautarea continua in pagina p₀.

Cautarea se termina cand nodul cu cheia x a fost gasit sau cand pagina desemnata de algoritmul de mai sus este nula (nu exista nici un nod cu cheia x).

2.3. Insertia unui nod

Insertia unui nod (chei) care nu mai exista in arbore incepe prin cautarea locului nodului de inserat. Avand in vedere ca nodul nu se afla in arbore, cautarea se va opri intr-o pagina terminala, in care se si realizeaza insertia.

Daca pagina in care a avut loc insertia nu a depasit numarul maxim de noduri (2*n), atunci insertia se termina. Altfel, la nivelul acestei pagini va avea loc o scindare (explozie), astfel:

- in locul paginii scindate ramane doar prima jumatate a sa (prima pagina-fiu si primele n noduri cu paginile-fiu urmatoare lor);

- nodul median va fi exclus din pagina, el fiind trimis spre insertie paginii parinte;

- nodul exclus va avea ca pagina urmatoare in parinte a doua jumatate a paginii scindate (aceasta contine ca prima pagina pe cea care a urmat nodului median, precum si ultimele n noduri cu paginile lor urmatoare).

Dupa realizarea scindarii, nodul exclus se va insera in pagina parinte. Este posibil ca si aici sa se produca o scindare si sa se transmita un nod de inserat mai departe, la intoarcerea pe drumul de cautare. Procesele de scindare se pot propaga pana la pagina radacina. O scindare la nivelul acesteia duce la cresterea in inaltime a arborelui-B.

Referat: Contabilitatea tertilor Referat: Structurarea elementelor de activ si pasiv dupa criterii financiare

Ca si exemplu, consideram insertia unui nod cu cheia 25 in arborele din figura 6.1. In figura 6.4 s-a reprezentat si drumul parcurs pentru gasirea locului de insertie (cu linie intrerupta).

2.4. Suprimarea unui nod

Pentru suprimare, intai se cauta nodul. Daca nu s-a gasit, nu avem ce suprima. Daca s-a gasit, se disting urmatoarele doua cazuri:

1)     nodul de suprimat este intr-o pagina terminala;

2)     nodul de suprimat este intr-o pagina care nu este terminala.

Daca ne aflam in cazul 2, atunci nu vom suprima chiar nodul gasit, ci vom cauta predecesorul sau, care se afla intr-o pagina terminala, vom copia informatiile predecesorului peste informatiile nodului de suprimat, apoi vom suprima nodul predecesor, operatie ce se incadreaza in cazul 1 (procedura similara suprimarii din arborii binari ordonati). Predecesorul se gaseste pornind de la pagina anterioara nodului de suprimat si continuand apoi tot pe ultima pagina a paginii curente, pana se ajunge intr-o pagina terminala. Ultimul nod din aceasta va fi predecesorul.

Asadar, suprimarea unui nod se reduce la cazul cand el se afla intr-o pagina terminala. Daca dupa suprimare, numarul de noduri din pagina de unde s-a facut suprimarea respecta criteriul pentru arbore, suprimarea se incheie. Se poate intampla insa ca pagina sa ramana cu mai putin decat n noduri.

Aceasta situatie se poate rezolva prin echilibrare sau prin contopire.

Daca o pagina vecina (din stanga sau din dreapta, pentru ca cel putin una exista) are cel putin n+1 noduri, se poate realiza o mutare de noduri intre cele doua pagini, cu trecere prin nodul din pagina parinte ce se afla intre cele doua pagini vecine, proces numit echilibrare.

Ca si exemplu, consideram ca am suprimat nodul cu cheia 71 din arborele dat ca exemplu. Pagina din dreapta are 3 (n+1) noduri, deci se poate face un transfer de noduri, astfel: 77 va fi ultimul nod din pagina din care s-a suprimat 71 si in locul sau trece 85.

Procesul de echilibrare, precum si cel de contopire, dupa cum se va vedea in continuare, pot avea loc si intre doua pagini vecine care nu sunt terminale. Atunci cand se face un imprumut, nu se imprumuta un singur nod, ci se incearca sa se distribuie nodurile in mod egal intre cele doua pagini.

Pentru echilibrarea cu imprumut din pagina vecina din stanga, prezentata in figura 6.6, j respecta conditia: n ≤ n+j < m.

Inainte de echilibrare, secventa:

p₀ k_n+j p_n+j k_m p_m k_i p₀^' k_n-1^' p_n-1^'

da prin liniarizare noduri ordonate. Acest lucru trebuie sa se intample si dupa echilibrare.

Echilibrarea cu imprumut din dreapta este asemanatoare.

Daca pagina vecina la care se apeleaza pentru rezolvarea situatiei de subdepasire are mai putin de n+1 noduri, deci nu are de unde face un imprumut, atunci cele doua pagini se vor uni intr-una, incluzand si nodul dintre ele din pagina parinte, proces numit contopire.

Ca si exemplu, consideram ca am suprimat nodul cu cheia 71 din arborele dat ca exemplu. Pagina din stanga are 2 (n) noduri, deci va avea loc contopirea, rezultand o pagina cu cheile: 66, 69, 70, 72, pagina parinte devenind subdimensionala (va contine doar nodul cu cheia 77), deci se pune din nou problema echilibrarii sau a contopirii. In acest caz, pagina vecina nu poate da un imprumut, deci se vor contopi, asadar si contopirea se poate propaga inspre radacina. Cand radacina are un singur nod si are loc contopirea celor doua pagini-fiu ale radacinii, noua radacina va fi pagina rezultata prin contopire. Acesta este cazul in care arborele-B scade in inaltime.

Figura 6.8 prezinta procesul de contopire a doua pagini vecine, in general.

3. Problema rezolvata

Sa se creeze un arbore-B in care sa se poata face insertii si suprimari de noduri.

Rezolvare

Programul de mai jos cuprinde crearea unui arbore-B, insertia, suprimarea, precum si cautarea unui nod. Cautarea nu este implementata ca functie separata, ci ea apare atat in cadrul insertiei (se cauta locul pentru noul nod), cat si in cadrul suprimarii (se cauta nodul de suprimat).

Ca si implementare, pentru modelarea arborilor-B, putem considera ca fiecare pagina contine adresa primei sale pagini-fiu si m noduri, fiecare nod avand: informatii specifice (k) si adresa paginii-fiu (p) cu chei mai mari decat cheia sa si mai mici decat ale nodului urmator (daca acesta exista).

In acest program, nodurile dintr-o pagina sunt memorate intr-un tablou.

In cazul suprimarii, daca rezulta o pagina subdimensionala, am urmat urmatoarele conventii:

daca pagina are pagina vecina in stanga (nu este p₀)

daca aceasta poate imprumuta, se face echilibrarea cu aceasta pagina

altfel, se contopesc

altfel, ea are pagina vecina in dreapta

daca aceasta poate imprumuta, se face echilibrarea cu aceasta pagina

altfel, se contopesc.

Programul este urmatorul:

#include <stdio.h>

#include <conio.h>

#include <stdlib.h>

#define n 2

#define nn 2*n

typedef struct _nodnod;

typedef struct _paginapagina;

pagina *pagRad;//pagina radacina a arborelui-B

int indNodCautat, pagFiuSubd;//pag.-fiu este subdimensionala;

pagina *pagParNodCautat;

void Afis(pagina *p, int niv)

Afis(p->pag0, niv+1);

}

nod* Ins(pagina **pg, int x)while(s<=d);

if(s-d>1)

}else d = -1;

//nu l-am gasit => insertie

if((*pg)->pag0==NULL)else//nu e terminala, trimitere mai departe

if(d==-1) // x < primul element

nd = Ins(&(*pg)->pag0, x);

else

nd = Ins(&(*pg)->e[d].pag, x);

if(nd)else

else

if(d+1<n)

else

delete nd;

(*pg)->m = ndExp->pag->m = n;

for(i=0;i<n;i++)

ndExp->pag->e[i] = (*pg)->e[n+i];

return ndExp;

}

}

return NULL;

void Insertie(int x)

//imprumut de la pag-frate stg

void ImprumutDinStg(pagina *pg,int s,int d)

//imprumut de la pag-frate dr

void ImprumutDinDr(pagina *pg, int s, int d)

//contopirea a doua pagini vecine (j este in stg lui k)

void Contopire(pagina *pg, int j, int k)

}//contopire

void LaRevenire(pagina *pg, int k)

else/*k NU are pag-frate vec. in stg. (este pag0) => vom folosi pe cea din dr.*/

if(pg->e[k+1].pag->m>n)

//pag. vecina dr. are de unde da => echilibrare

ImprumutDinDr(pg, k+1, k);

else//pag. vecina nu are de unde da => se vor contopi

Contopire(pg, k, k+1);

//suprima nodul k din pagina terminala pg

void SuprimaNod(pagina *pg, int k)

//primeste pagina in care este nodul de sters si indicele acestuia in pagina

void Predecesor(pagina *pg)else

void Suprimare(pagina *pg, int x)while(s<=d);

if(s-d>1)

}

else//nu l-am gasit pana in aceasta pagina

if(pg->pag0!=NULL)

//nu sunt in pag term. => cont. cautarea

if(d!=-1)

else

else printf('Nod negasit.n');

}else if(pg && !pg->m)

printf('Arborele este vid.n');

void StergArb(pagina *pg)

void main(void)else if(optiune=='2')

}

}while(optiune!='0');

StergArb(pagRad);

4. Probleme propuse

4.1. Sa se modifice problema rezolvata astfel incat:

a)     sa se semnaleze de fiecare data modificarea inaltimii arborelui B.

b)     sa fie permisa insertia multipla (sa poata exista mai multe noduri cu aceeasi cheie).

4.2. Sa se construiasca un arbore AVL si unul B de ordinul n 1, pornind de la aceeasi secventa de chei (generate aleator sau citite dintr-un fisier). Sa se compare inaltimile celor doi arbori si sa se afiseze diferenta lor raportata la numarul de chei, precum si raportul celor doua inaltimi.