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




























Operatii cu arbori B.

Informatica




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.

  În general, factorul de ramificare MIN=50 : 2000. Înaltimea unui arbore B cu n chei este .


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:

  1. radacina este frunza si cheia nu se afla în radacina. Nu avem în acest caz nimic de sters.
  2. radacina este frunza si am gasit cheia în radacina. O stergem!
  3. radacina nu este frunza si nu am gasit cheia în ea
  4. radacina nu este frunza si am gasit cheia în ea

Î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."










Document Info


Accesari: 3389
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.




eCoduri.com - coduri postale, contabile, CAEN sau bancare

Politica de confidentialitate




Copyright © Contact (SCRIGROUP Int. 2022 )