SDA
Lucrarea 5.
Operatii cu arbori B.
Un arbore B este un arbore general (multicai) cu urmatoarele proprietati:
fiecare nod intern poate contine un numar de chei cuprins între MIN si 2*MIN-1 si un numar de fii (subarbori) care depaseste cu 1 numarul cheilor, adica este cuprins între MIN si 2*MIN
nodul radacina poate sa nu contin 12412v2114m a nici o cheie daca arborele B este vid, sau are cel putin o cheie pentru un arbore B nevid
pentru un nod intern cu c chei: k0<=k1<=...<=kc-1 si c+1 subarbori S0, S1,...,Sc
orice cheie din Si <=ki<=orice cheie din Si+1
toate nodurile frunze au aceeasi adâncime
Cel mai simplu arbore B are MIN=2, un nod intern al sau putând avea 2,3, sau 4 fii, motiv pentru care este cunoscut sub numele de arbore 2-3-4.
.
Vom reprezenta un nod din arborele binar prin:
template <class T>
struct nodAB
Ne propunem în lucrare sa implementam operatiile specifice arborilor B:
cautarea unei chei în arborele B
creerea unui arbore B vid
inserarea unui chei în arborele B
stergerea unei chei din arborele B
Semnaturile acestor functii vor fi:
nodAB cauta(nodAB<T>* rad, T ch, int& ind);
nodAB*& creaza();
void insert(nodAB<T>*& a, T ch);
bool remove(nodAB<T>*& a, T ch);
Cautarea unei chei este o generalizare a cautarii într-un arbore binar. Cheia este cautata mai întâi în nodul radacina. Se poate face o cautare binara, întrucât cheile sunt sortate. Daca nu este gasita în nodul radacina, sunt posibile urmatoarele situatii:
ch < K0 se cauta în S0
ch > Kc-1 se cauta în Sc
Ki-1<ch<Ki se cauta în Si
Prin creerea unui arbore B vid, se face alocare, se initializeaza numarul de chei la zero si nodul ca frunza si se întoarce adresa nodului.
Operatia de inserare a unei chei este putin mai complicata, deoarece nodul în care se face inserarea poate fi plin (are deja 2*MIN-1 chei). Încercarea de inserare într-un nod plin duce la divizarea acestuia în doua noduri continând primele MIN-1, respectiv ultimele MIN-1 chei, iar cheia din mijloc este trecuta în nodul parinte. Daca nodul parinte nu exista (s-a umplut radacina), se creaza o noua radacina (crescând înaltimea arborelui B), care va avea doi fii, proveniti din divizarea vechii radacini si o cheie - cheia mediana din vechiul nod radacina.
Inserarea într-un nod neplin decurge în modul urmator:
daca nodul este frunza se insereaza cheia în pozitia care pastreaza relatia de ordonare între chei si se creste numarul cheilor din nod
daca nodul nu este frunza, se cauta ultima cheie din nod mai mica decât cheia de inserat si se trece în nodul fiu corespunzator. Aici este posibil ca încercarea de inserare sa divizeze nodul, daca acesta este plin.
stergerea unei chei dintr-un nod frunza nu prezinta nici o dificultate, nefiind supusa vreunei restrictii.
Pentru a sterge o cheie ch din arborele B se pleaca din radacina, determinând primul i pentru care Ki >= ch. Pot apare urmatoarele situatii:
În urma stergerii, unei chei dintr-un nod intern, numarul cheilor din nod scade cu 1, putând sa devina mai mic decât MIN-1. Pentru a evita aceasta situatie nodul va fuziona cu un alt nod, lucru permis, întrucât numarul total de chei nu depaseste 2*MIN-1
Pentru a sterge o cheie ch dintr-un nod intern, atunci când fiul Si care precede cheia are cel putin MIN-1 chei, se cauta predecesorul chp al cheii ch în subarborele Si, se înlocuieste ch cu chp si se sterge chp. Operatia continua recursiv sau se opreste.
Daca fiul Si+1 care succede cheia are cel putin MIN-1 chei, se cauta succesorul chs al cheii ch în subarborele Si+1, se înlocuieste ch cu chs si se sterge chs. Operatia continua recursiv sau se opreste.
Daca atât succesorul cât si predecesorul au numai MIN-1 chei, cele doua noduri fuzioneaza, nodul format are 2*MIN-1 chei si din acesta se sterge cheia ch
Daca cheia ch nu apare în nodul intern, se determina subarborele Si în care poate fi. Daca acesta are numai MIN-1 chei se reiau pasii precedenti, pentru a pastra numarul minim de chei, aplicându-se recursiv procedura pentru fiul corespunzator.
Consideram MIN=2 (arbore 2-3-4), având chei numere întregi. Se creaza un arbore B la care se adauga si se sterg succesiv noduri. Vizualizarea arborelui dupa fiecare operatie se asigura printr-o traversare pe niveluri (folosind o coada de adrese de noduri), afisând numarul nivelului, numarul nodului, numarul cheii si valoarea cheii.
Completare: in mesajul din mail profu zicea ca "Stergerea din arbore nu trebuie implementata."
|
