Evidența Ceasurilor dintr-un Magazin

TEMA PROIECTULUI

Evidenţa ceasurilor dintr-un magazin

Intr-un magazin trebuie ţinuta evidenţa ceasurilor cu ajutorul unui program care foloseşte structuri arborescente de tip B şi TRIE.

Pentru structura de tip B se vor face următoarele operaţii :

- încărcare în arbore

- inserări

- modificări de date

- ştergeri

- raportul ceasurilor vandute

- afişarea datelor ceasurilor din magazin

- afişarea pe nivele după câmpul ‘cod’ al ceasurilor din magazin

Cu ajutorul acestei structuri se va face trecerea de la B la TRIE apoi se vor afişa pe nivele după câmpul ‘denumire’ ceasurile din magazin.

Informaţiile cuprinse sunt : cod, denumire, preţ, data.

NOŢIUNI TEORETICE

ARBORI B+

Definiţie

Un arbore B de ordin m este un arbore cu următoarele proprietăţi:

-rădăcina este o frunză sau un nod cu 2 până la m descendenţi;

-toate nodurile interne (cu excepţia rădăcinii ) au între sup(m/2) (sup(x) este cel mai mic întreg mai mare ca x) si m descendenţi;

-toate frunzele sunt pe acelaşi nivel.

Trebuie menţionat că mai există si alte definiţii ale arborilor B dar care diferă de aceasta în mod neesenţial. Există anumiţi arbori B care sunt deja consacraţi din punct de vedere al ordinului lor. Acesta este cazul arborelui de ordin 4, numit şi arbore 2-3-4, precum şi al arborelui de ordin 3 cunoscut si sub denumirea de arbore 2-3. În cele ce urmează vom utiliza un arbore 2-3.

Arbori B - exemplu

În figura este prezentat un arbore 2-3. În nodurile interne sunt memoraţi pointerii la subarborii corespunzători, precum si cheile minime din aceşti subarbori. Liniuţele din noduri reprezintă absenţa celui de-al treilea subarbore. Frunzele sunt reprezentate prin dreptunghiuri si conţin informaţia efectivă. Aşa cum se poate observa, cheile din frunze sunt ordonate.

Proprietăţi

În arborii B informaţia este memorată în frunze. Nodurile interne conţin pointerii p1,p2, , pm către descendenţi si valorile k1, k2, ,km-1, reprezentând cheile cele mai mici din subarborii p1,p2, , pm.

Pentru fiecare subarbore, cheile din p1 sunt mai mici decât cheile din p2 ş.a.m.d. Desigur, unii dintre aceşti subarbori pot fi vizi, iar cheile vor fi în acest caz nedefinite.

Informaţia efectivă este memorată în frunze direct sau prin pointeri la alte structuri ce o conţin. În cele de faţa vom presupune prima alternativă, pentru uşurinţa prezentării.

Operaţii de bază asupra arborilor B

1)Căutarea unei chei intr-un arbore B

2)Inserarea unei chei intr-un arbore B

3)Eliminarea unei chei intr-un arbore B

1)Arbori B - căutare cheie

Pentru a regăsi o cheie într-un arbore B, se porneşte de la rădăcină şi se alege o anumită ramură în funcţie de relaţia în care se află cheia respectivă cu cheile din rădăcină. Procesul continuă în acelaşi mod pe nivelurile următoare, până se ajunge la o frunză, în care se face o căutare ordonată.

Din descrierea strategiei de căutare, ne aşteptăm ca durata operaţiei de căutare să fie proporţională cu înălţimea arborelui. Într-adevăr, înălţimea unui arbore B de ordin m este , iar operaţia de selecţie a ramurii pe care trebuie să continue căutarea durează O(log m) (în cazul căutării binare). Deci în cazul cel mai defavorabil, căutarea unei chei într-un arbore B durează

2)Arbori B - inserarea unei chei

Pentru a adăuga o cheie inexistentă într-un arbore B, facem o căutare în arbore pentru a găsi frunza în care cheia trebuie inserată si dacă putem o inserăm. Ce înseamnă dacă putem? O frunză nu poate conţine mai mult de m chei. Dacă numărul de chei din frunza în care trebuie adăugată cheia este mai mic decât m, atunci cheia poate fi inserată. Acesta este cazul din figura 1. în care este ilustrată inserarea cheii 28.