structuri de date

CUPRINSCUPRINS………………………………………………………….1CAPITOLUL 1 Structuri elementare de date……………………...3

1.1 Structuri liniare…………………………………....…….31.2 Stive………………………………………………....…..31.3 Coada…………………………………………………....5Întrebări şi exerciţii la capitolul 1…………………………..8

CAPITOLUL 2. Structuri externe de date…………………………9Întrebări şi exerciţii la capitolul 2…………………………14

CAPITOLUL 3 Modelul reţea……………………………………153. 1 Noţiuni de bază şi definiţii……………………………163.2.1. Transformnarea unei relaţii n-are…………………..203.2.2. Transformarea relaţiilor n la m……………………..20 3.3. Limbajul de definire al datelor (DDL)………………..21Întrebări şi exerciţii la capitolul 3…………………………22

CAPITOLUL 4 Modelul ierarhic……….………………………..23Întrebări şi exerciţii la capitolul 4……….………………...27

CAPITOLUL 5 Modelul relaţional………………………………282.1. Scurf istoric al modelului relaţional…………………..282.2. Modelul relaţional al datelor………………………….282.3 Structura relaţională a datelor…………………………31Întrebări şi exerciţii la capitolul 5…………………………32

CAPITOLUL 6 Arbori binari…………………………………….33 Întrebări şi exerciţii la capitolul 6…………………………38

CAPITOLUL7 Cozi de prioritate (cu HEAP).…………………..397.1 Operaţii asupra unei cozi de priorităţi…………………44Întrebări şi exerciţii la capitolul 7…………………………47

CAPITOLUL 8 Arbori binari de căutare………………………...478.1.Ce este un arbore binar de cautare…………………….478.2.Operaţii asupra unui arbore binar de căutare………….48Întrebări şi exerciţii la capitolul 8…………………………55

CAPITULUL 9 HASH – TABLES………………………………56 9.1. Tabele cu adresare directă…………………………..56 9.2. Tabele de repartizare .(hash-tables)…………………..589.3. Funcţii de repartizare (hash funcţii)…………………..619.4.Adresarea deschisă…………………………………….63Întrebări şi exerciţii la capitolul 9………………………....67

10. Arbori balansaţi (B-Trees)……………………………………6810.1 Structura datelor în memoria pe disc…………………68 10.2. Definiţia arborilor balansaţi.………………………...69

1

10.3 Operaţii în arbori balansaţi…………………………...71Întrebări şi exerciţii la capitolul 10………………………..77

CAPITOLUL 11. Arbori roşu-negri……………………………..7811.1.Proprietăţle arborilor roşu-negri……………………...7811.2.Rotaţii………………………………………….……..7911.3.Inserarea……………………………………….……..8111.4 Ştergerea……………………………………………..83Întrebări şi exerciţii la capitolul 11………………………..85

CAPITOLUL 12 Îmbogăţirea structurilor de date……………….86Întrebări şi exerciţii la capitolul 12………………………..94Capitolul 13 Heap-uri binomiale şi Fibonacci…………….9513.1 Despre necesitatea unor altfel de structuri…………...9513.2 Heap-uri binomiale…………………………………..9813.3 Arbori binomiali……………………………………...9913.4 Operaţii pe heap-uri binomiale……………………...10313.3 Heap-uri Fibonacci………………………………….11313.4 Metoda de potenţial………………………………....11513.5 Operaţii cu heap-uri interclasabile.............................11713.6 Mărginirea gradului maxim…………………………130 Rezolvarea unor probleme dintre cele propuse…………..133

BLIOGRAFIE…………………………………………………...143

2

CAPITOLUL 1 Structuri elementare de date.

În capitolul 1, introductiv, recapitulăm câteva din noţiunile introduse la ‘algoritmică’ şi anume:

structuri liniare vectori, matrici, stive, cozi alocarea stucturilor liniare

secvenţială înlănţuită

Am folosit, până acum structuri foarte simple de date cum ar fi : variabile simple (dintre care unele aveau domeniul de valori formate

doar din două valori). vectori cu componentele sortate sau nesortate (aşa cum sunt folosiţi

în matematică). matrici considerate ca vectori de vectori sau ca masive biortogonale.Vom studia acum alte structuri ceva mai complicate.

1.1 Structuri liniare.O structură liniară este o mulţime de n 0 componente x(1),x(2),

…,x(n) cu proprietăţile:a) Cand n=0 spunem ca structura este vidă.b) Daca n > 0 atunci x(1) este primul element iar x(n) este ultimul

element.c) Oricare ar fi x(k) unde k{2,…,n-1} există un predecesor x(k-1)

şi un succesor x(k+1).Ne va interesa să executăm cu aceste structuri urmatoarele operaţii:

-adăugarea unui element-extragerea unui element-accesarea unui element x(k) din structură-combinarea a două sau mai multe structuri într-una singură-“ ruperea “ unei structuri ăn mai multe structuri-sortarea elementelor unei structuri-căutarea unui element al structurii care are anumite proprietăţi

etc…1.2 Stive.

3

Una din cele mai folosite structuri liniare este stiva.O stivă este caracterizată de disciplina de intrare şi ieşire din stivă.

Să considerăm o mulţime de cărţi puse una peste alta ; există o primă carte care se poate lua foarte şor (TOP) şi o carte care se poate lua numai dacă deplasez toate celelalte carţi (BOTTOM).

Disciplina unei stive este “ ultimul intrat - primul ieşit “ (disciplină care nu v-ar place să fie respectată când staţi la rând la lapte ! ) ( Last in, first out - prescurtarea acestei reguli este LIFO).

Care ar fi diferenţele fată de un vector :-un vector are o lungime fixă, non zero cunoscută aprioric-o stivă poate fi vidă-stiva are un numar variabil de elemente în timpul execuţiei unui

algoritmSe pune problema reprezentării concrete a unei stive în memoria unui

calculator. Putem aloca o stivă în două moduri : I ) SecvenţialII ) Înlănţuit

I ) Alocarea secvenţială a stivei.Folosim vectorul ca fiind structura cea mai apropiată de structura reală a

memoriei. În vectorul (x (i) ) i=1,n

| x(1) | x(2) | x(3) | … | x(k) | … | x(n) | Bottom Top-din n componente ale unui vector doar ‘k’ elemente fac parte din stivă.

Algoritmul de intrare în stivă va fi :

a STIVA Daca k = n atunci DEPASIRE

altfel k = k + 1x(k) = a

SdacaReturn

Algoritmul de ieşire din stivă va fi :a STIVA Daca k = 0 atunci STIVA VIDA

altfel

4

a = x( k )- k = k – 1

SdacaReturn

II ) Alocarea înlanţuită a stiveiÎn alocarea înlănţuită fiecare element al structurii este însoţit de adresa

la care se afla precedentul element. Vom avea vârful pus în evidenţă (ancorat) în INC şi un semn special “” în loc de adresa bazei ca în figura următoare :

| INFO | LEG |

INC | || x(k) | ||x(k-1) | |…|x(2) | ||x(1) | |

(Ordinea 1,2,…,k este ordinea intrării în stivă).În acest caz intrarea în stivă va folosi stiva de locuri libere (această stivă

se numeşte LIBERE) pentru a obţine locuri la introducerea în stivă.Vom prezenta în continuare algoritmii de intrare-ieşire dintr-o stivă în

cazul în care alocarea ei a fost înlănţuită :Algoritmul de intrare in stiva va fi :

a STIVA yLIBEREINFO(y) = a ; LEG(y)=INC ; INC = yReturn

Algoritmul de ieşire din stivă va fi :

a STIVA Daca INC= ‘ ’ atunci ‘STIVA VIDA’

Altfel INCLIBERE

a=INFO(INC)INC=LEG(INC)

SdacaReturn

1.3 Coada.O altă structură liniară utilizată în conceperea algoritmilor este coada. O

coadă este caracterizată şi ea de o disciplină de intrare-iesire, bineinţeles

5

diferită de cea a stivei. De această dată puteţi să vă gândiţi la coada la lapte: primul care s-a aşezat la coadă va fi primul servit, adică primul care iese din coadă.

Disciplina unei cozi este “primul venit, primul plecat” ( “first in, first out “ având prescurtarea FIFO).

O coadă poate fi vidă şi are şi ea un număr variabil de elemente în timpul execuţiei unui algoritm.I ) Alocarea secvenţială a cozii.

Coada alocata secvenţial îşi va găsi locul tot într-un vector (x(i)),i=1,n.| x(1) | x(2) | … | x(f) | … | x(s) | … | x(n) |

FAŢĂ SFÂRŞIT

Din cele ‘n’ componente ale vectorului doar componentele x(f) … x(s) fac parte din coadă. Algoritmul de intrare în coadă va fi :

a COADA Daca S = n atunci ‘DEPASIRE’

Altfel S = S + 1x(S) = a

SdacaReturn

Algoritmul de ieşire din coadă va fi :

aCOADADaca F> S atunci COADA VIDA

Altfela=x(F);F=F+1

SdacaReturn

Se poate imagina uşor ca procedând în acest fel (scoţând din faţă şi introducând la sfârşit) coada “migrează” spre dreapta şi poate să ajungă în situaţia DEPASIRE când de fapt mai există mult loc gol (în vectorul x) pe primele poziţii. Apare astfel ideea de a folosi elementele vectorului ca şi cum ar fi dispuse circular:

6

FATA| x(F) |

| x(2) | | x(1) || x(n) | | x(S) |SFARSIT

Este locul ca cititorul să facă primul efort de a scrie algoritmii de intrare-ieşire din coada circulară.Exerciţiul 1 şi 2.

II ) Alocarea înlănţuită a cozii.Se face în mod similar cu alocarea înlănţuită a stivei în noduri de tipul:

| INFO | LEG |

| x(F) | || | | … | x(S) | | FAŢĂ SFÂRŞIT

Algoritmul de intrare în coadă va fi :

7

a COADA yLIBEREINFO(y) = a ; LEG(SFARSIT)=y Return

Algoritmul de ieşire din coadă va fi :

a COADA Daca FATA= ‘ ’ atunci COADA VIDA

Altfel a=INFO(FATA)

FATALIBEREFATA=LEG(FATA)

SdacaReturnÎntrebări şi exerciţii la capitolul 1.Exerciţiile 1 şi 2 se referă la coada circulară şi sunt cuprinse în text.Exerciţiul 3.Consideraţi două stive alocate în acelaşi vector.

a. care va fi disciplina de umplere? Faceţi un desen.b. scrieţi algoritmii de intrare-ieşire pentru stiva 1.c. scrieţi algoritmii de intrare-ieşire pentru stiva 2.

Exerciţiul 4Consideraţi o matrice patratică de ordinul n în care toate elementele deasupra diagonalei principale sunt egale cu 0.

a) câte elemente pot fi diferite de 0?b) aranjaţi, pe linii, elementele acestea (de pe diagonala principală şi

de sub ea) într-un vector. Faceţi un desen.c) Dacă matricea este A şi vectorul este B, A(i,j) se va duce în B(k).

Daţi formula pentru calculul lui k în funcţie de i şi j.d) Daţi şi formula invers: i şi j în funcţie de k.e) Scrieţi algoritmul care citeşte matricea A şi trece elementele de

pe diagonala principală şi de sub ea în vectorul B.f) Scrieţi algoritmul care, pornind de la doi vetori B1 şi B2,

obţinuţi ca la punctul e) din matricile A1 şi A2 calculează imaginea MB a matricii produs A1xA2. (Arătaţi, mai întâi, că produsul este o matrice de aceeaşi formă.)

8

CAPITOLUL 2. STRUCTURI EXTERNE DE DATE . ASPECTE ALE ORGANIZARII FIZICE A BAZELOR DE DATE În acest capitol vom învăţa:

Cum se desfăşoară o operaţie intrare-ieşire Cum este organizat un disc magnetic Care sunt factorii de performanţă ai discului Cum se calculează timpul de transfer al datelor Care sunt formatele de memorare pe disc

De modul în care sunt păstrate datele pe memoria externă depinde regăsirea informaţiei dorite în forma dorită într-un timp acceptabil. Dacă problema formei se poate rezolva mai uşor, problema obţinerii datelor în timp util este mai greu de rezolvat şi organizarea va fi subordonată rezolvării acestei probleme. Accesul fizic este prezentat schematic în urmatoarea figură:

9

Fig.2.1Figura arată cum cererea emisă de utilizator, într-un limbaj evoluat,

este translatată într-o forma efectivă (cea mai eficientă) pentru execuţie. Cererea translatată activează managerul de buffer care controlează mişcarile datelor între memoria principală şi cea secundară (în general pe disc magnetic). Managerul de fişier transferă de pe memoria secundară datele conform unei structuri definite tot de utilizator în dicţionarul de date.

Memoria principală ese o memorie foarte rapidă care conţine programele şi datele, transferate din memoria secundară cu care se lucrează la un moment dat; ea mai poate conţine câtiva megabaiţi de date dar, în general, este prea mică pentru totalitatea datelor.

Memoria secundară este realizată fizic pe suport magnetic disc( mai des) şi bandă. Discul magnetic este cel mai folosit pentru ca asigura un acces rapid la date şi poate realiza accesul direct; banda magnetică deşi mult mai ieftină, este prea lentă şi se foloseşte mai des pentru arhivare. Partea de hard a calculatorului care rezolvă sarcinile de scriere-citire a dlscului magnetic este unitatea de disc. În unitate se află un pachet de unul sau mai multe discuri pe un ax comun într-o mişcare permanentă de rotaţie cu o mare viteză. În figură se poate observa componenta discului cu faţa magnetizată organizată pe piste (cecuri concentrice), cu mecanismul de acces care prin mulţimea de capete generează din pistele parcurse concomitent de capete aşa numitul cilindru. Această structură fizică permite accesuI direct la

10

o anumită înregistrare (noţiune logică) dacă se specifică numarul de cilindru, numărul de suprafaţă şi numărul de înregistrare.

11

Factorii de performanţă ai discului. Timpul de cautare(A), este timpul necesar poziţionării dispozitivului de acces (împreună cu capetele de citire-scriere) pe cilindrul cerut. În general mişcarea pâna la cilindrul alăturat nu va dura la fel de mult ca mişcarea de la primul la ultimul cilindru. De obicei pen~ acestt~mp se foloseşte o valoare medie dată de timpul poziţionare de la primul cilimdru la mljlocul discului. 12 sau 20 de milisecunde sunt timpi tipici de căutare în funcţie de modelul de unitate de disc.

Timpul de activare al capetelor este timpul necesar pentru a determina electronic care din capetele de citire-scriere va fi activ (adică pe ce suprafaţă se va face operaţia de intrare-ieşire) acest timp este în general foarte mic în comparaţie cu ceilalţi timpi şi se neglijează în calcule.

Intervalul de rotaţie este timpul necesar discului în mişcare de rotaţie să ajungă la blocul care trebuie citit sau scris astfel ca tranferul de date să poată începe. Acest interval depinde de doi factori: viteza de rotaţie a discului şi poziţia relativă a noului bloc dată de poziţia de moment a discului. Fizic acest timp poate varia între zero şi timpul de revoluţie al discului; deci în medie se va consuma un timp egal cu R/2.

Rata de transfer al datelor (D) se referă la timpul necesar transferului datelor

Fig2.2de pe suprafaţa magnetică în memoria principală. Acesta este în funcţie de viteza de rotaţie a discului şi de densitatea datelor inregistrate. Acest timp este în general exprimat în mii de baiţi pe secundă. Timpul de transfer al datelor este timpul în care se speră să se ajungă la adresă şi să se realizeze transferul; deci formula de calcul va fi:

T=A+R/2+L/Dunde A este timpul de căutare, R este timpul de revoluţie (rotaţie completă), L este lungimea blocului în baiţi şi D este rata de transfer a datelor.

Exemplu de calcul pentru inregistrari accesate direct: Sa presupunem că o instituţie are depuse datele pe un disc câte trei înregistrări per bloc, (factor de blocare 3) şi fiecare înregistrare are 200 de baiţi. Rata de transfer a datelor este de 806000 baiţi pe secundă. Timpul mediu de căutare este de 30 milisecunde. Discul se roteşte cu 7200 rotaţii pe minut. Care va fi timpul de transfer al datelor? Să fixăm mai întâi variabilele: A=0.03 secunde Viteza de revoluţie pe secundă va fi R=7200/60= 120 R=1/120=0.0083 secunde R/2= 0.00415 L/D=600/806000=0.00074

12

Deci: T=0.03+0.00415+0.00074=0.03489 secunde

Exemplu cu înregistrari accesate secvenţial: Să presupunem ca în loc de a accesa un bloc, ca în exemplul precedent, avem de accesat un fişier cu plăţile făcute de la începutul lunii. Are sens să considerăm ca un astfel de fişier este secvenţial umplut în ordinea în care se fac plăţile şi deci cilindri succesivi sunt parcurşi pentru scrierea sau citirea unui asemenea fisier secvenţial. Se realizează, evident, în acest fel o economie de mişcări ale capetelor de citire-scriere: de exemplu, dacă capetele se afla la inceputul fişierului, pe primul cilindru ocupat, timpul de căutare va fi nul sau va fi pus o singură dată, pentru prima căutare, deci el poate fi ignorat. Vor fi numai mici mişcări la trecerea de la o pistă la urmatoarea (pentru alinieri) care poate fi evaluată în medie cu parcurgerea a jumătate de pistă. Pe o pistă nouă, o dată început transferul, blocurile pot fi transferate fără interval de rotatie, deci dacă avem de parcurs 8 piste, vom avea numai de 8 ori intervalul de rotaţie, indiferent de numărul de blocuri transferate.

Să presupunem, în continuare, că trebuiesc transferate 1000 de blocuri de pe fiecare din cele 8 piste, deci un total de 8000 de blocuri şi dacă factorul de blocaj este tot 3 asta însearnnă 24000 de înregistrări. Vom presupune, ca şi mai înainte, că fiecare înregistrare are 200 de baiţi deci blocul va fi de 600 de baiţi. Dacă avem de accesat întregul fişier atunci timpul mediu de acces pe înregistrare va fi: Timpul total de citire a fişierului= 0.00415*8+0.00074*8000=5.9532, iar

T=5.9532/8000=0.0007415 secundeUnde Teste timpul mediu de acces la o înregistrare. 2.2 Formate ale datelor memorate pe disc.

Formate de pistă. Datele se pot memora pe o pistă cu cheie sau fără cheie. Este momentul aici să facem diferenţa între înregistrarea logică şi fizică; între orice două înregistrări de pe o pistă apare un spaţiu ‘liber’, gap, care are o lungime variabilă determinată de posibilitaţile hard de citire-scriere şi care, evident, ocupă loc pe suportul magnetic. Pentru a micşora acest spaţiu ocupat neproductiv, se grupează mai multe înregistrări logice într-una singură fizică pe pistă, grup care se numeşte bloc. Acolo unde nu există confuzie vom folosi noţiunea de înregistrare şi pentru cea fizică şi pentru cea logică, dar cele două noţiuni nu coincid decât când blocul conţine o singură înregistrare. Numărul de cilindru, numărul de cap (de citire-scriere) şi numărul de înregistrare dau o adresă unică pe suportul magnetic pentru fiecare înregistrare. Ceea ce se va citi sau scrie, la un moment dat, va fi o înregistrare fizică, addică un bloc (cu probleme rezolvate de soft la sfârşit de fişier), iar

13

‘desfacerea’ blocului în înregistrări logice este tot o sarcină a sistemului de operare. Dacă înregistrarea este blocată, cu cheie atunci cheia înregistrarii fizice (care nu poate fi decât una) va fi cea mai mare cheie dintre cheile din bloc.

Formate de inregistrare. Datele pot fi memorate, pe disc, într-unul din următoarele patru formate:

Inregistrări de lungime fixă. Aşa cum spune şi denumirea apare atunci când înregistrările logice sunt de lungime fixă, deci ele vor da naştere la înregistrări fizice de lungime fixă blocate sau neblocate.

Atunci când înregistrările logice pot avea lungimi care diferă vom avea şi înregistrări fizice de lugime variabilă (blocate sau nu). Strucura acestor tipuri de înregistrări este prezentată în figura următoare. (a) Fixe neblocate .

(b) Fixe blocate.

(c) Variabile neblocate.

(d) Variabile blocate

14

Întrebări şi exerciţii la capitolul 2Exerciţiul 1.Să presupunem că o instituţie are depuse datele pe un disc câte patru înregistrări per bloc şi fiecare înregistrare are 250 de baiţi. Rata de transfer a datelor este de 80000 baiţi pe secundă. Timpul mediu de căutare este de 20 milisecunde. Discul se roteşte cu 7200 rotaţii pe minut. Care va fi timpul de transfer al datelor în acces direct?Exerciţiul 2.În aceleaşi condiţii de hard, să presupunem că trebuiesc transferate 1000 de blocuri de pe fiecare din cele 8 piste, deci un total de 8000 de blocuri. Care va

fi timpul de transfer al datelor în acces secvenţial?Exerciţiul 3.Care sunt factorii de performanţă ai discului?

În capitolele 3,4 şi 5 prezentăm cele mai importante modele de descriere a datelor în bazele de date. Veţi învăţa despre ele

Ce este modelul reţea Cum se adaptează o diagramă ER oarecare pentru modelul reţea Care este limbajul DDL pentru modelul reţea Ce este modelul ierarhic Cum se adaptează o diagramă ER oarecare pentru modelul

ierarhic Care este limbajul DDL în limbaju sistemului IMS Ce este modelul relaţional Ce este şi cum trebuiesc interpretate operaţiile şn algebra

relaţională

CAPITOLUL 3 MODELUL REŢEA.

15

Prezentăm aici modelul reţea aşa cum a fost el formalizat de CODASIL .

Modelul reţea este un model care conţine înregistrări, date şi relaţii 1 la mai mulţi între înregistrări.

Legătura dintre înregistrarea client şi înregistrarea factură reprezintă o relaţie de unu- la-mai-multe. Înregistrarea de pe partea ‘1’ se va numi proprietar iar cea de pe partea ‘mai-multe’ se va numi membru.

Relaţia unu-la-mai-multe reprezentată mai sus înseamnă că există posibilitatea ca 0 ,1 sau mai multe facturi sa fie în legătură cu un client dat.

Există situaţii în care relaţia este unu-la-unu de exemplu camionul şi şoferul, dar ea este tratată la fel. Forma generală a unei structuri de date în cazul modelului reţea este dată în figura 3.1.

Fig.3. 1Aceasta schemă poartă numele de diagrama lui Bachman.

In figura 3.2 va fi prezentata o schemă a unei structuri de date obţinute din diagrama Bachman prin introducerea instanţelor (actualele valori ale înregistrărilor din structura de date).

16

Reţelele sunt un mod natural de a reprezenta legăturile care se stabilesc între obiecte. Ele sunt des folosite în matematică, operaţii de căutare, chimie, fizică, sociologie şi alte domenii de cercetare. Atât timp cât marile concerne folosesc obiectele şi legăturile dintre ele pentru a modela fenomenele comerciale, nu ne va surprinde că arhitectura unei reţele este aplicată şi în organizarea bazelor de date. În general reţelele sunt reprezentate cu ajutorul unei structuri matematice numită graf orientat. 3. 1 Noţiuni de bază şi definiţii.

Modelul reţea aplicat bazelor de date este reprezentat de o arhitectură pe trei nivele după cum urmează:

1. nivelul conceptual ( aspectul logic al tuturor datelor şi al relaţiilor din baza de date) numit schema.

2. nivelul extern ( punctele de vedere ale utilizatorilor în ceea ce priveşte necesarul de date pentru diferitele aplicaţii ) numit subschema.

3. nivelul intern ( detalii referitoare la memorarea fizică ) este implicită în faza de implementare.

La modelul reţea sunt doar două structuri fundamentale si anume : - îmregistrarea sau record (o colecţie de date logic legate între ele) - legătura sau set (o relaţie de unu-la-mai-multe sau unu-la unu între

două lnregistrări). Exemplu :

Înregistrarea unui client trebuie să cuprindă urmatoarele date: Clientul, Nume, Adresa, ValoareDatorata, DataultimeiPlati . De reţinut : vom identifica aceasta colecţie ca o inregistrare client prin specificarea numelui înregistrării. Toate înregistrările vor primi nume ca CLIENT, FACTURA, FURNIZOR şi aşa mai departe.

17

Fig.3.2

În figura 3.2 am aplicat câteva convenţii de reprezentare a modelului reţea sub formă de diagramă. Legăturile sunt reprezentate prin săgeţi de la înregistrarea proprietar către înregistrarea membru, fiecare legătură având un nume corespunzator etichetei din dreptul săgeţii. Această diagramă corespunde unui graf orientat în care nodurile conţin înregistrările iar arcele sunt legăturile dintre înregistrări.

În figura 3.1 putem vedea trei tipuri de legături: - CLIENT-FACTURA legătura dintre proprietarul CLIENT si membrul FACTURA - FURNIZOR-FACTURA legătura dintre proprietarul FURNIZOR şi membrul FACTURA - FACTURA-LINIEFACT legătura dintre proprietarul FACTURA şi membrul LINIEFACT

Reţea simplă este structura de date în care toate legăturile se stabilesc pe baza relaţiilor de tip unu-la-mai-multe.

Reţea complexă este structura de date în care toate legăturile se stabilesc pe baza relaţiilor de tip multe-la-mai-multe.

În figura 3.3 este un exemplu de reţea complexă:

Fig.3.3.Dar o reţea complexă nu poate fi implementată direct, de aceea este necesară transformarea ei într-o reţea simplă penru a putea raspunde cerinţelor de implementare. Pentru a realiza această transformare vom folosi o înregistrare de legătură care are cel puţin cheile celor două entităţi proprietar respectiv membru (celelalte

18

atribute pot fi adăugate după dorinţa proiectantului). Figura 3.4 ilustrează cum o reţea complexă este transformată într-una simplă.

Fig.3.4In figura 3.5 vom vedea ce devine schema din fig.3.4 după introducerea instanţelor.

Fig 3.53.2.Modelarea conceptual semantică a relaţiilor în modelul reţea. Modelul reţea poate fi gândit ca un model conceptual de date cu toate relaţiile limitate la legături între două obiecte unde relaţiile sînt de unu la mai multe sau unu la unu. Acestea permit o reprezentare grafică simplă a structurilor de date. În schimbul mulţimilor de obiecte ale modelului conceptual de date avem înregistrari logice (înregistrările văzute din perspectiva utilizatorlui) care sînt conectate cu alte înregistrări logice prin conectări fizice conectarea înregistrărilor folosind adresa de pe disc a acestora. Fiecare conectare reprezintă o relaţie între exact două înregistrări. Relaţia dintre două înregistrări conectate fizic fac trimitere către o legătură. Vom considera o întreprindere având următoarele departamente: marketing şi contabilitate. In figura 3.6 vom prezenta un fragment din modelul

19

Fig.3.6conceptual de date care ilustrează relaţiile dintre clienţi şi conturi . In figura 3.7 vom arăta cum acest fragment din modelul conceptual este transformat într-o sructură de date de tip reţea.

Fig.3. 7.In figura 3.8 vom prezenta ce ar însemna o relaţie de unu-la-mai-multe între client şi cont.

Fig.3. 8

Figura are următoarea semnificaţie: un client poate avea mai multe conturi dar un cont poate aparţine unui singur client.

Putem da uşor un exemplu în care un cont poate aparţine mai multor clienţi dar fiecare client poate avea un singur cont.

20

Din precedentele exemple putem deduce urmatoarele reguli de transformare a modelului conceptual In model logic reţea.

- Regula 1. Pentru fiecare obiect al unei scheme conceptuale se crează o lnregistrare R in structura de date de tip reţea. Toate atributele ei sunt reprezentate ca şi câmpuri ale înregistrării R. - Regula 2. Pentru o relaţie unu-la-mai-multe înregistrarea de pe partea 1 devine proprietar, iar înregistrarea de pe partea ‘mai-multe’ devine membru. Dacă relaţia este de tipul unu-la-unu atunci proprietarul şi membrul pot fi arbitrar aleşi.

3.2.1. Transformnarea unei relaţii n-are. Într-o întreprindere pot apărea relaţii pe trei căi ,după cum se poate vedea în figura 3.8 acestea nesatisfăcând cerinţele unei relaţii binare. Totuşi exista o cale pentru a indeplini aceste cerinţe ,lucru aratat in figura 3.9.

Fig.3.9.- Regula 3. Pentru orice relatie n-ara ,n > 2,se creaza o ‘înregistrare de conectări’ care va fi o înregistrare membru corespunzătoare înregistrărilor proprietar obţinute pe partea ‘n’ a relaţiilor de tip unu-la-mai-multe obţinute în urma acestei transforrnări.

3.2.2. Transformarea relaţiilor n la m. Am văzut deja, în fig 3.3 că o relaţie poate fi n la m. Iată, în continuare

un alt exemplu: un produs poate fi făcut de mai mulţi furnizori şi un furnizor poate face mai multe produse.

21

Pentru aceasta diagramă un exemplu de instanţă ar putea fi cel din diagrama următoare

- Regula 4. Pentru o relaţie mai-multe-la-mai-multe între două obiecte O1 şi O2 se crează o înregistrare de conectări care devine înregistrare membru pentru fiecare dintre înregistrarile proprietar corespunzătoare obiectelor O1 şi O2 .

3.3.Limbajul de definire al datelor (DDL). În 1971 grupul Database Task Group a publicat un raport înaintat la

ANSI ( American Standard Institute) pentru standardizare. Raportul crează modelul CODASYL DBTG care a stat la baza mai multor modele comerciale cum ar fi S (Honeywell) IMS (Computer Associates). Limbajul DDL pentru descrierea schemei, al DBTG este prezentat în continuare pe un exemplu.

După cum am văzut mai înainte, schema conceptuală trece prin mai multe stadii pentru a putea fi transpusă în model reţea. Paşii acestei transformări sunt:

1. Crearea poiectului conceptual.2.1 Transformarea modelului conceptual în model reţea urmărind 2.1

relaţiile 1 la n se vor transcrie fără probleme în DDL .2.2 Relaţiile n la m se transformă în două seturi având relaţii 1 la n

adăugând entitatea necesară de legatură. 2.3 Dacă sunt relaţii complexe, n-are, se convertesc în relaţii binare

conform modelului prezentat .3. Se traduce în DDL modelul obţinut. În acest limbaj avem componentele: - secţiunea record (înregistrări)

22

- secţiunea set care specifică legăturile dintre înregistrări. Să considerăm diagrama conceptuală din fig 3.10

fig.3.10.Transformată în model reţea se poate vedea în figura următoare.

Acest model dă naştere la următoarea secvenţă în DDL al DBTG. 1. SCHEMA NAME IS INTRARI 2. RECORD NAME IS CLIENT 3. CLIENT-ID TYPE IS NUMERIC INTEGER 4. NUME TYPE IS CHARACTER 15 5. ADRESA TYPE IS CHARACTER 20 6. VAL-CONT TYPE IS NUMERIC (5.2) 7. RECORD NAME IS FACT 8. NRFACT TYPE IS NUMERIC INTEGER 9. DATA TYPE IS CHARACTER 9

23

10. RECORD NAME IS LINIE-FACT 11. COD-PROD TYPE IS NUMERIC INTEGER 12. PRET TYPE IS NUMERIC (13.2) 13. CANT TYPE IS NUMERIC (6.2) 14. CLIFACT 15. OWNER IS CLIENT 16. MEMBER IS FACT 17. FACTLIN 18. OWNER IS FACT . 19. MEMBER IS LINE-FACT În programe se va defini numai subschema care dă un acces limitat la date. Limbajul DBTG mai conţine şi partea cu care se descriu algoritmii aplicaţiilor.

Întrebări şi exerciţii la capitolul 3.Exerciţiul 1.Ce este modelul reţea?Exerciţiul 2. Daţi un exemplu de transformare a unei reţele complexe în diagramă utilizabilă în modelul reţea.

CAPITOLUL 4 MODELUL IERARHIC.Modelul ierarhic a fost dezvoltat primul în ordine istorică şi, deşi se

bazează pe teoria grafurilor, nu are un standard ca şi modelele relaţional sau reţea. SGBD-ul de referinţă pentru modelul ierarhic este IMS (Information Management System) dezvoltat de IBM şi North American Association (mai târziu Rockwell) începând din anii 1960 în legătură cu proiectul APOLLO.

Ceea ce se transcrie în stuctura externă modelul ierarhic este o arboresceţă grafică, un graf orientat, conex fără cicluri. Alte proprietăţi ale acestui tip de graf ar fi: - există un singur vârf, numit rădăcină, în care nu este incident nici un arc - exista varfuri, numite frunze, din care nu pleacă nici un arc; - orice varf, dacă nu este frunză, poate avea mai mulţi descendenţi (direcţi), vârfuri la care se poate ajunge parcurgând un singur arc - orice varf, în afară de rădăcină, are un părinte unic (vârful al cărui descendent este).

24

Rezultă din aceste definiţii că o schemă, ca cea din următorul exemplu, care nu pune nici o problemă pentru transformare în model reţea, trebuie transformată pentru modelul ierarhic.

De la schema conceptuală se transformă, pentru modelul ierarhic, în schema următoare:

Pentru că, în prima imagine, o persoană ar putea avea doi părinţi, unul ca apartenenţă la o secţie şi altul ca apartenenţă a persoanei la un lot de pensionare la o anumită dată.

Putem deduce de aici câteva principii: - Modelul ierarhic transpune scheme E-R de tipul 1 : n, în particular

1 :1. - A doua apariţie a unei entităţi poate fi numai o referinţă la prima

apariţie. Deşi noţiunile folosite în legătură cu modelul ierarhic diferă puţin de cele de la modelul reţea, există totuşi multe asemănări.

- Există, în legatură cu modelul ierarhic, două noţiuni de bază: părinte şi relaţie părinte-copil (PCR). Segmentul este analogul lui record din structura reţea, iar PCR este analog cu set din modelul reţea cu

25

diferenţa, care de altfel decurge din regulile de mai sus, că un segment poate fi descendentul unui singur părinte.

Să vedem, în continuare, cum se transformă alte tipuri de scheme conceptuale pentru a fi descrise cu modelul ierarhic:

Fig.4.1

Figura 4.1 Este un exemplu de arbore cu trei nivele, reprezentând entităţile SECTIE, PERSONAL, FUNCTIE, PROIECT ca segmente.

Apariţiile înregistrărilor corespunzătoare segmentelor unui arbore pot fi realizate în memorie folosind metoda de parcurgere în preordine.

Să luăm, de exemplu, o instanţă pentru schema din figura de mai sus:

26

Parcurgerea în preordine (algoritmul se gaseşte în capitolul arbori binari) se referă la posibila transformare a acestui arbore oarecare în arbore binar, în care cei doi fii ai unui vârf vor fi: primul descendent şi primul frate. Putem însă enunţa preordinea şi pentru arbori oarecare (această parcurgere mai poate fi găsită şi sub numele de parcurgere în adâncime). 1. Se începe din rădăcina arborelui şi se înregistrează rădăcina 2. La fiecare vârf, după ce s-a înregistrat segmentul respectiv, se înregistrează segmentul celui mai din stânga descendent al segmentului care a fost înregistrat. Dacă nu mai există descendenţi ne întoarcem cu un nivel mai sus şi înregistrăm cel mai din stânga descendent neînregistrat încă; procedeul se continuă până se epuizează segmentele arborelui. Această procedură, pentru graful următor, dă secvenţa de înregistrări din fig.4.2

fig.4.2

Iteraţie Segment Tip de segment1 A S 2 B P 3 E F 4 F PR 5 G PR 6 C P 7 H F 8 I PR9 D P

27

10 J F 11 K PR

Deoarece modelul ierarhic nu are standard vom prezenta , în continuare, limbajul IMS de descriere al datelor (DDL) pentru figura 4.1. 1 DBD NAME = SECTPERS, ACCESS = HISAM 2 SEGM NAME = SECTIE, PARENT = 0, BYTES = 20 3 FIELD NAME = (SECNUME,SEQ,U), BYTES = 10, START = 1, TYPE = C 4 FIELD NAME = MANAGER, BYTES = 10, START = 11, TYPE = C 5 SEGM NAME = PERSONAL, PARENT = SECTIE, BYTES = 22 6 FIELD NAME = (PERSNUME,SEQ), BYTES = 20, START = 1, TYPE = C 7 FIELD NAME = VECHIME, BYTES = 2, START = 21, TYPE = P 8 SEGM NAME = FUNCTIE, PARENT = PERSONAL, BYTES = 17 $ 9 FIELD NAME = (CODFUNCTIE,SEQ), BYTES = 2, START = 1, TYPE = P 10 FIELD NAME = NUMEFUNCTIE, BYTES = 15, START = 3, TYPE = C 11 SEGM NAME = PROIECT, PARENT = PERSONAL, BYTES = 4 12 FIELD NAME = (NUMEPROIECT,SEQ), BYTES = 2, START = 1, TYPE = P 13 FIELD NAME = DIVIZIE, BYTES = 2, START = 5, TYPE = C 14 DBGEN

Segmentele (SEGM) sunt simbolurile din limbaj ale nodurilor grafului, PARENT = 0 înseamnă că nodul SECTIE este rădăcina grafului, BYTES stabileşte lugimea segmentului, NAME = ( SECNUME, SEQ, U) înseamnă că o nouă memorare trebuie făcută ţinâd cont de valoarea câmpului din segment, iar U înseamnă că SECNUME trebuie să fie unic, START semnifică numărul locaţiei de început al câmpului în segment, TYPE = P şi TYPE = C reprezintă tipuri de date decimal împachetat respectiv caracter. Metode de acces:

IMS furnizează patru metode de acces : HSAM, ISAM, HDAM si HIDAM. Alegerea unei astfel de metode se face cu ACCESS = < metoda de acces aleasă >. Vom prezenata sumar aceste patru metode: - HSAM

HSAM înseamnă “hierarchic sequential acces method”.Este metoda de acces secvenţială la baza de date ierarhică. Segrnentele sunt memorate fizic în poziţii alăturate şi poate fi implementată pe disc sau bandă. Segmentele sunt

28

ordonate conform schemei de parcurgere în preordine care păstrează structura ierarhică. Această metodă este utilă numai pentru citirea datelor adică nu este destul de flexibilă pentru actualizările bazelor de date. - HISAM

HISAM înseamnă“hierarchic indexed-sequential acces method”. Este metoda de acces indexat-secvenţial la baza de date ierarhică care memorează segmentele ca şi în metoda HSAM dar dă posibilitatea accesului direct la un anumit segment rădăcină cu ajutorul indexului, după care accesul la segmentele dependente se face secvenţial ca şi în metoda HSAM. - HDAM

HDAM înseamnă “hierarchic direct- acces method”. Este metoda de acces direct la baza de date ierarhică. Această metodă nu leagă segmentele prin index sau apropiere fizică ci prin pointere adică câmpuri care conţin adrese pe disc. Accesul la o anumită rădăcină se face folosind algoritmi de repartizare. (vezi cap.10) - HIDAM

HIDAM înseamnă “hierarchic indexed direct- acces method”. Este o metodă de acces direct indexat care înseamnă acelaşi lucru ca şi HDAM dar permite accesul indexat la o anumită rădăcină ca şi accesul prin pointere la segmentele dependente. Întrebări şi exerciţii la capitolul 4.Exerciţiul 1.Cu ce diferă modelul ierarhic de modelul reţea?CAPITOLUL 5 MODELUL RELAŢIONAL .

Sistemele de gestiune ale bazelor de date relaţionale (notate pe scurt SGBDR) au devenit principalul soft în prelucrarea datelor folosite astăzi. Acest soft reprezintă a doua generaţie a SGBD-urilor şi este bazat pe modelul relaţional introdus de E.F.Codd în 1970. În modelul relaţional toate datele Sunt logic structurate prin relaţii (tabele).

Fiecare relaţie are un nume căruia îi corespunde o coloană de tabel (atribut). Fiecare tuplu (linie de tabelă) conţine o valoare a fiecărui atribut. Un mare avantaj al modelului relaţional este această structură logică simplă. 2.1. Scurf istoric al modelului relaţional.

Modelul relaţional a fost propus pentru prima dată de catre E.F.Codd în seminarul “Modelul relaţional al datelor pentru partajarea marilor date bancare“ în 1970. Un alt model asamblist a fost propus de catre Childs, în 1968, care a subliniat faptul că orice structură de date poate fi prezentată prin una sau mai multe tabele de date, în cadrul cărora este necesar să existe şi informaţii de legătură, pentru asigurarea legăturilor între tabele. Codd, însă,

29

are meritul de a fi accentuat şi dezvoltat ideile cu privire la utilizarea teoriei mulţimilor sub forma unui model coerent de structurare a datelor, şi anume modelul relaţional.

Sistemele comerciale bazate pe modelul relaţional au început să apară în ultimii ani ai perioadei 1970. Acum sunt mai mult de 100 de SGBDR, chiar dacă multe nu respectă întocmai definiţia modelului relaţional. Datorită popularităţii modelului relaţional, multe dintre sistemele non-relaţionale furnizează interfaţa relaţională. 2.2. Modelul relaţional al datelor. 1. Structura relaţională a datelor. În cadrul bazelor de date relaţionale, datele sunt organizate sub forma unor tablouri bidimensionale (tabele) de date, numite relaţii. Asocierile dintre relaţii se reprezintă explicit prin atributele de legătură. Aceste atribute figurează într-una din relaţiile implicate în asociere.

Selecţia este operaţia care creează dintr-o relaţie-operand o relaţie-rezultat cu aceeaşi schemă, dar în care sunt incluse numai tuplele pentru care predicatul de selecţie este adevărat.

Proiecţia este operaţia care creează dintr-o relaţie-operand o relaţie-rezultat care are acelaşi număr de tuple dar are numai o parte din atribute. De exemplu

nume,oras(student) va avea tuplele:

30

Produsul cartezian a doua relaţii-operanzi are ca rezultat o relaţie-rezultat cu atributele formate din reuniunea celor două mulţimi de atribute ale operanzilor şi ca tuple, pentru fiecare tuplu din prima relaţie toate tuplele din a doua relaţie (deci ca număr produsul numerelor tuplelor celor doua relaţii-operanzi). Deci dacă avem schema catalog=(nr_mat,materia,note) cu avea tupele:

nr_mat Materia note22 Matematica 1022 Engleza 9102 Matematica 8102 Engleza 91330 Matematica 5

Atunci produsul cartezian student X catalog va avea tuplele:

Student.nr_mat nume oraş Catalog.nr_mat materia note22 Avram

IonBraşov 22 matematica 10

22 Avram Ion

Braşov 22 engleza 9

22 Avram Ion

Braşov 102 matematica 8

22 Avram Ion


22 Avram Ion


102 Condru Marin

Craiova 22 matematica 10

102 Condru Marin

Craiova 22 engleza 9

102 Condru Marin


102 Condru Marin


102 Condru Marin


1330 Pop Nelu


1330 Pop Braşov 22 engleza 9

31

Nelu1330 Pop

NeluBraşov 102 matematica 8

1330 Pop Nelu


1330 Pop Nelu


Această tabelă este greu de înţeles la ce ar fi bună. De ce să-l legăm pe un anumit student de toate notele?

Avem însă şi alte operaţii mai utile. Echijoncţiunea face de fapt o selecţie după un predicat în produsul cartezian. Dacă vom lua

Student Jstudent.nr_mat=catalog.nr_mat catalog =

student.nr_mat=catalog.nr_mat(student X catalog)vom obţine tabela:

Student.nr_mat nume oraş Catalog.nr_mat materia note22 Avram

IonBraşov 22 matematica 10

22 Avram Ion


102 Condru Marin


102 Condru Marin


1330 Pop Nelu


Se observă că de data aceasta operaţia leagă fiecare student de nota lui în mod natural. De ce să mai avem atunci de două ori atributul Nr_mat?

Join-ul natural a două relaţii are un efect similar cu echijoncţiunea, pe atribute care în cele două relaţii-operanzi au acelaşi nume şi în relaţia rezultat atributele respective apar o singură dată. De exemplu:

Student JN catalog

Va avea tuplele:

32

Reuniunea se poate aplica numai la două relaţii care au aceeaşi schemă şi are ca rezultat relaţie cu schema iniţială şi cu tuplele din ambele relaţii operanzi.

Intersecţia se poate aplica numai la două relaţii care au aceeaşi schemă şi are ca rezultat o relaţie cu schema iniţială şi cu tuplele - numai tuplele comune celor două relaţii inţiale.

Diferenţa se poate aplica numai la două relaţii care au aceeaşi schemă şi are ca rezultat o relaţie cu schema iniţială şi cu tuplele care sunt în prima relaţie dar nu şi în a doua relaţie. Exemplele se pot da uşor de către cititor devreme ce noţiunile sunt analoage cu binecunoscutele noţiuni omonime din teoria mulţimilor.

Restricţiile de integritate ale modelului relaţional permit definirea stărilor coerente ale bazei de date. 2.3. Structura relaţională a datelor.

Modelul relaţional este bazat pe conceptul matematic de “ relaţie “ care este fizic reprezentată de o tabelă. Cunoscutul matematician Codd foloseşte termionologia matematică din teoria mulţimilor şi logica predicatelor în definirea modelului relaţional.

Prezentarea structurii relaţionale a datelor impune definirea noţiunilor de: relaţie, atribut, domeniu şi schemă a unei relaţii. Trebuie adaugat aici că orice tabelă are urmatoarele proprietăţi: - nu există rânduri duplicate, - nu există nume de coloane duplicate- ordinea rândurilor nu este importantă - ordinea coloanelor nu este importantă - valorile atributelor sunt atomice ( nedecompozabile). - o relaţie este o tabela cu linii şi coloane.

33

În modelul relaţional, relaţiile sunt folosite pentru a păstra informaţii despre obiectele care sunt reprezentate în bază. Relaţia este reprezentată printr-un tablou bidimensional, în care liniile reprezintă înregistrările individuale (tuplele), iar coloanele reprezintă atributele.

Un SGBDR necesită ca baza de date sa fie percepută de către utilizatori doar sub forma unei tabele.

Atributul unei relaţii este o coloană a relaţiei, caracterizată printr-un nume. Numele coloanei exprimă semnificaţia valorilor din cadrul coloanei respective.

Domeniul este un set de valori permise pentru unul sau mai multe atribute. Acest concept are o mare greutate în modelul relaţional. Fiecare atribut are asociat un domeniu. Domeniile pot fi distincte pentru fiecare domeniu în parte, sau pot exista două sau mai multe atribute definite pe acelaşi domeniu. Totodată, acest concept are o mare importanţă deoarece permite utilizatorului să definească într-o poziţie centrală semnificaţia şi sursa valorilor pe care atributul le poate lua.

O importanţă aparte în cadrul relaţiei o are semnificaţia valorilor. Semnificaţia valorilor din cadrul unui tuplu se stabileşte atât pe baza domeniilor cărora aparţin valorile, cât şi în funcţie de poziţia ocupată în cadrul tuplului. Dependenţa faţă de ordinea valorilor în tuplu ar înseamna o reducere a flexibiliăţii organizării datelor.

Pentru a diferenţia coloanele care conţin valori ale aceluiaşi domeniu şi a elimina astfel dependenţa de poziţia din cadrul tabelei se asociază fiecărei coloane un nume distinct, ceea ce duce la apariţia noţiunii de atribut.

Tot din punct de vedere al semnificaţiei valorilor, putem spune că relaţia reprezintă un subansamblu al produsului cartezian de mai multe domenii, subansamblu caracterizat printr-un nume şi care conţine tupluri cu semnificaţie.

În cadrul modelului relaţional nu interesează decât relaţiile finite, chiar dacă la construirea relaţiilor se admit domenii infinite. Numărul valorilor dintr-un tuplu poartă numele de grad al relaţiei. Gradul unei relaţii este parte a intensiei unei relaţii.

Cardinalul unei relaţii este numărul tuplurilor conţinute în respectiva relaţie. Prin contrast faţă de gradul relaţiei, numărul tuplurilor este numit

34

cardinalul relaţiei, iar schimbarea cardinalului unei relaţii se face prin ştergerea sau adăugarea de tupluri.

Cardinalul este o proprietate a extensiei ( intensia şi extensia vor fi definite puţin mai jos, în cadrul schemei unei relaţii). Structura unei relaţii, împreună cu o specificare a domeniilor pentru valori formează schema unei relaţii. Schema unei relaţii este adesea cunoscută şi sub denumirea de intensie a relaţiei, ca expresie a proprietăţilor comune şi invariante ale tuplurilor care compun relaţia. Întrebări şi exerciţii la capitolul 5.Exerciţiul . Se dau relaţiile cu schema:Carte=(id_carte,titlu,c_edit,c_domeniu)Domenii=(c_domeniu,d_domeniu)Edituri=(c_edit,d_edit,oras, str, nr)Autor=(c_aut,nume_aut)Carteaut=(id_carte,c_aut)Să se exprime înalgebra relaţională cererile:

1. Titlurile cărţilor din domeniul ‘stiinta’2. Editurile din ‘brasov’3. Cărţile scrise de ‘Ion Ion’4. Cărţile scrise numai de ‘Ion Ion’ (ca singur autor)

CAPITOLUL 6 ARBORI BINARI.

În acest capitol vom învăţa: Ce sunt arborii binari Cum se memorează ei Cum se parcurg arborii binari Cum se transformă un arbore oarecare în arbore

binar Ce este un nomenclator

Un arbore în care orice vârf are zero, unul sau doi descendenţi se numeşte arbore binar. Un arbore binar care are numai vârfuri cu nici un descendent sau cu doi descendenţi se numeşte arbore strict binar. (Un astfel de arbore de foloseşte, de

35

exemplu, la reprezentarea în memorie a unei expresii aritmetice.) Exemplu: expresia (a+b)*c - 2/c^3.5 unde (x^y înseamnă ‘ x la puterea y’) - se va reprezenta astfel :

fig. 6.1

Frunzele acestui arbore ( nodurile fără descendenţi) conţin operanzii, iar celelalte noduri conţin operaţiile. Deoarece nu toate operaţiile sunt comutative este foarte important dacă un nod este descendent pe stânga sau pe dreapta. Rădăcina unui arbore este nodul care nu este descendentul nici unui nod.

Alocarea unui arbore binar se poate face: secvenţial, înlănţuit sau mixt.

1) Alocarea secvenţială a unui arbore binar În vectorul (x(I))I=l,n) vom avea următoarele reguli: - rădăcina este în x(1) - pentru fiecare nod x(I) descendentul din stânga este x(2*I) iar cel din dreapta este x(2 *I+1) - dacă nu există descendent se pune ‘*’.

Reprezentarea secvenţială a arborelui din fig. 1 este :

Observaţie : x(20), ... , x(27) sunt poziţii din vector neutilizate.Vom folosi această alocare în capitolul destinat cozilor de prioritate pentru a construi o structură asemănătoare denumită HEAP. Exemple de parcurgeri: 1- parcurgerea arborelui din fig.6.1 în preordine -,*,+,a,b,c,2,/,^,c,3.5 aceasta scriere se nmeşte scriere poloneză prefixata pentru o expresie aritmetică. 2- parcurgerea arborelui din fig. 1 în inordine a,+,b,*,c,-,2,/,c,^,3.5

36

aceasta este scrierea obişnuită a expresiilor matematice (operaţiile sunt scrise în ordinea efectuării lor). 3- parcurgerea arborelui din fig. 1 în postordine a,b,+,c, *,2,c, ^,3.5,/,- aceasta scriere se numeşte scriere poloneză postfixată a unei expresii aritmetice.

PREORD_IT(RAD) STIVA = {Stiva este vidă} P=RAD {P conţine nodul care se viziteză} Repetă

RepetăDacă P ’ * ‘ atunci{Parcurgere pe stânga}

Scrie INFO(P); P=>STIVA P=LS(P) Ciclează

altfelEXIT

Sdacasciclu{Parcurgere pe dreapta} Dacă STIVA = atunci EXIT

Altfel P<=STIVA ; P= LD(P)

Sdaca Sciclu Return

Algoritmul se poate modifica uşor pentru INORDINE_IT, dar pentru POSTORDINE_IT este nevoie de două stive. Exerciţiul 1.Scrieţi algoritmul pentru inordine iterativ.

37

Exerciţiul 2.Scrieţi algoritmul pentru postordine iterativ.

Un exemplu des folosit este structura unui produs format din ansamble, subansamble şi aşa mai departe până la piese simple. Această structură dă naştere unui arbore oarecare cum ar fi cel din figura 6.2.

38

Fig.6.2Există o metodă de a construi un arbore asociat care, de această dată,

este binar. Transformarea se face în felul următor : pentru fiecare nod descendentul din dreapta este fratele următor (elementul următor aflat la acelaş nivel de descompunere). Astfel arborele din fig.6.2 dă naştere unui

arbore binar ca cel din fig.6.3.

39

Fig 6.3.Parcurgerea în preordine a acestui arbore binar asociat dă aceeaşi ordine

a nodurilor ca şi parcurgerea în adâncime a arborelui oarecare iniţial (fapt pentru care se spune câte odată ordine de parcurgere în preordine pentru arborele oarecare). Lista parcurgerii în preordine în acest caz concret este nomenclatorul de produse şi este o listă reprezentativă care intră în reclama

produsului. Ea arată în felul următor: Diagrama E-R conceptuală pentru nomenclatorul de produse arată în prima instanţă aşa: Repere = (CodRep, Denum,. . .) Stuctura = (CodRep,CodRep,Cant) De exemplu, pentru arborele de mai sus, se obţin instanţele:

40

Repere Structura

Structura Întrebări şi exerciţii la capitolul 6.Exerciţiile 1 şi 2 sunt în text referitoare la parcurgerea arborilor binari în inordine şi postordine nerecursiv.Exerciţiul 3.Se dă A,B,C,D,E,F,G,H parcurgerea în preordine a unui arbore binar şiB,A,E,D,C,F,H,G parcurgerea în inordine a aceluiaşi arbore. Să se deseneze arborele.Exerciţiul 4.Să se scrie algoritmul pentru exerciţiul 3.

CAPITOLUL7 COZI DE PRIORITATE (cu HEAP).

41

HEAP -ul este o structură de date care memorează un arbore binar complet într-un vector. Fiecare nod al arborelui corespunde unui element al vectorului unde se memorează valoarea din nod. Arborele este echilibrat, adică numai ultimul nivel este eventual incomplet.

Un vector A care reprezintă un Heap este caracterizat de două atribute: n=lung(A) care este numărul elementelor memorate în vector şi Heap- C lung(A) care este numărul de elemente ale Heap-ului din vectorul A. Deci Heap-Iung(A)~lung(A). Rădăcina arborelui este întotdeauna A(l) si dându-se un indice i al unui nod, indicii părintelui Par(i) , fii din stânga LS(i) şi din dreapta LD(i) pot fi calculaţi conform algoritmilor :

Functie Par(i) ... Par = Li/2J Return

Functie LS(i) LS = 2*i Return

Functie LD(i) LD = 2*i + 1 Return

Pe cele mai multe computere funcţia LS poate calcula 2*i printr-o singură instrucţiune deplasând către stânga peste o poziţie binară reprezentarea binara a lui i. Similar, funcţia LD poate calcula rapid 2*i + 1 prin deplasare către stânga peste o poziţie binară reprezentarea lui i şi modificând în 1 cel mai din dreapta bit. Funcţia Par poate calcula i/2 printr-o singură instrucţiune deplasând către dreapta peste o poziţie binară reprezentarea binară a lui i.

Reprezentarea unui arbore binar într-un vector oarecare .

42

Acest arbore este un arbore binar echilibrat şi are adâncimea h = log2n. O structură căreia i se poate pune în corespondenţă un arbore echilibrat se numeşte HeapMax dacă orice nod are o valoare mai mare decât oricare din fii săi. (Dacă orice nod are o valoare mai mică decât oricare dintre fii săi atunci structura se numeşte HeapMin ).

Algoritmul de heapificare a unui vector cu n componente începând de la a i-a componentă este:

HEAPIFY(A ,i) L = 2*i R = 2*i + 1 Daca L <= Heap-lung(A) şi A(L) > A(i) atunci

Imax = L Altfel

Imax = i SdacaDaca R <= heap-lung(A) şi A(R) > A(imax) atunci

43

Imax=RSdaca Daca Imax I atunci

A(i) A(imax)Sdaca

Cheama HEAPIFY(A, Imax)return

Algoritmul pentru construcţia unui heap este următorul: CHEAP(A ,n) Heap-lung(A) = npentru i =n/2,1,-1

cheama HEAPIFY (A ,i) Spentru

Fişierul al cărui arbore ataşat este:

se hipifică în felul următor:Pentru I=5

44

4

1

i

i

45

3

2 79

100000

4 8 6

4

31

8 79 1

000004 2 6

i

i

46

4

10

1

8 79 3

0

4 2 6

4

10

8

4 79 3

0

1 2 6

Heap-ul după terminarea algoritmului va arăta astfel :

Se poate observa că timpul de execuţie al lui Heapify depinde de înălţimea nodului în arbore. În heap avem pentru orice înălţime h avem [n/2h+1] noduri de înălţime h. Cunoscând aceasta putem calcula timpul de execuţie.

T(n)= [n/2h+1]*O(h) = O(n* [h/2h+1])= O(n) h=0,lg(n) h=0,lg(n)

Algoritmul Heapify este de complexitate O(n). Structura de Heap este foarte utilă: am văzut în cursul de ‘Algoritmică’

că HeapSort-ul este un excelent algoritm de sortare. În continuare vom prezenta cea mai utilizată aplicaţie a unui Heap şi anume coada de priorităţi.

Coada de priorităţi este o structură de date care păstreaza elementele unei mulţimi S în care fiecărui element îi este asociată o valoare numită prioritate. 7.1 Operaţii asupra unei cozi de priorităţi: 1) Introducera unui element x în S Insert(S,x) 2) Determinarea elementului cu cea mai mare cheie Maxim(S) :

47

10

9 8

4 74 3

0

1 2 6

3) Extragerea elementului cu cea mai mare cheie Extract_Max(S) Una dintre aplicaţiile cozii de priorităţi este gestionarea proceselor în

programarea partajată. Coada de priorităţi păstrează lista proceselor care trebuie să fie efectuate şi priorităţile acestora. Când un proces s-a încheiat sau s-a întrerupt se introduce un nou proces, alegerea acestuia se face în funcţie de prioritatea ataşată. Deci se va folosi Extract_Max(S) pentru alegerea procesului cu cea mai mare şi Insert(S ,x) pentru a-l introduce în lucru. O coadă de priorităţi poate fi folosită şi în simularea conducerii evenimentelor.

În continuare vom prezenta algoritmii care implementează cu ajutorul Heap-ului operaţiile care se pot efectua asupra unei cozi.

Extract_Max(A,max) Daca Heap-lung(A) < 1 atunci

EROARE “ heap vid” Sdacamax = A(l) A(l) = A(Heap-lung(A) )Heap-lung(A) = Heap-lung(A) - 1 Cheama Heapify(A,l) Return

Evident că, deoarece heapul s-a stricat doar la vârf, Heapify(A,l) va parcurge doar o singură dată arborele de la rădăcină la o frunză, deci complexitatea va fi O(lg n).

Insert(A,cheie) Heap-lung(A) = Heap-lung(A) + 1 i= Heap-lung(A) Atât timp cât i> 1 şi A(Par(i)) < cheie

A(i) = A(Par(i)) i= Par(i) A(i) = cheie

Sciclu

Si această procedură va parcurge doar o singură dată arborele de la rădăcină la o frunză, deci complexitatea va fi O(lg n).

Figura următoare ilustrează operaţia Insert asupra heap-ului a) în care urmează să fie inserat un nod cu cheia 15.

48

10

a)

49

9 8

4 74 3

0

1 2 6 15

10

9 8

4 15

4 3 0

1 2 6 7

10

9 15

Cheia 15 a fost iserată la locul ei.

Puteţi observa, pe succesiunea de arbori, că s-a creat mai întâi locul şi apoi, ‘15’ a trecut la locul corect urcând în sus în arbore, din părinte în părinte.

Întrebări şi exerciţii la capitolul 7.Exerciţiul 1.Arătaţi cum se poate implementa o stivă cu ajutorul unui HEAP.Exerciţiul 2.Arătaţi cum se poate implementa o coadă cu ajutorul unui HEAP.Exerciţiul 3.Având un arbore binar memorat secvenţial scrieţi algoritmul care listează nodurile fără descendent stâng.

CAPITOLUL 8 ARBORI BINARI DE CĂUTARE .

50

4 84 3

0

1 2 6 7

150

9 10

4 84 3

0

1 2 6 7

În acest capitol vom învăţa: Ce sunt arborii binari de căutare Ce operaţii se fac cu acşti arbori Care este complexitatea acestor algoritmi

Arborii de căutare sunt structuri de date care suportă foarte multe operaţii cum ar fi : SEARCH (cautare), MINIMUM, MAXIMUM, PREDECESOR, SUCCESOR, INSERT (introducere) şi DELETE (ştergere). Un arbore de căutare poate fi folosit atât ca dicţionar cât şi ca o coadă de priorităţi.

Operatţiile de bază pe un arbore binar de căutare au timpul proporţional cu înălţimea arborelui. Pentru un arbore binar complet aceste operaţii se execută în cel mai rău caz în O(lg n). Dacă arborele este o înlănţuire liniară de n noduri atunci aceleaşi operaţii se vor face în cel mai rău caz în O(n).

În practică nu putem garanta întotdeauna randomizarea construirii arborilor de căutare, dar sunt anumiţi arbori binari de căutare (arborii roşu-negru, arborii balansaţi) ale căror performanţe sunt bune pentru operaţiile de bază, chiar şi în cel mai rău caz. 8.1.Ce este un arbore binar de cautare?

Un arbore binar de căutare este organizat, după cum ne sugerază şi numele, ca un arbore binar cum vedem în figura 8.1

fig.8.1Acesta este un arbore binar de căutare cu 6 noduri şi înălţime 2.

Un asemenea arbore poate fi reprezentat de o structură de date înlănţuită în care fiecare nod este un obiect. Într-un nod x avem |KEY | ADR | LS | LD | P | KEY(x) însemnă valoarea cheii din nodul x, informaţia de lângă KEY se mai numeşte şi informaţie satelit (SAT), legătura la copilul din stânga, legătura la copilul din dreapta, şi părintele nodului x. Dacă un copil sau un

51

părinte lipsesc, câmpul corespunzator va conţine NIL. Fie un arbore care conţine aceleaşi chei cu cel din fig.8.l dar cu înălţimea 4 şi mai puţin eficient a cărui reprezentare o găsiţi în figura 8.2. Definiţie Un arbore binar de căutare este un arbore binar care satisface condiţia:

fig.8.2.a) Pentru orice nod y care se află într-un subarbore stâng al nodului x

KEY(y) ~ KEY(x) b) Pentru orice nod y care se află într-un subarbore drept al nodului x

KEY(x) ~ KEY(y) Aceasta proprietate a unui arbore binar de căutare ne permite să

extragem toate cheile sortate cu ajutorul unui simplu algoritm recursiv printr-o parcurgere în inordine.

INORD_PARC (x) Daca LS(x) NIL atunci

Cheama INORD_P ARC(LS(x))Scrie KEY (x) Cheama INORD_P ARC(LD(x))

Sdaca

8.2.Operaţii asupra unui arbore binar de căutare. Cea mai comună operaţie efectuată asupra unui arbore binar de căutare

este căutarea unei chei memorată în arbore careia îi vom spune căutare binară. Aceasta structură mai suportă şi interogări de tipul “care este Minimum-

ul, Maximum-ul, Succesor-ul, Predecesor-ul?”.

52

În continuare vom examina aceste operaţii şi vom vedea că fiecare se poate face într-un timp proporţional cu înălţimea arborelui, deci O(h).

În figura 8.3 vom exemplifica care este calea de căutare a cheii 13.

Fig.8.3. Căutarea cheii 13 trebuie făcută pe partea stângă a rădăcinii - 15, unde găsim cheia 6, deci căutarea trebuie continuată pe partea dreaptă, unde găsim cheia 7, vom continua căutarea pe partea dreaptă şi găsim cheia 13. Calea acestei căutari este: 15-6-7-13.

Vom folosi următorul algoritm pentru a căuta într-un arbore binar de căutare un nod cu cheie dată:

CAUT_BIN(Rad, k, Rez) x=Rad Atat timp cat x Nil şi k KEY(x)

Daca k <KEY(x) atuncix = LS(x) altfelx = LD(x)

Sdaca Sciclu Daca x = Nil atunci Rez =Nil

altfelRez =ADR(x)

Sdaca return

53

MINIMUM şi MAXIMUM. Un element al unui arbore binar de căutare, a carui cheie este minimă,

poate fi găsit urmărind pointerele descendenţilor din partea stângă începând de la rădăcină până când este întâlnită o adresă = Nil.

Următorul algoritm determină nodul de cheie minimă a unui arbore cu rădăcina Rad:

MIN_BIN (Rad, Min) x = Rad Atat timp cat LS(x) Nil x = LS(x) Min=KEY(x) Return

Exerciţiul 1.Algoritmul pentru determinarea nodului cu cheia maximă este simetric

cu cel de mai sus şi vă propunem să-l scrieţi aici:

SUCCESOR şi PREDECESOR Fiind dat un nod într-un arbore binar de căutare, câteodată este

important să-i găsim succesorul în şirul sortat al cheilor obţinut prin parcurgerea în inordine. Dacă toate cheile sunt distincte succesorul unui nod x este nodul cu cea mai mică cheie, mai mare decât KEY(x). Structura arborilor binari de căutare ne permite să determinăm succesorul unui nod fără a compara vreodată cheile.

Următorul algoritm determină succesorul nodului x dacă acesta există şi returnază Nil dacă x este cea mai mare cheie din arbore: SUCC_BIN(x, y) Daca LD(X) Nil atunci

Cheama MIN_BIN(LD(x), y) Return

sdacay =P(x) Atat timp cat y Nil şi KEY(y)<KEY(x)

x=y y = P(y)

sat

54

Return

Algoritmul pentru succesor este rupt în doua cazuri: - Dacă sub arborele drept al nodului x nu este gol, atunci succesorul lui x este cel mai din stânga nod al subarborelui drept, pe care îl găsim chemând MIN_BIN. Dacă subarborele drept al nodului x este gol şi x are un succesor y, atunci y este cel mai mic stramoş al lui x şi copilul stâng al lui y este deasemenea un stramoş al lui x. Exerciţiul 2.

Algoritmul pentru determinarea predecesorului este simetric cu cel de mai sus şi îl lăsăm ca exerciţiu pentru cititor.

INSERAREA şi ŞERGEREA Operaţiile de inserare şi ştergere aplicate unei mulţimi dinamice

reprezentate de un arbore binar de căutare cauzează schimbari în arbore. Structura de date trebuie modificată ca să reflecte aceste schimbări, dar proprietăţile arborelui binar de căutare trebuie să fie în continuare păstrate. Modificarea arborelui pentru inserarea unui unui element este relativ directă, în schimb la ştergere este ceva mai complicat. INSERAREA

Pentru inserarea unei noi valori într-un arbore binar de căutare T vom folosi algoritmul INS_BIN. Aceasta procedura este exemplificată în figura 9.4:

În aceasta figură nodurile umbrite marchează calea de la rădăcină până la poziţia în care se face inserarea. Linia punctată indică legătura în arbore care este adăugată pentru inserarea elementului. (cheia elementului care se insereaza este 13).

55

fig.5. 4 INS_BIN(x ,y) y = Nil x = Rad LS(z) = LD(z)=Nil Atata timp cat x Nil

y=x Daca KEY(z)<KEY(x) atunci

x = LS(x) altfel

x = LD(x) sdaca

Sciclu P(z)=y Daca y = Nil atunci

Rad = z altfel

Daca KE Y ( z) < KE Y (y) atunci LS(y) = z

altfelLD(y) = z

Sdaca Sdaca Return

56

ŞTERGEREA. Algoritmul pentru ştergerea unui nod dat - z dintr-un arbore binar de

căutare are ca argument un pointer către z. Procedura consideră trei cazuri ilustrate în figura 8.5:

Dacă z nu are copil modificăm părintele lui z înlocuindu-l pe z cu Nil.

Dacă z are un singur copil îl eliminăm pe z făcând o nouă legătură între copilul şi părintele lui z.

Daca z are doi copii îl eliminăm pe z prin înlocuirea conţinutului său cu cel al succesorului său care nu are copil stâng.

Fig. 8.5 a ) când z nu are copil: b ) când z are un singur copil:

57

c ) când z are doi copii

ELIMIN_BIN (T ,z) Daca LS(z)=Nil sau LD(z)=Nil atunci

y=z altfel

cheama SUCC_BIN(z ,y) sdacaDaca LS(y) Nil atunci

x =LS(y) altfel

x=LD(y) sdaca Daca x Nil atunci

58

P(x) = P(y) sdacaDaca P(y) = Nil atunci

Rad = x altfel

Daca y=LS(P(y)) atunci LS(P(y)) = x altfel LD(P(y)) = x

Sdaca sdacaDaca KE Y ( z) < KE Y (y) atunci

KEY(z) = KEY(y) ADR(z) = ADR(y)

Sdaca Return

Întrebări şi exerciţii la capitolul 8.Exerciţiile 1 şi 2 se găsesc în text.Exerciţiul 3.Scrieţi algoritmul de căutare binară recursiv.

CAPITULUL 9 HASH – TABLES.

În acest caitol vom învăţa: Ce este şi cum se foloseşte o tabelă cu adresare directă Ce este şi cum se foloseşte o tabelă de repartzare Ce operaţii se fac într-o tabelă de repartizare Ce este o funcţie derepartizare şi cum se poate defini Cum se poate rezolva problema coliziunilor Ce este o tabelă cu repartizare deschisă Ce este o tabelă cu repartizare închisă

59

Cum se poate face testarea

Foarte multe aplicaţii au nevoie de o mulţime dinamică în care sunt permise operaţiile Insert, Search (căutare), Delete (ştergere ). De exemplu, un compilator pentru un limbaj foloseşte o tabelă de simboluri în care cheile sunt şiruri de caractere arbitrare care corespund identificatorilor limbajului.

Vom folosi în continuare pentru Hash-Table denumirea de “Tabela de repartizare”. O tabelă de repartizare este o structură de date eficientă pentru implementarea dicţionarelor. De asemenea căutarea într-o tabela de repartizare se poate face, în cel mai rău caz, cu un timp egal cu cel necesar căutarii într-o listă înlănţuită adică O(n), practic însă metoda repartizării funcţionează foarte bine. Cu presupuneri rezonabile, complexitatea căutarii unui element într-o tabelă de repartizare este O(1).

O tabelă de repartizare este generalizarea, pentru memoria auxiliară, a noţiunii de vector. Când numărul cheilor memorate este mic raportat la numărul total posibil de chei, tabelele de repartizare devin o altemativă eficientă la memorarea directă într-un vector, deoarece o tabelă de repartizare foloseşte un spaţiu de mărime proporţională cu numărul cheilor memorate. În loc de a folosi cheia ca indice în vector, indicele este calculat în funcţie de cheie. 9.1. Tabele cu adresare directă.

Adresarea directă este o tehnică simplă care lucrează bine atunci când universul U al cheilor este destul de mic. Presupunem că o aplicaţie are nevoie de o mulţime dinamică în care fiecare element are o cheie care face parte din universul cheilor U={ 0, 1, ... ,m-l}, unde m nu este prea mare şi de asemenea nu avem două elemente cu aceeaşi cheie.

În figura 9.1 este descrisă implementarea unei mulţimi dinamice printr-o tabelă cu adresare directă. Fiecare cheie din universul U = {O ,1 ,... ,9 } corespunde unui index din tabela T. Mulţimea cheilor actuale K ={2 ,3 ,5 ,8}

60

determină în tabelă o celulă care va conţine pointere către element, celelalte celule (umbrite) conţin Nil. Pentru a reprezenta o mulţime dinamică vom folosi un vector sau o tabelă cu adresare directă T[O..m-l] fiecărei celule k din tabelă corespunzându-i un element din mulţime având cheia k sau NIL dacă în mulţime nu s-a găsit un element cu cheia egală cu numărul celulei.

Fig. 9.1Operaţiile asupra tabelei cu adresare directă sunt implementate de

următorii algoritmi care sunt foarte rapizi având o complexitate O(1):

SEARCH(T , k ,lor) lor = T(k) Return

INSERT(T ,x) T(cheie(x)) = x Return

DELETE(T ,x) T(cheie(x)) = NIL Return

Pentru unele aplicaţii, elementele unei mulţimi dinamice pot fi memorate chiar în tabela cu adresare directă. 9.2. Tabele de repartizare .(hash-tables).

Este evident că prin adresare directă apar dificultăţi dacă universul U este mare, memorarea unei tabele T (de dimensiune |K|) devenind ineficientă sau chiar imposibilă. Dacă mulţimea cheilor actuale K este foarte mică în raport cu U atunci cea mai mare parte a spaţiului alocat pentru T se va irosi.

Atunci când mulţimea cheilor actuale K memorată într-un dicţionar este cu mult mai mică decât universul U o tabelă de repartizare necesită mult mai puţină memorie decât o tabelă cu adresare directă. Şi anume, cerinţele de memorie pot fi reduse la O(|K|) , chiar dacă căutarea unui element într-o tabelă de repartizare se va face tot într-un timp O(|K|). (Atragem atenţia ca acestea se referă la timpul mediu, pe când pentru adresarea directă este timpul pentru cel mai rău caz).

Cu adresarea directă, memorarea unui element cu cheia k, se făcea în celula k. Prin repartizare acest element va fi memorat în celula h(k) unde h este o funcţie care va calcula celula în care va fi memorat elementul cu cheia k - vom numi aceasta funcţie hash funcţie sau funcţie de repartizare.

61

De acum h va pune în corespondenţă fiecărui element având cheia din U o singură celulă din tabela de repartizare T[O ,... ,m-l] deci:

h : V ~ {O ,1 ,... ,m-l}. Vom spune că un element cu cheia k este repartizat celulei h(k) şi că

h(k) este valoarea de repartizare a cheii k. În următoarea figură va fi ilustrată ideea de bază. Fie h(k) = k mod 10.

Atunci: h(3) = 3 , h(12) = 2 , h(15) = 5 , h(17) = 7

fig.9.2Scopul funcţiei de repartizare h, este de a reduce rangul indicilor

vectorului ajutător. Observăm că, indiferent de cardinalul mulţimii U, avem nevoie doar de cel mult |K| valori, deci cerinţele pentru memorare sunt mult reduse.

Dacă, în figura 9.2, K ar conţine cheia 25 funcţia de repartizare i-ar pune în corespondenţă celula 5 ( h(15) = 5 şi h(25) = 5 ). Vom numi două chei k1 şi k2 sinonime daca h(k1) = h(k2), iar repartizarea aceleiaşi celule, pentru chei distincte, coliziune.

Cum vom rezolva problema coliziunii? Soluţia ideală ar fi să evităm coliziunile alegând o funcţie de repartizare convenabilă de exemplu : a) h(k) = k mod n ,unde n sa fie un număr prim nu foarte apropiat de o putere a lui 2 b) h(k) = [m*(k*A) mod I] ,unde A este o aproximare a lui (5-1) şi N mod 1 = N – [N]. Aceasta funcţie a fost propusă de Knuth în “Tratat de programare a calculatoarelor”.

62

c) crearea unui portofoliu de funcţii de repartizare, alegerea uneia dintre ele fiind aleatoare (această metodă este cunoscută sub numele de funcţie universală de repartizare)

Cu toate acestea, toate soluţiile propuse mai sus nu fac altceva decât să micşoreze numărul de coliziuni deci avem nevoie de o metodă care să rezolve coliziunile care pot avea loc. Vom prezenta în figura 9.3 cea mai simplă metodă de rezolvare a coliziunilor numită înlănţuire.

Fig9.3Se observă ca fiecare celulă a tabelei de repartizare conţine o listă

înlănţuită a tuturor cheilor a căror valoare de repartizare este egală cu j. De exemplu h(k1) = h(k4) = 1 sau h(k3) = h(k7) = h(k8) = 5.

Operaţiile asupra unei tabele de repartizare în care coliziunile au fost rezolvate prin înlănţuire sunt implementate cu următorii algoritmi:

Repart_Inlant_Insert(T, x) Insereaza x in capul listei T(h(cheie(x))) Return

Repart_Inlant_Search(T, k) Caută un element cu cheia k în lista T(h(k)) Return

Repart_Inlant_Delete(T, x) Şterge elementul x din lista T(h(cheie(x))) Return

63

Listele care se crează sunt de fapt stive. Cititorii sunt rugaţi, pentru întelegerea acestor algoritmi, sa consulte capitolul 1.

În cel mai rău caz, algoritmul pentru inserţie are o complexitate de O(1). Pentru căutare, în cel mai rău caz, complexitatea algoritmului este proporţinală cu lungimea listei. Pentru ştergere, complexitatea este O(1) dacă lista este dublu înlanţuită. Dacă lista este simplu înlănţuită, atunci va avea aceeaşi complexitate cu algoritmul de căutare.

Analiza repartizarii prin înlănţuire. Ne punem întrebarea cât durează căutarea unui element de cheie dată în

cazul repartizarii prin înlănţuire? Fiind dată o tabelă T cu m celule care memorează n elemente vom

defini factorul de încărcare- al tabelei T ca fiind raportul =n / m adică numărul mediu de elemente memorate în lanţ. Analiza se va face în funcţie de imaginându-ne că el este fixat iar n şi m tind către infinit. (Obs. poate fi < , > sau = 1)

Performanţa medie a repartizării prin înlănţuire depinde de cât de bine distribuie funcţia h celule setului de chei pentru a fi memorate. Putem presupune că în fiecare celulă elementele au fost egal distribuite (adica o repartizare simplu uniformă). Teorema.

Într-o tabelă de repartizare, în care coliziunile au fost rezolvate prin înlănţuire, iar repartizarea este simplu uniformă, compexitatea căutarii este în medie dată de (1+).

Dacă numărul celulelor din tabela de repartizare este cel puţin proporţional cu numărul de elemente din tabelă, vom avea n = O(m) şi în consecinţă = n/m = O( m)/m = 1, aşadar căutarea în medie se face într-un timp constant.

În subcapitolul 9.4 se va introduce o metodă altemativă de rezolvare a coliziunilor numită adresare deschisă. 9.3. Funcţii de repartizare (hash funcţii).

În acest subcapitol ne vom ocupa de câteva chestiuni care se referă la proiectarea unei funcţii de repartizare bune. Vom prezenta trei scheme pentru construirea lor: prin împărţire, prin înmulţire şi universală.

Cele mai multe funcţii de repartizare presupun că universul cheilor este format din numere naturale. Dacă acestea nu sunt naturale trebuie să găsim o cale de a le interpreta ca pe nişte numere naturale. De exemplu dacă o cheie

64

este un şir de caractere ea poate fi interpretată ca o expresie întreagă apelând la reprezentarea binară a caracterelor. În continuare vom presupune că universul cheilor este format din numere naturale. Metoda impărţirii.

Această metodă construieşte o funcţie de repartizare care memorează elementul având cheia k într-una din celulele tabelei T[0,..., m-l] având numărul egal cu restul împărţirii lui k la m.

h(m) =k mod m exemplu: Dacă tabela T are m=12, iar cheia k=90, atunci h(k) = 6. Medoda inmulţirii.

Această metodă determină funcţia de repartizare în doi paşi: mai întâi înmulteşte cheia k cu o constantă A (0<A<1) şi reţine partea fracţionară a acestei înmulţiri, apoi înmulţeşte această valoare cu m şi reţine doar partea întreagă a rezultatului.

h(k) = [m*(k*A) mod 1] Avantajul acestei metode este că valoarea lui m nu este critică. De

obicei se alege pentru un întreg m astfel încât 2 - m =2P putând implementa funcţia pe orice tip de calculator.

În fig 9.4 este reprezentată metoda înmulţirii pentru construirea unei funcţii de repartizare. Reprezentarea w de biţi (w lungimea reprezentarii binare a unui cuvânt) a cheii k (presupunem că k încape într-un singur cuvânt) este înmulţită cu valoarea k [A*2w], unde 0<A<l este o constantă convenabilă. Rezultatul este o valoare pe 2w biţi r1*2W+ro uncle r1 este cuvântul de rang maxim al rezultatului iar, r0 cuvântul de rang minim. Valoarea de repartizare, din p biţi, constă din bitul cel mai semnificativ al lui r0.

65

Fig.9.4Această metodă funcţionează cu orice valoare a constantei A dar,

funcţionează mai bine cu anumite valori decât cu altele. Alegerea optimă pentru această constantă depinde de caracteristicile datelor ce urmează a fi repartizate. Knuth sugerează alegerea lui A ca fiind ( 5-1) 0,6180339887. . . care funcţionează foarte bine. De exemplu pentru cheia k=123456 şi m=10000 obţinem h(k)=[10000*(123456*0,61803...) mod 1] = 41. Metoda universală.

Dacă se caută nod în papură se pot alege cheile în aşa fel încât toate să fie repartizate în aceeaşi celulă a tabelei de repartizare ceea ce ar duce la un timp mediu (n).

Orice funcţie de repartizare fixă din cele prezentate mai sus este vulnerabilă în cazul alegerii “răutăcioase” a cheilor adică va genera multe chei sinonime.

Singura cale de a îmbunătăţi această situaţie este alegerea aleatoare a unei funcţii de repartizare într-un mod care să nu depindă de cheile care urmează a fi memorate. Această metodă se numeşte repartizarea universală metoda are performanţe bune indiferent de cheile alese de cei rău intenţionaţi .

Ideea, care stă la baza repartizării universale, este alegerea aleatoare a unei funcţii de repartizare, în momentul execuţiei, dintr-un portofoliu de funcţii de repartizare construite cu grijă la început. Randomizarea, la fel ca şi în cazul sortării rapide, garantează că nici o intrare nu va cauza un comportament rău. Datorită randomizării algoritmul se va comporta diferit la fiecare execuţie chiar şi pentru aceleaşi date de intrare.

Fie H o colecţie (portofoliu) de funcţii de repartizare care memorează cheile din universul U într-o tabela T[O,... ,m-l]. H se va numi universală dacă pentru fiecare pereche de chei distincte k1,k2U numărul de funcţii de repartizare hH pentru care h(k1) = h(k2) este egal exact cu |H|/m. Cu alte cuvinte probabilitatea unei coliziuni, în acest caz, este de 1/m.

Teorema. Daca h este aleasă din H şi este folosită pentru repartizarea a n chei într-

o tabelă de repartizare de mărime m, unde n m, numărul posibil de coliziuni în care este implicată o cheie x, este mai mic decât 1.

Să vedem cum se poate crea un astfel de portofoliu. Să alegem mărimea tabelei de repartizare m – prim. Descompunem cheia x în r + 1 byţi deci x = (xo,…,xr) singura restricţie fiind că valoarea maximă a unui byt să fie mai mică decât m.

66

Fie a = (a0,... ,ar ) o secvenţă de elemente aleasă la întâmplare din mulţimea {0,..., m - 1}. Definim funcţia de repartizare corespunzatoare ha H ca fiind

r

ha(x) = ai* xi mod m (1) i=0

Cu această definiţie obţinem

H=U{ha} (2) a

care va avea mr+1 elemente. Teorema.

Multimea H definită de ecuaţiile (1) şi (2) mulţime universală de funcţii de repartizare.

9.4.Adresarea deschisă. În acest caz toate elementele unei mulţimi dinamice sunt memorate în

tabela de repartizare (fiecare celulă va conţine un element al mulţimii dinamice sau NIL). Pentru a căuta un element în tabela de repartizare vom examina sistematic celulele tabelei până când vom găsi elementul dorit sau până când va fi clar că acesta nu se găseşte în tabelă. Această metodă nu utilizează liste, nu sunt elemente memorate în afara tabelei (spaţii de depăşire) aşa cum folosea metoda înlănţuirii. Deci, în adresarea deshisă, tabela de repartizare se poate “umple” ceea ce înseamnă că nu se vor mai putea face inserări de noi elemente, altfel spus factorul de încărcare nu poate fi mai mare decât 1.

Avantajul adresării deschise constă în faptul că evită cu totul pointerele. De fapt, în loc să căutam pointere, vom “calcula” o secvenţă de celule care urmează a fi examinată. Memoria rămasă liberă prin nememorarea pointerelor face ca tabela de repartizare să aibă un număr mare de celule pentru aceaşi cantitate de memorie, şansele de coliziune să fie mici iar regăsirea elementelor să fie rapidă.

Pentru a executa inserarea, folosind adresarea deshisă, examinăm succesiv tabela de repartizare până când vom găsi o celulă liberă în care se va pune cheia. În loc să fie fixat în ordinea 0, 1, ..., m-1 (care înseamnă o complexitate de cautare (n) şirul poziţiilor testate depinde de cheia care a fost inserată. Pentru a determina celula de examinat extindem funcţia de repartizare pentru a include numărul testării (începând de la 0) ca o a doua intrare. Astfel funcţia de repartizare devine

67

h: U x {0,1,... ,m-1} {0,1,... ,m-1}. Cu adresare deschisă, avem nevoie pentru fiecare cheie k ,ca şirul de

testare {h(k,0), h(k,I) ,h(k,2),…,h(k,m-1)} să fie o permutare a lui {0,1,... ,m-1} astfel încât fiecare poziţie din tabela de repartizare este eventual considerată ca o celulă pentru o nouă cheie pe măsură ce tabela se umple.

În următorul algoritm, presupunem că elementele în tabela de repartizare T sunt chei fără informaţie satelit; cheia k este identică cu elementul care conţine cheia k. Fiecare celulă conţine deci fie o cheie fie NIL (dacă celula este goală).

REPART _Insert(T, k,j) i=O repeta

j = h(k, i) Daca T (j) = NIL atunci

T(j) = k return i=i+l

sdaca pana cand i=m sau T(j)=NILj=NILEROARE “tabela plină” return

Algoritmul de căutare pentru cheia k testează celulele în aceeaşi ordine în care algoritmul de inserare le-a examinat când a fost inserată cheia k. De aceea căutarea se poate termina (fără succes) când găseşte o celulă goală deoarece k ar fi fost inserat acolo şi nu mai departe în şirul lui de testări. (bineînţeles că nu vom mai permite ştergerea cheilor din tabela de repartizare.)

Procedura REPART_Search are ca intrare o tabelă de repartizare T şi o cheie k, şi ca ieşire j dacă celula j a fost găsită cu cheia k sau NIL dacă cheia k nu este prezentă în tabela T.

REPART_Search(T, k,rez)i=0 repeta

j = h(k, i) daca T (j) = k atunci

rez = j

68

return sdacai=i+l

pana cand T(j)=NIL sau i =m rez =NIL return

Ştergerea dintr-o tabelă de repartizare cu adresare deschisă este dificilă. Nu avem dreptul să punem în locul unei chei care a fost ştearsă valoarea NIL pentru că ar face imposibilă găsirea oricarei chei la inserţia căreia celula respectivă a fost gasită ocupată. Soluţia acestei probleme poate fi găsită introducând un nou câmp în înregistrare care să conţină, în cazul ştergerii, un marcaj pentru ştergere. În acestă situaţie procedurile de căutare şi de inserţie se vor modifica corespunzător.

În analiza noastră facem presupunerea de repartizare uniformă: adică orice cheie considerată are şanse egale de a avea ca secvenţă de testare oricare din cele m! permutări ale mulţimii {0,... ,m-l} .

Repartizarea uniformă generalizează noţiunea de repartizare simplu uniformă definită mai înainte pentru situaţia în care funcţia de repartizare dă, nu un singur număr ci o întreagă secvenţă de testări.

Se folosesc, mai des, următorele trei tehnici pentru a “calcula” şirul de testări necesar pentru adresare deschisă. Toate aceste tehnici garantează că

{h(k,0), h(k,l) ,h(k,2) ,…,h(k,m)} este permutare a lui {0,... ,m-l} pentru fiecare cheie k. Niciuna din aceste tehnici nu îndeplineşte presupunerea de repartizare uniformă deoarece niciuna din acestea nu este capabilă de a genera mai mult decat m2 şiruri de testări diferite (în loc de m! câte cere repartizarea uniformă). Dubla repartizare are cel mai mare număr de şiruri de testare deci pare să dea cele mai bune rezultate. Testarea liniară.

Fiind dată o funcţie de repartizare oarecare h’:U{0,... ,m-1}, metoda testării liniare foloseşte funcţia de repartizare de forma:

h(k ,i) = (h’(k) + i) mod m pentru i = 0, 1,... ,m-1. Pentru o cheie dată k, prima celulă testată este T(h’(k)). Următoarea celulă testată va fi T(h’(k) + 1) şi aşa mai departe până la celula T(m-1). Vom testa celulele T(0) ,T(1), ... , până când, în sfârşit, vom testa celula T(h’(k) – 1). Deoarece în testarea liniară testarea poziţiei iniţiale determină întreg şirul de testări, vom folosi doar m şiruri distincte de testări. Testarea pătratică.

69

Testarea pătratică foloseşte o funcţie de repartizare de forma h(k ,i) = (h’(k) + c1*i +c2*i2) mod m

unde h’ este o funcţie de repartizare auxiliară, c1, c2 sunt constante auxiliare şi i=0,1,... , m-1. Poziţia iniţială testată este T(h’(k)); poziţiile testate ulterior sunt decalate prin cantităţi care depind într-un mod pătratic de a i-a testare. Această metodă funcţionează mult mai bine decât testarea liniară dar, pentru a folosi complet tabela de indexare valorile lui c1, c2 şi m sunt restricţionate. Dubla repartizare.

Dubla repartizare este una din cele mai bune metode în cazul adresării deschise pentru că permutările care se produc au multe caracteristici ale permutărilor alese aleator. Funcţia de repartizare folosită este de forma: h(k ,i) = (h1(k) + i *h2(k)) mod m, unde h1, h2 sunt funcţii de repartizare auxiliare. Prima poziţie testată este T(hl(k)); poziţiile testate ulterior sunt decalate de la poziţia anterioară prin cantitatea h2(k) mod m. Astfel, spre deosebire de cazurile testării liniare şi pătratice, aici şirul de testare depinde în două feluri de cheia k deoarece poziţia iniţială de testare, decalarea, sau amândouă pot varia.

Fig 9.5 dă un exemplu de inserţie cu dublă repartizare. Avem o tabelă de repartizare de mărime 13 şi funcţiile de repartizare hl(k) = k mod 13, h2(k) = 1 + (k mod 11). Cum 14=1 mod 13 va fi testată celula T(1), dar ea este ocupată. 14=3 mod 11 deci următoarea celulă testată va fi T(5) care este şi ea ocupată, celula care urmează a fi testată este T(9) care este liberă şi cheia 14

va fi inserată. fig. 10.5.

70

Analiza repartizării prin adresare deschisă. La fel ca la analiza repartizării prin înlănţuire şi această analiză se va

face în funcţie de factorul de încărcare al tabelei de repartizare. Reamintim că dacă n elemente sunt memorate într-o tabelă de mărime m atunci =n/m. Cum la adresarea deschisă n m rezultă că factorul de încarcare 1.

Presupunem că este folosită repartizarea uniformă. În această schemă idealizată şirul de testare {h(k,0) , h(k,1) ,h(k,2),…,h(k,m)} pentru fiecare k este echiprobabil de a fi orice permutare a lui {0,1,... ,m-1}. Asta înseamnă că orice şir posibil de testare este echiprobabil să fie utilizat ca şir de testare pentru o inserţie sau o căutare. Desigur o anumită cheie dată are un anumit şir de testare asociat unic şi fix; asta înseamnă că, considerând distribuţia de probabilitate pe spaţiul cheilor şi operaţia de funcţie de repartizare a unei chei, orice şir de testare are aceeaşi probabilitate.

Următoarele teoreme vor stabili numărul de testări preconizate pentru repartizarea cu adresarea deschisă. Teorema.

Fiind dată o tabelă de repartizare cu adresare deschisă cu factorul de încărcare =n/m < 1 numărul preconizat de testări într-o căutare fără succes este cel mult 1/(1-), presupunând repartizarea uniformă.

Această teoremă ne dă imediat performanţa inserţiei prin următorul: Corolar

lnserţia unui element într-o tabelă de repartizare cu adresare deschisă are nevoie de cel mult 1/(1-) testări în medie, presupunând repartizarea uniformă.

Formula pentru numărul preconizat de testări pentru o căutare cu succes

este dată de următoarea : Teoremă.

Fiind dată o tabelă de repartizare cu adresare deschisă cu factorul de încarcare <1 numărul preconizat de testări într-o căutare cu succes este cel mult

(1/)*ln(1/(1-))presupunând repartizarea uniformă.

Întrebări şi exerciţii la capitolul 9.Exerciţiul 1.

71

Se consideră o tabelă de reprtizare de dimensiune m=1000 şi funcţia de repartizare h(k)=[m*(k*A mod 1)] pentru A=(5-1)/2calculaţi locaţiile în care se pun cheile: 61, 62, 63, 64, 65. Exerciţiul 2.Se consideră că se inserează cheile 10, 22, 31, 4, 15, 28, 17, 88, 59 într-o tabelă de repartizare de lungime m=11 folosind adresarea deschisă cu funcţia de repartizare h(k)=k mod m. Ilustraţi rezultatul inserării cu verificare liniară, cu verificare patratică unde c1=1 şi c2=3 şi folsind dubla repartizare cu h2(k)=1+(k mod(m-1)).Exerciţiul 3.Scrieţi algoritmul pentru ştergerea din tabela de repartizare cu adresare deschisă şi modificaţi corespunzător algoritmii REPART_INSERT şi REPART_SEARCH.

10. ARBORI BALANSAŢI (B-Trees) .

În acest capitol : Vom afla ce sunt arborii balansaţi Vom calcula înălţimea arborilor balansaţi Vom descrie operaţiile cu arbori balansaţi

Arborii balansaţi sunt arbori de căutare destinaţi să lucreze eficient pe discuri magnetice; ei sunt realizaţi urmărind aceleaşi idei şi scopuri ca şi arborii roşu-negrii dar sunt superiori acestora în minimizarea timpului pentru intrare-ieşire .

Diferenţa esenţială este că, în arborii balansaţi, un nod poate avea mai mulţi descendenţi (până la sute). Asemănarea este că înălţimea arborelui este O(log n) deşi baza logaritmului (mult mai mare) dă o înălţime corespunzator mai mică. Aceasta este important pentru că operaţiile asupra arborelui, cum ar fi căutarea, inserarea şi ştergerea au complexităţi proporţionale cu înălţimea arborelui.

Se vede din figura 10.1 cum arborii balansaţi generalizează arborii binari de căutare.

72

Fig.10.Cheile sunt consoane. Un nod conţine n(x) chei şi are n(x) + 1

descendenţi. Toate frunzele au aceeaşi adancime. Nodurile albe marcheză drumul pentru căutarea literei R. 10.1 Structura datelor în memoria pe disc.

Avem la dispoziţie multe tehnologii de memorare a datelor. Memoria principală este realizată pe cipuri de siliciu. Această memorie a crescut şi s-a ieftinit de-a lungul timpului, totuşi ea rămâne mai mică şi mai scumpă decât memoria pe medii magnetice deşi mult mai rapidă.

Timpul unor operaţii pe calculator ce includ citiri şi scrieri pe disc depind de:

- numarul de accese la disc - timpul de lucru al procesorului. Folosim arbori balansaţi în aplicaţii în care datele nu pot intra în

memoria Principală. Algoritmii conţinuţi în acest capitol copiază anumite pagini de memorie de pe disc în memoria principală şi, pe cele care s-au modificat, le rescrie (înapoi pe disc). Modelul, din acest punct de vedere, este următorul:

Fie x un pointer către un obiect. Dacă obiectul se află în memoria principală, ne vom referi la câmpuri ca de obicei (ex.KEY(x)). Dacă obiectul se află pe disc, vom face mai întâi o operaţie de citire CIT_DISK(x) a obiectului x şi apoi ne putem referi la câmpurile lui. Dacă s-au efectuat modificări ale câmpurilor lui x ele vor fi actualizate pe disc prin scriere SCR_DISK(x).

73

fig. 10.2.

Figura 10.2 conţine un exemplu de arbore balansat care are mai mult de un miliard de chei.

Ca să micşorăm numărul de accese la disc trebuie să mărim dimensiunea nodului. În general un nod va fi memorat pe o pagină întreagă. Aceasta înseamnă un factor de ramificare între 50 şi 2000. 10.2. Definiţia arborilor balansaţi.

Vom considera, ca şi mai înainte, că “informaţia satelit” asociată cu o cheie este memorată în acelaşi nod cu cheia şi este “mutată” odată cu mutarea cheii.

Un arbore balansat (echilibrat) T este un arbore cu rădăcina Rad(T) cu următoarele proprietăţi :

1.Fiecare nod are următoarele câmpuri: a) n( x) numarul de chei de stocate în x b) cele n( x) chei memorate în ordine crescătoare KEY1(x),KEY2(x),...,KEYn(x)(x). c)F(x) cu valoare adevarat daca x este frunză şi fals dacă x nu

este frunză d) Dacă x este nod intern (Frunza(x) este fals) atunci x mai

conţine n(x)+ 1 pointeri Cl(X),C2(X) ,... ,Cn(x)+l(X) la copiii (descendenţii) lui x

2.Cheile din x separă cheile din descendenţi adică dacă kj este o cheie oarecare din descendentul de la adresa Cj( x) cu j{1,2,...,n( x)+ 1} atunci k1KEY1(x)k2KEY2(X) ... KEY n(x)(x)kn(x)+l

3.Fiecare frunză are aceeaşi “adâncime” care este înălţimea arborelui. 4.Există un număr maxim şi un număr minim de chei pe care le poate conţine un nod care sunt în legătură cu t 2 numit gradul minim al lui T.

74

a)Fiecare nod, în afară de rădăcină, are cel puţin t-1 chei şi deci, dacă este intern, are cel puţin t descendenţi. Dacă arborele este nevid, rădăcina trebuie să aibă cel puţin o cheie .

b)Fiecare nod poate conţine cel mult 2t-1 chei (un nod intern are cel mult 2t descendenţi). Spunem ca un nod este plin, dacă are exact 2t-1 chei. Cel mai simplu arbore balansat este cu t = 2 unde fiecare nod poate avea

2, 3 sau 4 descendenţi. Înălţimea unui arbore balansat. Teorema

Dacă n1 este numărul de chei dintr-un arbore balansat cu înălţimea h şi gradul minim t 2 atunci h logt ((n+1)/2).Demonstraţie.

O să pornim în demonstraţie de la un arbore cu număr maxim de chei ca în exemplul următor.

Figl0.3Dacă arborele are înălţimea h, atunci numărul de noduri este minim

când rădăcina conţine o cheie şi celelalte noduri conţin t-1 chei. În acest caz sunt 2 noduri la primul nivel, 2t la al doilea nivel, şi aşa mai departe până la nivelul h unde sunt 2th-1.

n 1+ (t - 1)2t-1 =1 + 2(t-1)((th-1)/(t-1))= 2th - 1 i=1,h

10.3 Operaţii în arbori balansaţi. Pentru următorii algoritmi vom presupune că rădăcina arborelui este în

memoria principală, deci nu avem CIT_DISK pentru ea, dar este nevoie de

75

SCR_DISK dacă avem actualizări ale câmpurilor rădăcinii. Mai presupnem că orice alt nod are nevoie să fie citit ca să avem acces la câmpurile lui. Căutarea în arborii balansaţi.

Algoritmul este recursiv şi se apelează prima dată cu B_TREE_CAUT(Rad(T), k ,rez), unde k este cheia cautată, rez conţine rezultatul căutării adică perechea (y,i) care înseamnă că nodul y are a i-a cheie KEY(y)=k sau rez=Nil dacă cheia nu este în arbore.

B- TREE- CAUT( x,k,rez) i=l atât timp cat i<n(x) şi k> KEYi(x)

i=i+l Sciclu Daca in(x) şi k = KEYi(x) atunci

rez = (x, i) return

sdacaDaca Frunza(x) atunci

rez = Nil Return

altfel Cheama CIT_DISK(ci(x)) Cheama B_TREE_CAUT(ci(x), k, rez) return

sdaca

b.Construcţia unui arbore balansat. Pentru aceasta vom creea mai întâi un arbore vid şi vom insera pe rând

în el noile chei. Avem nevoie mereu de locuri libere pe disc pe care le fumizează ALOC_NOD().

B_TREE_CRE(T) x = ALOC_NOD( ) Frunza(x) = True n(x) = 0 SCR_DISK(x) Rad(T) = x Return

76

Dacă un nod este plin, ca să putem insera în continuare, el trebuie rupt în două, ca în figura 10.4:

Fig.l0.4Nodul plin are 2t - 1 chei şi cheia din mijloc (indice t) se duce în

părinte, presupus neplin. Dacă se face ruperea rădăcinii atunci arborele creşte în înălţime cu 1.

Procedura B_TREE_RUP are ca intrare un nod intern neplin - x (aflat deja în memoria principală), un index - i şi 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)

77

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 balansaţi. Putem să construim acum inserarea care începe cu cazul în care

rădăcina este plină exemplificat în figura 10.5.

Fig.10.5Cheia k trebuie inserată î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

78

cheama B- TREE_INS_NEPLIN (r,k) SdacaReturn

Procedura B_TREE_INS_NEPLIN parcurge arborele în jos până la locul unde trebuie făcută inserarea. B- TREE_INS_NEPLIN(x, k) i = n(x) Daca Frunza(x) atunci atata timp cat i 1 şi 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 şi k<KEYi(x)

i=i-1 sciclui=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

sdacaCheama B_TREE_INS_NEPLIN(ci(x), k) return

Exemple de inserări Mai multe cazuri sunt reprezentate în figura 10.6.:

79

(a) arborele iniţial

(b) este inserat B ( c ) este inserat Q

(d) este inserat L

( e) este inserat F Fig.10.6.

Ştergerea unei chei dintr-un arbore balansat. Aceasta este o operaţie similară cu inserarea, dar ceva mai complicată.

B_TREE_STERG(x, k) şterge din subarborele T începând în nodul x, cheia k. Grija este ca numărul de chei din nodurile parcurse (altul decât rădăcină) să fie t (gradul minim), adică cu 1 mai mult decât de obicei ca să putem şterge o cheie. Aşa că, uneori, o anumită cheie trebuie să coboare într-un nod descendent înainte de a-l parcurge. Dacă în acest mod rădăcina x rămâne fără chei atunci singurul descendent ci(x) va fi noua rădăcină şi x dispare, micşorând astfel înalţimea arborelui cu 1.

Figura 10.7. ilustrează diversele situaţii care se pot întâlni la ştergere.

80

(a) arborele iniţial

(b ) ştergerea lui F: cazul 1

(c) ştergerea lui M: cazul2a

(d) ştergerea lui G: cazul 2c

(e) ştergerea lui D: cazul 3b

81

(e’) arborele scade în înălţime

(e) ştergerea lui B : cazul 3a Contrar obiceiului dăm aici numai câteva idei ale algoritmului de

ştergere: 1.Dacă cheia k este în nodul x şi x este frunză atunci se şterge pur şi

simplu k din cheile lui x. 2.Daca cheia k este în nodul x (intern) atunci :

a.Dacă descendentul y, care precede k în x (k=KEYi(x)), y=ci(x)) are cel puţin t chei atunci se găseşte k’ care precede pe k şi se înlocuieşte k cu k’ în x (ştergând k’ din y) b.Dacă z este descendentul care urmează pe k se procedează simetric cu cazul a. c.În alt caz (deci când şi y şi z au t-1 chei adică numărul minim) şterge k din x şi adresa ci+1(x) (către z) iar cheile k şi cele din z se introduc împreună cu pointerii în y continuând ştergerea recursiv cu B_TREE_STERG(y, k).

3.Dacă k nu este în nodul intern se determină ci(x) rădăcina unui subarbore care

trebuie să-l conţină pe k. Dacă ci(X) are numai t-l chei se execută 3.a. sau 3.b. apoi se reia recursiv pasul 3.

a.Daca ci(x) are numai t-l chei, dar are un frate alăturat (ci(x) sau c+1(x) care au t chei atunci ci(x) primeşte o nouă cheie coborâtă din x, urmând să se completeze numărul de chei cu cheia potrivită din fratele care avea t chei. b.Dacă ci(x) şi toţi fraţii lui alăturaţi (ci-1(x) sau ci+1(x)) au numai t-1 chei se unifică ci(x) cu unul dintre fraţii alăturaţi coborând o cheie din x ca cheie mediană în noul nod. (Acţiunea este exact inversa ruperilor şi determină eliminarea ei şi crearea unei noi

82

rădăcini, aceasta însemnând micşorarea înălţimii arborelui cu o unitate.

Întrebări şi exerciţii la capitolul 10.Exerciţiul 1.Construiţi un arbore balansat cu t=3 şi înălţime =3.Exerciţiul 2.Ilustraţi, pe arborele de mai sus, inserarea şi ştergerea unui nod.

11.ARBORI ROŞU-NEGRI. În capitolul 10 am arătat că operaţiile de căutare, predecesor, succesor,

minimum, maximum, inserarea, şi ştergerea pentru un arbore binar de căutare cu înălţimea h se fac în O(h). Deci aceste operaţii se execută rapid dacă înălţimea este mică; dar, dacă înălţimea este mare, performanţele lor nu pot fi mai bune decât ale unei lisle înlănţuite.

Arborii roşu-negri sunt una din multele scheme de arbori de căutare care sunt “echilibraţi” cu scopul de a garanta ca operaţiile dinamice să aibă complexitatea O(lg n). 11.1.Proprietăţle arborilor roşu-negri.

Un arbore roşu-negru este un arbore binar care conţine căte o informaţie în plus pentru fiecare nod aceasta fiind culoarea care poate fi roşu sau negru. Arborii roşu-negrii ne asigură că nu există o cale cu lungimea de două ori mai mare decât orice altă cale, deci aceşti arbori sunt aproximativ echilibraţi.

Fiecare nod al arborelui roşu-negru conţine următoarele câmpuri: - culoarea (CuI) - cheia (KEY) - legătura din stânga (LS) - legătura din dreapta (LD) - părintele (P) Un arbore binar de căutare este arbore roşu-negru dacă îndeplineşte

următoarele proprietăţi: 1.Fiecare nod este roşu sau negru 2.Fiecare frunză Nil este neagră 3.Dacă un nod este roşu, atunci ambii descendenţi sunt negri

83

4.Pe orice cale între un nod şi o frunză descendentă se află acelaşi număr de noduri negre. Un exemplu de arbore roşu-negru avem în figura 11.1 unde nodurile roşii sunt cele umbrite.

fig.11.1.

Lema

Un arbore roşu-negru cu n noduri interne are înălţimea cel mult 2*log(n+ 1).

Consecinţă Operaţiile dinamice căutare, minimum, maximum, succesolr,

predecesor pot fi implementate pentru arborii roşu-negri în O(lg n).

84

11.2.Rotaţii. Operaţiile de căutare şi ştergere aplicate unui arbore roşu-negru cu n

chei modifică arborele, ceea ce ar putea duce la distrugerea proprietăţilor pe care trebuie să le aibă un arbore roşu-negru. Pentru a restaura aceste proprietăţi va trebui sa schimbăm culoarea anumitor noduri şi, deasemenea, să schimbăm structura pointer. Schimbăm structura pointer printr-o rotaţie, care este o operaţie locală într-un arbore de căutare care conservă disciplina cheilor.

In figura 11.2 sunt expuse două tipuri de rotaţii: rotaţie_stânga şi rotaţie_dreapta.

fig. 11.2. Când facem o rotaţie stânga presupunem că LD(y)Nil. Rotatia_stânga

“pivotează” în jurul legăturii dintre x şi y, făcându-l pe y noua rădăcina a subarborelui având pe x ca şi copil stâng, iar copilul stng al lui y va fi copilul drept al lui x. (,,, sunt subarbori arbitrari). Algoritmul pentru rotaţie_stânga.

Rotaţie_stânga(T ,x) y=LD(x) LD(x)=LS(y) Daca LS(y) Nil atunci

P(LS(y))=x sdacaP(y)=P(x) Daca P(x)=Nil atunci

Rad(T)=y altfel

Daca x = LS(P(x)) atunci LS(P(x))=y

altfelLD(P(x))=y

sdaca

85

LS(y)=x P(x)=y Return Exerciţiul 1.Algoritmul Rotaţie_dreapta este similar. Este momentul să vedeţi dacă l-aţi înţeles pe cel dinainte şi să scrieţi algoritmul pentru Rotaţie_dreapta.

86

Ambii algoritmi au complexitatea O(1). În figura 11.3 se vede cum funcţionează Rotaţie_stânga:

Fig.11.3

.

fig.11.3.b11.3.Inserarea.

Vom folosi algoritmul INS_BIN din capitolul 9. Pentru a insera un nod x în arborele T ca şi cum ar fi un arbore binar de căutare oarecare apoi îl vom colora roşu. Pentru a garanta că proprietăţile roşu-negru sunt păstrate vom ‘repara’ modificările apărute în arbore prin recolorarea nodurilor şi folosirea rotaţiilor. În mare parte algoritmul se ocupă de diferitele cazuri care pot apărea pentru a ‘repara’ modificările apărute în arbore.

RN_INSERT(T ,x) Cheama INS_BIN(T ,x) Cul(x)=roşu Atat timp cat xRad(T) şi cul(P(x))=roşu daca P(x) = LS(P(P(x)) atunci

y= LD(P(P(x)) daca Cul(y)=roşu atunci

Cul(P(x))=negru Cul(y)=negru Cul(P(P(x))=roşu x=P(P(x))

altfeldaca x=LD(P(x)) atunci

x=P(x)

87

cheama Rotaţie_stânga(T,x) sdaca

Cul(P(x))=negru Cul(P(P(x)) = ro:u Cheama Rotaţie_dreapta( T ,P(P(x))

Sdaca (aceleaşi instrucţiuni ca pe ramura de dreaptă unde LD şi LS au fost schimbate) Cul(Rad(T))=negrureturn

Care dintre proprietăţile roşu-negru sunt încălcate după primele două linii ale algoritmului? Proprietatea 1 se păstrează cu siguranţă, la fel şi cea de-a doua din moment ce noul nod introdus este roşu şi copilul sau este Nil. Proprietatea 4 este satisfacută pentru că nodul x înlocuieşte un nod negru - Nil şi acest nod x este roşu cu copil Nil. Deci singura proprietate care poate fi ‘stricată’ este cea cu numarul 3 (în cazul în care părintele lui x este roşu). În figura 11.4.a. este dat un exemplu care arată cum este încalcată această proprietate după ce un nod x este inserat. La celelalte subpuncte ale figurii sunt prezentaţi paşii algoritmului care ‘repară’ această încălcare.

(a)(b)

88

(d)fig. 11.4.

11.4 Ştergerea. Ştergerea unui nod dintr-un arbore roşu-negru este doar un pic mai

complicată decât operaţia de inserare. Algoritmul RN_Elimin este obţinut din algoritmul ELIMIN_BIN din cap.9 printr-o mică modificare. Vom utiliza o ‘sentinelă’ pentru a reprezenta nodurile Nil. Într-un arbore rou-negru T, ‘sentinela’ NiI(T) e un nod cu aceeaşi structură cu a oricărui nod în arbore. Culoarea sa este neagră, iar restul înregistrărilor (KEY, LS, LD, P) vor avea valori arbitrare. Într-un arbore roşu-negru vom înlocui toate legăturile la Nil cu legături la Nil(T). Sensul folosirii ‘sentinelei’ este de a înlocui un descendent Nil al unui nod x printr-un nod care are ca părinte pe x. Pentru economie de memorie vom folosi o singură ‘sentinela’ pentru a reprezenta toate nodurile Nil (setând la fiecare folosire a ‘sentinelei’ legătură de tip

89

părinte către nodul x la care ne referim). La fel ca la inserare trebuie să avem grijă să păstrăm proprietaţile roşu-negru ale arborelui. Acest lucru se face cu ajutorul unui algoritm care se apelează după ce ştergerea a fost efectuată. Cazurile care apar la ştergerea nodurilor dintr-un arbore roşu-negru sunt prezentate în figura următoare : (nodurile umbrite sunt roşii, cele albe sunt cele care pot fi roşii sau negre).

Cazul 1. Acest caz apare când fratele alăturat al nodului x este roşu.

90

Cazurile 2, 3, 4. Aceste cazuri apar când fratele alăturat al nodului x este negru

diferenţiindu-se între ele după culorile copiilor acestui frate. Întrebări şi exerciţii la capitolul 11.Exerciţiul 1 este în text la rotaţii.Exerciţiul 2.Pe arborele de la începutul capitolului ilustraţi ştergerea cheii 30.Exerciţiul 3.Pe arborele de la începutul capitolului ilustraţi adăugarea cheii 13.

91

CAPITOLUL 12 Îmbogăţirea structurilor de date.

În acest capitol vom învăţa: De ce este nevoie de îmbogăţirea unei structuri Cum arată un arbore pentru statistică de ordine Care sunt paşii care trebuie parcurşi pentru îmbogăţirea unei structuri Cum arată un arbore de intervale

In practica programării apar câte o dată situaţii care necesită numai o structură de date clasică, ca de exemplu lista dublu înlănţuită, tabela de dispersie sau arborele binar de căutare, însă majoritatea problemelor care trebuie rezolvate au nevoie de o structură nouă. Totuşi foarte far este nevoie să se creeze un tip complet nou de structură de date. Mai des se potriveşte să fie suficient să adaugăm informaţii suplimentare la o structură de date clasică în aşa fel încât ea saă răspundă nevoilor impuse de aplicaţia pe care o realizăm.

Desigur, îmbogăţirea structurilor de date nu este întotdeauna simplă, deoarece informaţia adăugată trebuie sa fie actualizată, şi întretinută prin operaţiile obişnuite ale structurii de date respective.

Definim a i-a statistică de ordine a unei mulţimi de n elemente ca al i-lea cel mai mic element. De exemplu, minimul unei multimi de n elemente este prima statistică de ordine (i = 1), iar maximul este a n-a statistică de ordine (i = n). Intuitiv, o mediană este punctul de la jumătatea drumului. Când n este impar, mediana este unică, şi apare pe pozitia i = (n+ 1)/2. Când n este par, există două mediane, care apar pe poziţiile i = n/2, i = n/2+ 1.

Se poate arăta că orice statistică de ordine poate fi determinată într-un timp de O(n) în cazul unei mulţimi neordonate.

În acest capitol vom vedea cum se pot modifica arborii roşu-negri pentru ca orice statistică de ordine să se determine într-un timp O(lg n) şi vom afla cum se determină rangul unui element - poziţia acestuia în ordonarea liniară a mulţimii - tot într-un timp O(lg n).

92

In figura următoare vom prezenta o structură de date care posedă operaţii rapide de statistici de ordine. Un arbore cu statistică de ordine T este un arbore roşu-negru care conţine o informaţie suplimentară în fiecare nod. La câmpurile uzuale pentru un nod x dintr-un arb ore roşu-negru: KEY(x), CUL(x), P(x), LS(x), şi LD(x), se adaugă un câmp nu DIM(x). Acest câmp conţine numărul de noduri (interne) din subarborele cu rădăcina x (incluzându-l şi pe x), adică dimensiunea subarborelui. Dacă facem convenţia DIM(NIL)=0, atunci are loc identitatea:

DIM(x)=DIM(LS(x))+DIM(LD(x))+1Un arbore de statistică de ordine care este de fapt un arbore roşu-negru

îmbogăţit. Nodurile gri sunt roşii, iar nodurile negre sunt negre. În partea de

jos a fiecarui nod este câmpul DIM(x) care reprezintă numărul de noduri ale subarborelui cu rădăcina x.

Fig.12.1

Regăsirea unui element cu rangul cunoscut. Începem cu operaţia care regăseşte un element cu rangul cunoscut.

Procedura RN-SELECT(x,i,y) retumeaza un pointer - y la nodul care conţine a i-a cheie din subarborele având rădăcina x. Pentru a determina a i-a cea mai mică cheie din arborele de statistică de ordine T vom face apelul RN -SELECT( RAD(T),i,y).

93

RN-SELECT(X,i,y) R=DIM(LS(x))+1daca i=r atunci

y=x altfel daca i < r atunci

cheama RN-SELECT(LS(x)) altfel cheama RN-SELECT(LD(x))

sdacasdacaReturn

Pentru a vedea cum funcţioneaza RN-SELECT, să considerăm căutarea pentru al 17 -lea cel mai mic element din arborele de statistica de ordine T din figura 12.1 . Se începe cu x egal cu rădăcina, a carei cheie este 26 ăi cu i = 17.

Deoarece dimensiunea subarborelui stâng al lui 26 este 12, rangul rădăcinii va fi 13. Prin urmare, ştim deja că nodul cu rangul 17 este a117-13 = 4-lea cel mai mic element din subarborele drept al lui 26. După apelul recursiv, x este nodul având cheia 41, iar i = 4.

Deoarece dimensiunea subarborelui stâng al lui 41 este 5, rangul său în subarborele în care acesta este rădăcina, este 6. Prin urmare ştim deja că nodul cu rangul 4 este în al 4-lea cel mai mic element al subarborelui stâng al lui 41. După apelul recursiv, x este nodul având cheia 30, iar rangul său în subarborele pentru care el este rădăcină este 2. Aşadar se face un nou apel recursiv pentru a-l determina pe al 14-2 =2-lea cel mai mic element din subarborele având rădăcina 38. La acest apel vom constata că subarborele stâng are dimensiunea 1, ceea ce înseamnă că rădăcina 38 este al doilea cel mai mic element. În consecinţă, acest ultim apel va întoarce pe y ca pointer la nodul având cheia 38 şi execuţia procedurii se termină.

Deoarece fiecare apel recursiv coboară un nivel în arborele de statistică de ordine T, timpul total pentru acest algoritm este, în cel mai defavorabil caz, proporţional cu înălţimea arborelui. Deoarece arborele este roşu-negru înălţimea sa este O(lg n), unde n este numărul de noduri. Prin urmare, timpul de execuţie al algoritmului prezentat este O(lg n) pentru o mulţime dinamică avand n elemente. Determinarea rangului unui element.

94

Fiind dat un pointer la un nod x dintr-un arbore de statistică de ordine T, procedura RN-RANG returnează r = poziţia lui x în ordinea liniară dată de parcurgerea în inordine a lui T.

RN-RANG(T,x,r) R=DIM(LS(x))+1y=x cat timp yRAD(T)

daca y=LD(P(x)) atunci r=r+DIM(LS(P(y)))+1

sdacay=P(y)

sciclureturn

Execuţia algoritmului RN-RANG pe arborele de statistică de ordine din figura 12.1 pentru determinarea rangului nodului având cheie 38 va produce următoarea secvenţa de valori pentru KEY(y) şi r înregistrate la începutul corpului ciclului cat timp. Iteraţia KEY r

1 38 22 30 43 41 44 26 17Procedura va returna rangul r = 17. Fiecare iteraţie a ciclului cat timp consumă un timp de O(1), iar y urcă

un nivel în arbore la fiecare iteraţie, timpul de execuţie al algoritmului RN- RANG este, în cel mai rău caz, proporţional cu înălţimea arborelui: O(lg n) pentru un arbore de statistică de ordine având n noduri. Întreţinerea dimensiunilor subarborilor.

Fiind dată valoarea câmpului dimensiune din fiecare nod, procedurile RN-SELECT şi RN-RANG pot calcula repede informţia de statistică de ordine. Nu am caştigat nimic dacă câmpurile nu se pot întreţine eficient prin operaţiile de bază ce modifică arborii roşu-negri. Vom arăta acum că dimensiunile subarborilor se pot întreţine atât pentru inserare cât şi pentru ştergere, fara afectarea timpilor asimptotici de execuţie ai acestor operaţii.

Inserarea unui nod într-un arbore roşu-negru se face în două etape: - se insereaza nodul x în arborele dat ca şi cum ar fi un arbore binar de căutare obişnuit şi se colorează inserat cu roşu

95

-se aplică asupra arborelui rezultat un algoritm care va recolora nodurile pentru conservarea proprietăţilor specifice arborelui roşu-negru. În prima fază se coboară în arbore începând de la rădăcină şi se

inserează nodul nou ca fiu al unui nod existent. A doua fază înseamnă urcarea în arbore, modificând culorile şi efectuând la sfârşit rotaţii pentru a conserva proprietăţile roşu-negru.

Pentru a întreţine dimensiunile subarborilor în prima fază, se va incrementa câmpul dimensiune[x] pentru fiecare nod x de pe drumul traversat de la rădăcină în jos spre frunze. Noul nod care se adăuga va primi valoarea 1 pentru câmpul său dimensiune. Deoarece pe drumul parcurs sunt O(lg n) noduri, costul suplimentar pentru întreţinerea câmpurilor dimensiune va fi şi el O(lg n ). În faza a doua, singurele modificări structurale ale arborelui roşu-negru sunt produse de rotaţii, care sunt cel mult două. Mai mult, rotaţia este o operaţie locală; ea invalideză numai câmpurile dimensiune din nodurile incidente (de la capetele) legăturii în jurul căreia se efectuează rotaţia. La codul procedurii ROTEŞTE-STANGA(T ,x) se adaugă următoarele două linii:

dimensiune(y)= dimensiune(x)dimensiune(x)= dimensiune(LS(x))+ dimensiune(LD(x))+1Figura de mai jos ilustrează cum sunt actualizate câmpurile dimensiune.

Pentru procedura ROTEŞTE-DREAPTA modificările sunt simetrice. Deoarece la inserarea unui nod într-un arbore roşu-negru sunt necesare

cel mult două rotaţii, se consumă un timp suplimentar de O(1) pentru actualizarea câmpurilor dimensiune, în faza a doua a inserării. În concluzie, timpul total necesar pentru inserarea unui nod într-un arbore de statistică de ordine cu n noduri este de O(lg n) acelaşi din punct de vedere asimptotic cu cel al arborilor roşu-negru obişnuiţi.

Ştergerea unui nod dintr-un arbore roşu-negru are de asemenea două faze: prima operează pe arborele binar de căutare, iar a doua face cel mult trei rotaţii şi în rest nu efectuează alte modificări structurale ale arborelui. Prima fază elimină din arbore un nod y. Pentru a actualiza dimensiunile subarborelui, vom traversa un drum în sus de la nodul y la rădăcină şi vom decrementa câmpurile dimensiune ale nodurilor de pe acest drum. Deoarece drumul are lungimea O(lg n), în cazul unui arbore roşu-negru cu n noduri, timpul suplimentar consumat cu întreţinerea câmpurilor dimensiune în prima faza a ştergerii unui nod este de O(lg n). Cele O(1) rotaţii din faza a doua a ştergerii sunt gestionate în aceeaşi manieră ca şi în cazul inserării. Prin urmare, atât inserarea cât şi ştergerea, inclusiv întretinerea câmpurilor dimensiune, consuma un timp O(lg n) pentru un arbore de statistică de ordine cu n noduri.

96

Cum se îmbogăţeşte o structură de date. La proiectarea algoritmilor apare frecvent problema îmbogăţirii

structurilor de date uzuale pentru ca acestea să ofere funcţionalitate suplimentară.

Procesul de îmbogăţire a unei structuri de date se poate împărţii în patru paşi: 1. Alegerea unei structuri de date suport. 2. Determinarea informaţiei suplimentare care trebuie inclusă şi întreţinută în structura de date luată ca suport.3. Verificarea posibilităţii întreţinerii informaţiei suplimentare în cazul operaţiilor de bază care modifică structura suport. 4. Proiectarea noilor operaţii. Ca şi în cazul altor metode de proiectare prezentate schematic, nu trebuie să respectăm exact paşii în ordinea de mai sus. Nu are nici un rost, de exemplu, să se determine informaţia suplimentară şi proiectarea noilor operaţii (paşii 2 şi 4) dacă nu se va putea întreţine eficient informaţia suplimentară memorată în structura de date. Totuşi, această metodă în patru paşi va asigura o abordare ordonată a eforturilor de îmbogăţire a unei structuri de date şi o schemă de organizare a documentaţiei referitoare la aceasta.

Paşii de mai sus au fast exemplificaţi la începutul capitolului pentru proiectarea arborilor de statistică de ordine. La pasul 1 am ales ca structură suport arborii roşu-negri. O indicaţie asupra utilităţii acestor arbori la obţinerea statisticilor de ordine este dată de eficienţa operaţiilor specifice mulţimilor dinamice pe o ordine totală, precum MINIM, MAXIM, SUCCESOR şi PREDECESOR.

La pasul 2 am adăugat câmpurile dimensiune, care conţin, pentru fiecare nod x, dimensiunea subarborelui având rădăcina x. În general, informaţia suplimentară are ca scop sa facă operaţiile (proprii structurii îmbogăţite) mai eficiente. De exemplu, am fi putut implementa operaţiile RN-SELECT şi RN-RANG folosind numai cheile memorate în arbore, însă în acest caz timpul lor de execuţie nu ar mai fi fost O(lg n). Uneori această informaţie suplimentară conţine referinţe şi nu date.

La pasul 3, ne-am asigurat că operaţiile de inserare şi ştergere pot întreţine câmpurile dimensiune fără a-şi altera eficienţa asimptotică, ele executându-se tot într-un timp O(lg n). În cazul ideal, un numar mic de modificări ale structurii de date, trebuie să fie suficient pentru a întreţine informaţia suplimentară. De exemplu, dacă am memora în fiecare nod rangul său din arbore, atunci operaţiile RN-SELECT şi RN-RANG s-ar

97

executa mai rapid, dar inserarea unui nou element minim în arbore, ar provoca modificarea acestei informaţii (rangul) în fiecare dintre nodurile arborelui. În schimb dacă memorăm dimensiunea subarborilor în locul rangului, inserarea unui nou element va necesita modificări ale informaţiilor doar in O(lg n) noduri.

La pasul 4, am proiectat operaţiile RN-SELECT şi RN-RANG. De fapt, îmbogăţirea structurii de date este impusă tocmai de nevoia de a implementa noi operaţii. Uneori informaţia suplimentară se va putea folosi nu numai la proiectarea operaţiilor noi, ci şi la reproiectarea celor proprii structurii de date suport pentru a le îmbunătăţii performanţele. Arbori de intervale.

Ne propunem să îmbogăţim arborii roşu-negri pentru a realiza operaţii pe mulţimi dinamice de intervale. Un interval închis este o mulţime notată [t1;t2] ={tR|t1,t2R, t1<t<t2}. În această secţiune vom presupune că intervalele cu care lucrăm sunt închise; extinderea rezultatelor la intervale deschise sau semideschise este imediată.

Intervalele reprezintă un instrument convenabil de reprezentare a evenimentelor care ocupa fiecare un interval continuu de timp. Am putea dori, de exemplu, să interogăm o bază de date de intervale de timp pentru a descoperi ce evenimente au apărut într-un anumit interval. Bazele de date temporale, de altfel, sunt la modă acum. Structura de date prezentată în aceasta secţiune oferă un mijloc eficient de întreţinere a unei astfel de baze de date de intervale.

Intervalul [t1;t2] se poate reprezenta sub forma unui obiect i, care are câmpurile jos[i] = t1 (capătul inferior) şi sus[i] = t2 (capătul superior). Spunem ca intervalele i şi i’ se suprapun daca i i’ adică dacă jos[i] sus[i’] şi jos[i’] sus[i]. Pentru orice două intervale i ~i i’ are loc trihotomia intervalelor, adică ele verifică doar una din urmatoarele trei proprietăţi: a. i si i’ se suprapun, b. sus[i] < jos[i‘], c. sus[i] < jos[i ‘].

În figura următoare sunt prezentate cele trei cazuri:

(a)

98

(b) (c)

Numim arbore de intervale un arbore roşu-negru care întreţine o mulţime dinamică de elemente, în care fiecare element x conţine un interval int[x]. Arborii de intervale au urmatoarele operaţii. INSEREAZĂ(T, x) adaugă la arborele de intervale T elementul x care are în câmpul int un interval. ŞTERGE(T,x) şterge elementul x din arborele de intervale T. CAUTA(T,x,r) retumează un pointer la un element din arborele de intervale pentru care int[y] se suprapune cu intervalul int[x], sau NIL dacă în mulţime nu există un astfel de element. --

În figura următoare vom ilustra modul de reprezentare al unei mulţimi de intervale cu ajutorul unui arbore de intervale. Vom aplica metoda în patru paşi descrisă mai înainte pentru a proiecta arborele de intervale şi operaţiile proprii acestuia.

(a)

99

(b)Figura (a) reprezinta 0 multime de 10 intervale, sortate de jos în sus după capătul din stânga (inferior), iar figura (b) reprezintă arborele de intervale corespunzător. Parcurgerea în inordine a acestui arbore va produce lista nodurilor sortată după capătul din stânga. Pasul 1: Structura de date suport

Am ales ca structură suport un arbore roşu-negru în care fiecare nod x conţine un câmp interval int[x] şi pentru care cheia nodului x este capătul inferior, jos[int[x]], al intervalului. Prin urmare, o traversare în inordine a structurii de date va produce o listă a intervalelor, ordonată după capătul inferior al acestora. Pasul 2: Informaţia suplimentară.

Pe lângă câmpul int[x], fiecare nod x va conţine o valoare max[x] care reprezintă valoarea maximă a capetelor intervalelor memorate în subarborele având rădăcina x. Deoarece capătul superior al fiecărui interval este cel puţin la fel de mare ca şi capătul inferior al acestuia, max[x] va fi de fapt valoarea maximă a capetelor superioare ale intervalelor memorate în subarborele având rădăcina x. Pasul 3: Întreţinerea informaţiei suplimentare.

Inserarea şi ştergerea se pot executa într-un timp O(lg n) pe un arbore de intervale cu n noduri. Valoarea câmpului max[x] se determină uşor dacă se cunosc int[x] şi valorile max ale fiilor nodului x cu : max[x] = max(sus[int[x]], max[LS[x]], max[LD[x]]).

De fapt, actualizarea câmpurilor max după o rotaţie se poate realiza într-un timp O(1). Pasul 4: Proiectarea noilor operaţii.

Singura operaţie care trebuie proiectată este CAUTA(T ,i,x), care găseşte un interval din arborele T suprapus pe intervalul i. Dacă T nu conţine

100

astfel de intervale se returnează NIL altfel retumează x - pointer la intervalul căutat. CAUTA(T,i,x) x=rad[T]Daca jos[i]>max[x] atunci x=NIL returnsdaca

cat timp x NIL şi i nu se suprapune cu int[x] daca LS[x] NIL şi max[LS[x]] jos[i] atunci

x=LS[x] altfel

x=LD[x] sdacascattimpDaca x≠NIL atunci i=x return

Altfel i=NILsdaca

Întrebări şi exerciţii la capitolul 12.Exerciţiul 1.Verificati afirmaţia: ‘dacă am memora în fiecare nod rangul său din arbore, atunci operaţiile RN-SELECT şi RN-RANG s-ar executa mai rapid, dar inserarea unui nou element minim în arbore, ar provoca modificarea acestei informaţii (rangul) în fiecare dintre nodurile arborelui’ . Exerciţiul 2.Scrieţi algoritmul pentru INSEREAZA(T, x). Exerciţiul 3. Scrieţi algoritmul pentru ŞTERGE(T, x). Exerciţiul 4.Scrieţi algoritmul care găseşte toate intervalele i’ pentru care sus[i] < jos[i ‘], unde i este un interval la intrare. Exerciţiul 5.Care este complexitatea algoritmului de mai sus?

Capitolul 13 Heap-uri binomiale şi Fibonacci

101

În acest capitol vom învăţa:

Ce sunt arborii binomiali

De ce se numesc aşa

Ce sunt heap-urile binomiale

Ce este analiza amortizată

Ce sunt heap-urile Fibonaci

De ce sunt superioare heap-urile Fibonacci

13.1 Despre necesitatea unor altfel de structuri

Mulţimea, ca noţiune fundamenatală, este la fel de importantă în informatică ca şi în matematică. În timp ce mulţimile matematice sunt nemodificabile, mulţimile manipulate de algoritmi pot creşte, descreşte sau, în restul cazurilor, se pot modifica în timp. Astfel de mulţimi se numesc dinamice. În funcţie de algoritmi, sunt necesare diferite timpuri de operaţii pentru a fi executate asupra mulţimilor. De exemplu, mulţi algoritmi au nevoie doar de posibilitatea de a insera elemente într-o mulţime, de a şterge elemente dintr-o mulţime sau de a testa apartenenţa la o mulţime. Alţi algoritmi necesită operaţii mai complicate. De exemplu, cozile de prioritate suportă operaţiile de inserare a unui element şi extragere a celui mai mic element dintr-o mulţime. Deci nu e surprinzător faptul că cea mai bună modalitate de a implementa o mulţime dinamică depinde de operaţiile pe care trebuie să le ofere.

Într-o implementare tipică a unei mulţimi dinamice, fiecare element este reprezentat de un obiect ale cărui câmpuri pot fi examinate şi manipulate dacă avem un pointer (o referinţă) la acel obiect. Unele categorii de mulţimi dinamice presupun că un câmp al obiectului este un câmp cheie, de identificare. Dacă toate cheile sunt diferite, mulţimea dinamică poate fi privită ca o mulţime de valori ale cheilor. Obiectul poate conţine date adiţionale, care sunt gestionate în alte câmpuri ale obiectului, dar sunt de fapt neutilizate de către implementarea mulţimii. De asemenea, obiectul poate avea câmpuri ce sunt manipulate de către operaţiile mulţimilor, aceste câmpuri putând conţine date sau referinţe spre alte obiecte din mulţime. Unele mulţimi dinamice presupun că valorile cheilor sunt alese dintr-o mulţime total ordonată, ca de exemplu, mulţimea numerelor reale. O ordine totală ne permite să definim, de exemplu, cel mai mic element în mulţime sau să vorbim despre următorul element mai mare decât un element dat din mulţime.

102

Operaţiile pe o mulţime dinamică pot fi împărţite în două categorii: interogări, care returnează informaţii despre mulţime sau operaţii de modificare, care modifică mulţimea.

Există structuri de date simple ca: stive, cozi, liste înlănţuite şi arbori cu rădăcină, tabele de dispersie (hash).

O altă structură de date importantă sunt arborii de căutare binară care au rol de bază pentru multe alte structuri de date. Arborii roşu-negru, sunt o variantă a arborilor de căutare binară. Un arbore roşu-negru este un arbore de căutare echilibrat ca şi un alt tip de arbore de căutare echilibrat numit B-arbore.

O altă structură de date importantă este ansamblul (heap-ul). Heapsort introduce o tehnică nouă de proiectare a algoritmilor bazată pe utilizarea unei structuri de date, numită heap. Structura de date heap este utilă nu doar pentru algoritmul heapsort, ea poate fi la fel de utilă şi în tratarea eficientă a unei cozi de prioritate.

Termenul heap a fost introdus şi utilizat iniţial în contextul algoritmului heapsort, dar acesta se foloseşte şi în legătură cu alocarea dinamică, respectiv în tratarea memoriei bazate pe “colectarea reziduurilor”, de exemplu, în limbajele de tip Lisp.

Prezentăm în continuare sructurile de date avansate: heap-uri binomiale şi operaţiile care se execută pe heap-uri: creare, găsirea cheii minime, reuniunea a două heap-uri binomiale, inserarea unui nod, extragerea nodului având cheia minimă şi descreşterea unei chei.

B-arborii, care sunt arbori echilibraţi folosiţi la memorarea pe disc magnetic. Deoarece discul magnetic operează mult mai încet decât memoria RAM, performanţele B-arborilor vor fi măsurate nunumai prin timpul consumat cu operaţiile de căutare dinamice, ci şi prin numărul de accese la disc efectuate. Pentru fiecare operaţie numărul de accese la disc este proporţional cu înălţimea B-arborelui.

Heap-urile binomiale execută operaţiile: INSEREAZĂ, MINIMUM, EXTRAGE-MIN şi REUNEŞTE în cazul cel mai defavorabil, în timp O(lg n), unde n este numărul total de elemente din heap-ul de intrare (sau în cele două heap-uri de intrare în cazul REUNEŞTE). Pe structura de date heap binomial se pot executa şi operaţiile ŞTERGE şi DESCREŞTE-CHEIE.

Heap-urile Fibonacci sunt superioare heap-urilor binonmiale, cel puţin în sens teoretic. Pentru măsurarea performanţelor heap-urilor Fibonacci se folosesc margini de timp amortizate. Operaţiile INSEREAZĂ, MINIMUM şi REUNEŞTE consumă în caul heap-urilor Fibonacci, timp amortizat de numai

103

O(1), în timp ce EXTRAGE-MIN şi ŞTERGE consumă un timp amortizat de O(lg n). Cel mai mare avantaj al heap-urilor Fibonacci este acela că DESCREŞTE-CHEIE consumă un timp amortizat de numai O(1). Operaţia DESCREŞTE-CHEIE definită pentru heap-urile Fibonacci este asimptotic mai slabă decât operaţiile similare la diverşii algoritmi specifici de grafuri, motiv pentru care aceştia o folosesc mai rar.

O altă categorie de structuri de date avansate o reprezintă structurile de date pentru mulţimi disjuncte. Se dă un univers de n elemente care sunt grupate în mulţimi dinamice. Iniţial, fiecare element este singur într-o mulţime. Operaţia reuneşte fuzionează două mulţimi, iar cererea GĂSEŞTE-MULŢIME identifică mulţimea care conţine un anumit element la un moment dat. Reprezentând fiecare mulţime printr-un arbore cu rădăcină, vom obţine operaţii surprinzător de rapide: o secvenţă de m operaţii se execută în timp O(m(m,n)), unde (m,n) este cel mult 4.

Printre altele sunt incluse şi următoarele structuri:- O structură de date, inventată de van Emde Boas, care admite operaţiile MINIMUM, MAXIMUM, INSEREAZĂ, ŞTERGE, CAUTĂ, EXTRAGE-MIN, EXTRACT-MAX, PREDECESOR, SUCCESOR. Acestea, în mulţimea de chei {1,2,…,n} necesită, în cel mai defavorabil caz, timpul O(lg lg n).- Arborii dinamici, definiţi de către Sleator şi Tarjan. Cu ajutorul lor se întreţine o pădure de arbori cu rădăcini disjuncte. Fiecare arc din fiecare arbore are ataşat, drept cost, un număr real. În arborii dinamici se pot efectua operaţii în vederea aflării părinţilor, rădăcinilor, costurilor arcelor, costului minim al unui drum de la un nod la o rădăcină. Arborii pot fi manevraţi prin tăierea de arce, modificarea costurilor arcelor de pe un drum de la un nod la o rădăcină, legarea unei rădăcini la un alt arbore etc. Una din implementările arborilor dinamici necesită un timp amortizat de O(lg n) pentru fiecare operaţie.- Arborii splay (oblici), dezvoltaţi de către Sleator şi Tarjan, sunt un tip de arbori binari de căutare care dau un timp amortizat O(lg n) pentru toate operaţiile standard. Una dintre aplicaţiile acestor arbori permite simplificarea arborilor dinamici.

Structurile de date persistente permit atât cereri, cât şi, uneori, actualizări ale versiunilor vechi ale structurii. Tehnicile de creare a structurilor de date înlănţuite persistente, descrise de către Driscoll, Sarnak, Sleator şi Tarjan, sunt eficiente deoarece consumă foarte puţin timp şi spaţiu.

13.2 Heap-uri binomiale

104

Heap-urile binomiale fac parte din structurile de date cunoscute sub numele de heap-uri interclasabile, caracterizate de următoarele operaţii:- CREEAZĂ-HEAP(H) creează şi returnează un heap nou care nu conţine elemente.- INSEREAZĂ(H,x) inserează nodul x a cărui cheie a fost iniţializată în heap-ul H.- MINIMUM(H,y) returnează un pointer la nodul cu cea mai mică cheie din H- EXTRAGE-MIN(H) şterge nodul cu cheia minimă din H şi returnează un pointer la acest nod.- REUNEŞTE(H1,H2,H) creează şi returnează un heap nou care conţine toate nodurile heap-urilor H1 şi H2. Heap-urile H1 şi H2 sunt “distruse” în urma acestei operaţii.- DESCREŞTE-CHEIE(H,x,k) atribuie nodului x din heap-ul H valoarea k pentru cheie, valoare presupusă a nu fi mai mare decât valoarea curentă a cheii.- ŞTERGE(H,x) şterge nodul x din heap-ul H.

Tabelul de mai jos arată că heap-urile binare obişnuite, folosite, de exemplu, în heapsort, suportă bine aceste operaţii, cu excepţia operaţiei REUNEŞTE. În cazul heap-urilor binare, pentru fiecare operaţie, exceptând REUNEŞTE, tipul de execuţie în cazul cel mai defavorabil este O(lg n) (sau mai bun). Dacă totuşi un heap binar trebuie să execute operaţia REUNEŞTE, aceasta va fi lentă. Prin concatenarea celor două tablouri care memorează heap-urile binare care se interclasează şi apoi aplicarea operaţiei RECONSTITUIE-HEAP, timpul de execuţie, în cazul cel mai defavorabil, pentru operaţia REUNEŞTE este (n).

procedură

heap binar(cazul cel mai defavorabil)

heap binomial(cazul cel mai defavorabil)

heap Fibonacci(amortizat)

CREEAZĂ-HEAP (1) (1) (1)INSEREAZĂ (lg n) O(lg n) (1)MINIMUM (1) O(lg n) (1)EXTRAGE-MIN (lg n) (lg n) O(lg n)REUNEŞTE (n) O(lg n) (1)DESCREŞTE-CHEIE

(lg n) (lg n) (1)

ŞTERGE (lg n) (lg n) O(lg n)

105

În tabel sunt prezentaţi timpii de execuţie ai operaţiilor pentru trei implementări ale heap-urilor interclasabile. Numărul elementelor din heap-urile folosite de o operaţie este notat cu n.

În continuare vom analiza heap-urile binomiale a căror margini pentru timpii de execuţie, în cazurile cele mai defavorabile, sunt prezentate în tabelul de mai sus. În particular, operaţia reuneşte pentru interclasarea a două heap-uri binomiale cu n elemente va fi de complexitate O(lg n). Vor fi ignorate operaţiile de alocare a nodurilor înainte de o inserare şi de eliberare a nodurilor după o ştergere. Presupunem că de aceste detalii este responsabil codul care apelează operaţiile heap-ului.

Heap-urile binare, binomiale şi Fibonacci sunt ineficiente în raport cu operaţia de CĂUTARE; pentru găsirea unui nod care conţine o anumită valoare nu se poate stabili o cale de căutare directă în aceste structuri. Din acest motiv, operaţiile DESCREŞTE-CHEIE şi ŞTERGE care se referă la un anumit nod reclamă ca parametru de intrare un pointer la nodul respectiv. În cele mai multe aplicaţii această cerinţă nu ridică probleme.

13.3 Arbori binomiali

106

figura 13.2 Deoarece un heap binomial este o colecţie de arbori binomiali, vom prezenta mai intâi arborii binomiali şi demonstra unele proprietăţi esenţiale ale acestora. Arborele binomial Bk este un arbore ordonat definit recursiv. După cum se vede în figura de mai jos, arborele binomial B0 constă dintr-un singur nod. Arborele binomial Bk constă din doi arbori binomiali Bk-1 care sunt înlănţuiţi: rădăcina unui dintre ei este fiul situat cel mai în stânga rădăcinii celuilalt arbore. Figura prezintă arborii binomiali de la B0 la B4. Lema următoare conţine câteva proprietăţi ale arborilor binomiali. Arborele binomial Bk are: 1. 2k noduri, 2. înălţimea k, 3. exact noduri, la adâncimea i, pentru i=0,1,…,k.4. rădăcina de grad k, grad mai mare decât al oricărui alt nod; mai mult, dacă fii rădăcinii sunt numerotaţi de la stânga spre dreapta prin k-1, k-2,…,0 atunci fiul i este rădăcina subarborelui Bi.

107

DemonstraţieDemonstraţia este inductivă în raport cu k. Pasul iniţial pentru fiecare proprietate îl constituie arborele binomial B0. Verificare prorpietăţilor pentru B0 este imediată. Presupunem că lema are loc pentru arborele Bk-1.1. Arborele binomial Bk are 2k-1+2k-1=2k noduri, deoarece el constă din două copii ale arborelui Bk-1.2. Ţinând cont de modul în care sunt înlănţuite cele două copii ale lui Bk-1 pentru a forma Bk, rezultă că adâncimea maximă a lui Bk este cu 1 mai mare decât adâncimea maximă a lui Bk-1. Din ipoteza de inducţie obţinem valoarea (k-1)+1=k pentru adâncimea maximă a lui Bk.3. Fie D(k,i) numărul nodurilor situate pe nivelurile i al arborelui binomial Bk. Deoarece Bk este compus din două copii înlănţuite ale lui Bk-1, un nod de pe nivelul i din Bk-1 apare în Bk pe nivelele i şi i+1. Altfel spus, numărul nodurilor situate pe nivelul i în Bk este egal cu numărul nodurilor de pe nivelul i din Bk-1

plus numărul nodurilor de pe nivelul i-1 din Bk-1. Astfel,

4. Singurul nod cu grad mai mare în Bk decât în Bk-1 este rădăcina, care are cu un fiu mai mult decît în Bk-1. Deoarece rădăcina lui Bk-1 are gradul k-1, rădăcina lui Bk are gradul k. Din ipoteza de inducţie şi după cum ilustrează figura de mai sus, fii lui Bk-1 (de la stânga la dreapta) sunt rădăcinile arborilor Bk-2, Bk-3, …, B0. Când Bk-1 este legat la Bk-1, fii rădăcinii rezultate sunt rădăcini pentru Bk-1, Bk-2, …, B0.CorolarGradul maxim al nodurilor unui arbore binomial având n noduri este lg n. DemonstraţieRezultă imediat din prorietăţile 1 şi 4 ale lemei de mai sus.

Proprietatea 3 a lemei justifică termenul de arbore binomial prin faptul că sunt coeficienţii binomiali.

Heap-uri binomialeUn heap binomial H este format dintr-o mulţime de arbori binomiali care satisfac următoarele proprietăţi de tip binomial.1. Fiecare arbore binomial din H satisface proprietatea de ordonare a unui heap: cheia unui nod este mai mare sau egală decât cheia părintelui său. 2. Există cel mult un arbore binomial în H a cărui rădăcină are un grad dat.Conform primei proprietăţi, rădăcina unui arbore cu proprietatea de heap ordonat, conţine cea mai mică cheie din arbore.

108

Proprietatea a doua implică faptul că un heap binomial H având n noduri conţine cel mult [lg n]+1 arbori binomiali. Pentru o justificare a acestei afirmaţii se observă că reprezentarea binară a lui n are [lg n]+1 biţi, fie aceştia

<b[lg n], b[lg n]-1,…,b0>, astfel încât . Din proprietatea 1 a lemei de

mai sus rezultă că arborele binomial Bi apare în H dacă şi numai dacă bitul bi=1. Astfel heap-ul H conţine cel mult [lg n]+1 arbori binomiali.

În figura de mai jos este prezentat un heap binomial H având 13 noduri. Reprezeantarea binară a numărului 13 este 1101, iar H conţine arborii binomiali cu proprietatea de heap B3, B2 şi B0 având 8, 4 şi respectiv un nod,

în total fiind 13 noduri.figura 13.3

109

Reprezentarea heap-urilor binomialeDupă cum ilustrează şi figura de mai sus, fiecarea arbore binomial al

unui heap binomial este memorat conform reprezentării stânga-fiu, dreapta-frate. Fiecare nod are un câmp cheie plus alte informaţii specifice aplicaţiei care foloseşte heap-ul. În plus, fiecare nod x conţine pointerii p[x] spre părintele lui, fiu[x] spre fiul situat cel mai în stânga şi frate[x] spre fratele lui x, situat imediat în dreapta. Dacă nodul x este o rădăcină atunci p[x]=NIL. Dacă nodul x nu are fii atunci fiu[x]=NIL, iar dacă x este fiu situat cel mai în dreapta, atunci frate[x]=NIL. Fiecare nod conţine de asemenea câmpul grad[x], care reprezintă numărul fiilor lui x.

Rezultă din figură că rădăcinile arborilor binomiali conţinuţi de un heap binomial sunt păstrate într-o listă înlănţuită pe care o vom numi în continuare listă de rădăcini. La o traversare a listei de rădăcini gradul rădăcinilor formează un şir strict crescător. Din a doua proprietate de heap binomial, rezultă că gradele rădăcinilor unui heap binomial având n noduri formează o submulţime a mulţimii {0,1,…,[lg n]}. Câmpul frate are semnificaţii diferite după cum nodurile sunt rădăcini sau nu. Dacă x este rădăcină atunci frate[x] referă rădăcina următoare în lista de rădăcini. (dacă x este ultima rădăcină din listă atunci, ca de obicei, frate[x]=NIL.)

Un heap binomial dat H este referit prin pointerul cap[H] spre prima rădăcină din lista de rădăcini a lui H. Dacă heap-ul binomial H nu are elemente, atunci cap[H]=NIL.

13.4 Operaţii pe heap-uri binomiale

Crearea unui heap binomial nou

Pentru a crea un heap binomial vid, procedura CREEAZĂ-HEAP-BINOMIAL va aloca şi returna un obiect H, pentru care cap[H]=NIL. Timpul de execuţie este (1).

Găsirea cheii minime

Procedura HEAP-BINOMIAL-MIN returnează un pointer y la nodul cu cea mai mică cheie dintr-un heap binomial H având n noduri. Această implementare presupune că nu există chei cu valoarea .HEAP-BINOMIAL-MIN(H,y)1: y=NIL2: x=cap[H]

110

3: min=4: cât timp xNIL execută5: dacă cheie[x]<min atunci6: min=cheie[x]7: y=x8: sfârşit daca9: y=frate[x]10: sfârşit cât timp11: return

Cheia minimă a unui heap binomial se află într-o rădăcină deoarece este un heap ordonat. Procedura HEAP-BINOMIAL-MIN verifică toate rădăcinile (în număr de cel mult [lg n]+1) şi reţine minimul curent în min, respectiv un pointer la acest minim în y. Apelată pentru heap-ul binomial din figura 3, procedura va returna un pointer la nodul care conţine cheia 1.

Timpul de execuţie al procedurii HEAP-BINOMIAL-MIN este O(lg n) deoarece există cel mult [lg n]+1 rădăcini verificate.

Reuniunea a două heap-uri binomiale

Operaţia de reuniune a două heap-uri binomiale este folosită de aproape toate celelalte operaţii rămase. Procedura HEAP-BINOMIAL-REUNEŞTE înlănţuie repetat arborii binomiali care au rădăcini de acelaşi grad. Procedura următoare leagă arborele Bk-1 având nodul rădăcină y la arborele Bk-1 având nodul rădăcină z; mai precis, z va fi părintele lui y. Nodul z devine astfel rădăcina unui arbore Bk.BINOMIAL-LEGĂTURĂ(y,z)1: p[y]=z2: frate[y]=fiu[z]3: fiu[z]=y4: grad[z]=grad[z]+15: return

Procedura BINOMIAL-LEGĂTURĂ plasează nodul y în capul listei înlănţuite care conţine fiii nodului z într-un timp O(1). Reprezentarea stânga-fiu, dreapta-frate a fiecărui arbore binomial asigură succesul acestei proceduri deoarece fiecare arbore binomial are proprietatea de ordonare a arborelui: fiu cel mai din stânga al rădăcinii unui arbore Bk este rădăcina unui arbore Bk-1.

Procedura HEAP-BINOMIAL-REUNEŞTE uneşte două heap-uri binomiale H1 şi H2 şi returnează heap-ul rezultat. Pe parcursul efectuării operaţiei, reprezentările heap-urilor H1 şi H2 sunt distruse. Procedura foloseşte

111

pe lângă procedura BINOMIAL-LEGĂTURĂ încă o procedură auxiliară ANSAMBLU-BINOMIAL-INTERCLASEAZĂ, care interclasează listele de rădăcini ale heap-urilor H1 şi H2 într-o singură listă simplu înlănţuită ordonată crescător după gradul nodurilor.

112

figura 13.4

În figura 13.4 se prezintă un exemplu pentru care se petrec toate cele patru cazuri indicate prin comentarii în procedura HEAP-BINOMIAL-REUNEŞTE.Procedura HEAP-BINOMIAL-REUNEŞTE se desfăşoară în două faze. În prima fază se interclasează (prin apelul HEAP-BINOMIAL-INTERCLASEAZĂ) listele de rădăcini ale heap-urilor binomiale H1 şi H2 într-o listă simplu înlănţuită H care este ordonată crescător în raport cu gradul nodurilor rădăcină. Lista formată poate conţine cel mult două rădăcini cu acelaşi grad. Astfel, în faza a doua sunt unite toate rădăcinile care au acelaşi grad, astfel încât să nu existe două noduri cu acelaşi grad. Deoarece lista înlănţuită H este ordonată după grad, operaţiile de înlănţuire din faza a doua sunt efectuate rapid.

Detaliem cele două fraze ale procedurii. Liniile 1-3 încep prin interclasarea celor două liste ale heap-urilor binomiale H1 şi H2 într-o singură listă de rădăcini H. Listele de rădăcini ale lui H1 şi H2 sunt ordonate strict crescător după grad, iar HEAP-BINOMIAL-INTERCLASEAZĂ returnează o listă de rădăcini H, ordonată crescător după grad. Dacă listele H1 şi H2 au împreună m noduri, atunci timpul de execuţie pentru HEAP-BINOMIAL-INTERCLASEAZĂ este O(m), datorat examinării repetate a rădăcinilor din capul listelor şi adăugării rădăcinii având gradul mai mic în lista de rădăcini rezultat, eliminând această rădăcină din lista dată la intrare. HEAP-BINOMIAL-REUNEŞTE(H1,H2,H) 1: Cheama CREEAZĂ-HEAP-BINOMIAL(H ) 2: Cheama HEAP-BINOMIAL-INTERCLASEAZĂ(H1,H2,H) 3: eliberează obiectele H1,H2, dar nu şi listele referite de ele 4: dacă cap[H]=NIL atunci 5: return 6: sfârşit dacă 7: prec-x=NIL 8: x=cap[H]

113

9: urm-x=frate[x]10: cât timp urm-xNIL 11: dacă (grad[x]grad[urm-x]) sau (frate[urm-x]NIL şi grad[frate[urm-x]]=grad[x]) atunci11: prec-x=x cazurile 1 şi 212: x=urm-x cazurile 1 şi 213: altfel14: dacă cheie[x]cheie[urm-x] atunci15: frate[x]=frate[urm-x] cazul 316: BINOMIAL-LEGĂTURĂ(urm-x,x) cazul 317: altfel18: dacă prec-x=NIL atunci19: cap[H]=urm-x cazul 420: altfel21: frate[prec-x]=urm-x cazul 422: sfârşit dacă23: BINOMIAL-LEGĂTURA(x,urm-x) cazul 424: x=urm-x cazul 425: sfârşit dacă26: urm-x=frate[x] cazul 427: sfârşit dacă28: sfârşit dacă29: sfârşit cât timp30: return

În continuare procedura HEAP-BINOMIAL-REUNEŞTE iniţializează câţiva pointeri în lista de rădăcini H. Dacă heap-urile binomiale date la intrare sunt vide, atunci în liniile 4-5 se iese din procedură. Începând cu linia 6 ne situăm în cazul în care H conţine cel puţin o rădăcină. Din acest punct se păstrează 3 pointeri în lista de rădăcini: - x indică rădăcina curentă examinată,- prec-x indică rădăcina precedentă lui x în lista de rădăcini: frate[prec-x]=x,- urm-x indică rădăcina următoare lui x în listă: frate[x]=urm-x.H poate conţine iniţial cel mult două rădăcini cu un grad dat: deoarece H1 şi H2

sunt heap-uri binomiale, ele nu au două rădăcini având acelaşi grad. Mai mult, procedura HEAP-BINOMIAL-INTERCLASEAZĂ ne garantează că dacă H conţine două rădăcini având acelaşi grad, atunci ele sunt adiacente în lista de rădăcini.

114

În timpul execuţiei procedurii HEAP-BINOMIAL-REUNEŞTE, de fapt, pot exista 3 rădăcini având acelaşi grad. Vom vedea când se produce această situaţie. La fiecare iteraţie a ciclului cât timp din liniile 9-24 se decide dacă se poate lega x şi urm-x în funcţie de gradul lor şi de gradul lui frate[urm-x]. Un invariant al acestui ciclu este faptul că la fiecare reluare a corpului ciclului atât x cât şi urm-x sunt diferiţi de NIL.

figura 13.5Cazul 1, prezentat în figura 13.5.a se produce atunci când

grad[x]grad[urm-x], adică x este rădăcina unui arbore Bk şi urm-x este rădăcina unui arbore Bl pentru un l>k. Această situaţie este tratată în liniile 11-12. Deoarece nu trebuie să legăm x şi urm-x, nu rămâne decât să deplasăm pointerii în listă. Actualizarea pointerului urm-x pentru a referi nodul ce

115

urmează noului nod x este efectuată în linia 24, deoarece aceasta este comună tuturor cazurilor.

Cazul 2, prezentat în figura 13.5.b, are loc atunci când x este prima rădăcină din cele 3 care au acelaşi grad, adică atunci când grad[x]=grad[urm-x]=grad[frate[urm-x]]Acest caz este tratat similar cu cazul 1: efectuăm doar o deplasare a pointerilor în listă. Testul din linia 10 este comun cazurilor 1 şi 2, la fel cum liniile 11-12 tratează amândouă cazurile.

Cazurile 3 şi 4 se produc atunci când x este prima rădăcină din 2 rădăcini succesive având acelaşi grad, adică grad[x]=grad[urm-x]grad[frate[urm-x]].Aceste cazuri apar la iteraţia următoare după fiecare caz, dar unul din ele urmează imediat după cazul 2. În cazurile 3 şi 4 vom înlănţui x şi urm-x. Aceste cazuri diferă între ele după cum x sau urm-x au cheia mai mică, fapt ce determină care din noduri va fi rădăcină în procesul de legare a lor.

În cazul 3, prezentat în figura 13.5.c, cheie[x]cheie[urm-x], astfel că urm-x va fi legat la linia x. Linia 15 şterge urm-x din lista de rădăcini, iar în linia 16 urm-x devine fiul situat cel mai în stânga lui x.

În cazul 4, prezentat în figura 13.5.d cheia mai mică o are urm-x, deci este legat la urm-x. Liniile 17-21 şterg x din lista de rădăcini. Există două subcazuri, după cum x este (linia 19) sau nu (linia 21) prima rădăcină din listă. În linia 22, x devine fiul situat cel mai în stânga lui urm-x, iar linia 23 actualizează x pentru iteraţia următoare.Pregătirea iteraţiei următoare a ciclului cât timp este aceeaşi pentru ambele cazuri 3 şi 4. x referă un arbore Bk+1 obţinut prin negarea a doi arbori Bk. După operaţia HEAP-BINOMIAL-INTERCLASEAZĂ în lista de rădăcini existau zero, unu sau doi arbori Bk+1, deci x este acum prima rădăcină din lista de rădăcini pentru un număr de unu, doi sau trei arbori Bk+1. În cazul existenţei unui singur arbore (x referindu-l pe acesta), la iteraţia următoare se va produce cazul 1: grad[x]grad[urm-x]. Dacă x referă primul arbore din doi existenţi atunci la iteraţia următoare are loc unul din cazurile 3 sau 4. În sfârşit, dacă x referă primul arbore din trei existenţi atunci la iteraţia următoare are loc cazul 2.

Timpul de execuţie pentru HEAP-BINOMIAL-REUNEŞTE este O(lg n), unde n este numărul total de noduri din heap-urile binomiale H1 şi H2. Justificăm acest rezultat după cum urmează: fie n1 şi n2 numărul nodurilor heap-urilor H1 şi respectiv H2 astfel încât n=n1+n2. Atunci numărul maxim de rădăcini conţinute de H1 şi H2 este [lg n1]+1, respectiv [lg n2]+1. Astfel imediat după apelul HEAP-BINOMIAL-INTERCLASEAZĂ, H conţine cel mult

116

[lg n1]+[lg n2]+22[lg n]+2=O(lg n) rădăcini. Rezultă că timpul de execuţie pentru HEAP-BINOMIAL-INTERCLASEAZĂ este O(lg n). Fiecare iteraţie a ciclului cât timp se execută într-un timp O(1) şi pot exista cel mult [lg n1]+[lg n2]+2 iteraţii deoarece de la fiecare iteraţie fie pointerii avansează cu o poziţie în lista H, fie se elimină o rădăcină din lista de rădăcini. Astfel, timpul total de execuţie este O(lg n).

Inserarea unui nod

Procedura următoare inserează nodul x în heap-ul binomial H. Se presupune că nodul x este creat şi câmpul cheie[x] este iniţializat. HEAP-BINOMIAL-INSEREAZĂ(H,x)1: Cheama CREEAZĂ-HEAP-BINOMIAL(H’ )2: p[x]=NIL3: fiu[x]=NIL4: frate[x]=NIL5: grad[x]=06: cap[H’]=x7:Cheama HEAP-BINOMIAL-REUNEŞTE(H,H’,H)8: return

Procedura creează un heap binomial H’ cu un nod într-un timp O(1) pe care îl reuneşte apoi cu heap-ul binomial H având n noduri într-un timp O(lg n). Procedura HEAP-BINOMIAL-REUNEŞTE eliberează spaţiul alocat heap-ului binomial temporar H’.

Extragerea nodului având cheia minimă

Procedura următoare extrage nodul având cheia minimă din heap-ul binomial H şi returnează un pointer la nodul extras.HEAP-BINOMIAL-EXTRAGE-MIN(H)1: caută rădăcina x cu cheia minimă în lista de rădăcini şi şterge x din lista de rădăcini a lui H2: Cheama CREEAZĂ-HEAP-BINOMIAL(H’)3: inversează ordinea memorării fiilor lui x în lista înlănţuită asociată şi atribuie lui cap[H’] capul listei rezultate4: Cheama HEAP-BINOMIAL-REUNEŞTE(H,H’,H)5: returne

117

figura 13.6

Modul de funcţionare al procedurii este ilustrat în figura 13.6. Heap-ul binomial H dat ca parametru de intrare este ilustrat în figura 13.6.a. Figura 13.6.b prezintă situaţia obţinută după linia 1: rădăcina x având cheia minimă a fost eliminată din lista de rădăcini a lui H. Dacă x este rădăcina unui arbore Bk, atunci fiii lui x de la stânga la dreapta, sunt rădăcinile unor arbori Bk-1, Bk-2,…, B0. În figura 6.c se ilustrează faptul că inversând lista fiilor lui x (în linia 3) obţinem un heap binomial H’ care conţine toate nodurile din arborele corespunzător lui x, exceptându-l pe x. Deoarece în linia 1 arborele lui x este şters din H, heap-ul binomial rezultat prin reunirea în linia 4 a lui H şi H’, conform figurii 6.d, va conţine toate nodurile care existau iniţial în H, exceptându-l desigur pe x. În final, în linia 5 se returnează x.HEAP-BINOMIAL-EXTRAGE-MIN se execută într-un timp O(lg n) deoarece fiecare din liniile 1-4 se execută într-un timp O(lg n).

118

Descreşterea unei chei Procedura HEAP-BINOMIAL-DESCREŞTE-CHEIE(H,x,k) 1: dacă k>cheie[x] atunci 2: eroare “cheia nouă este mai mare decât cheia existentă” 3: sfârşit dacă 4: cheie[x]=k 5: y=x 6: z=p[y] 7: cât timp zNIL şi cheie[y]<cheie[z] 8: interschimbă cheie[y]cheie[z] 9: dacă y şi z au şi alte câmpuri atunci interschimbă şi aceste câmpuri10: y=z11: z=p[y]12: sfârşit cât timp

119

figura 13.7

Această procedură descreşte o cheie în mod similar cu metoda aplicată pentru un heap binar: prin “ridicarea” cheii în heap, după cum arată figura 7. După ce procedura se asigură că noua cheie nu este mai mare decât cea curentă şi apoi actualizează cheia curentă a lui x, urmează un proces de căutare în sus, iar y referă iniţial nodul x. La fiecare iteraţie a ciclului cât timp, în liniile 6-10, se compară cheie[y] cu cheia părintelui z a lui y.Dacă y este chiar rădăcina sau cheie[y]cheie[z], atunci arborele binomial este un heap ordonat. În caz contrar nodul y încalcă proprietatea de ordonare pentru heap, astfel cheile lui y şi z se interschimbă, împreună cu alte informaţii, apoi procedura deplasează y şi z cu un nivel mai sus în arbore şi continuă iteraţiile.

Timpul de execuţie HEAP-BINOMIAL-DESCREŞTE-CHEIE este O(lg n). Numărul maxim de iteraţii pentru ciclul cât timp (liniile 6-10) este [lg n] deoarece, din proprietatea 2 a lemei enunţate mai sus rezultă că înălţimea maximă a lui x este [lg n].

120

Ştergerea unei chei

Ştergerea cheii şi a altor informaţii asociate unui nod x aparţinând unui heap binomial H se poate desfăşura fără dificultate într-un timp O(lg n). Implementarea următoare presupune că nodurile din heap-ul binomial nu au chei având valoarea -.HEAP-BINOMIAL-ŞTERGE(H,x)1: HEAP-BINOMIAL-DESCREŞTE-CHEIE(H,x,-)2: HEAP-BINOMIAL-EXTRAGE-MIN(H)

După ce în procedura HEAP-BINOMIAL-ŞTERGE se atribuie valoarea - cheii nodului x, acesta devine nodul având cheia minimă în heap-ul binomial. Urmează apoi ca această cheie şi eventual alte informaţii asociate să fie ridicate până la o rădăcină prin apelul HEAP-BINOMIAL-DESCREŞTE-CHEIE. Această rădăcină este apoi eliminată din H prin apelul HEAP-BINOMIAL-EXTRAGE-MIN.

Timpul de execuţie pentru HEAP-BINOMIAL-ŞTERGE este O(lg n).

13.3 Heap-uri Fibonacci

Un arbore cu rădăcină este un arbore liber în care unul dintre vârfuri se deosebeşte de celelalte. Vârful evidenţiat se numeşte rădăcina arborelui.

Un arbore ordonat este un arbore cu rădăcină în care fiii fiecărui nod sunt ordonaţi. Cu alte cuvinte, dacă un nod are k fii, atunci există un prim fiu, un al doilea fiu,…şi un al k – lea fiu.

Arborele binomial Bk este un arbore ordonat definit recursiv:1. arborele binomial B0 constă dintr-un singur nod;

2. arborele binomial Bk constă din doi arbori binomiali Bk-1 care sunt înlănţuiţi: rădăcina unuia dintre ei este fiul situat cel mai în stânga rădăcinii celuilalt arbore.

Un heap binomial H este format dintr-o mulţime de arbori binomiali care satisfac următoarele proprietăţi de heap binomial :

1. fiecare arbore binomial din H satisface proprietatea de ordonare a unui heap : cheia unui nod este mai mare sau egală decât cheia părintelui său;

2. există cel mult un arbore binomial în H a cărui rădăcină are un grad dat.

121

Conform acestei definiţii, rădăcina unui arbore cu proprietatea de heap ordonat, conţine cea mai mică cheie din arbore.

Similar cu un heap binomial, un heap Fibonacci este o colecţie de arbori care au proprietatea de ordonare de heap. Totuşi, arborii dintr-un heap Fibonacci nu trebuie să fie arbori binomiali. Figura 13.8(a) reprezintă un exemplu de heap Fibonacci.

Spre deosebire de arborii dintr-un heap binomial, care sunt ordonaţi, arborii aparţinând unui heap Fibonacci sunt arbori cu rădăcină , dar neordonaţi. După cum prezintă figura 13.8(b), fiecare nod x conţine un pointer p[x] spre părintele lui şi un pointer fiu[x] la unul din fiii lui. Fiii lui x sunt înlănţuiţi circular printr-o listă dublu înlănţuită, numită lista fiilor lui x. Fiecare fiu y dintr-o listă de fii are pointerii stânga[y] şi dreapta[y] care indică fratele stâng, respectiv drept al lui y. Dacă nodul y este singurul fiu, atunci stânga[y] = dreapta[y] =y . Ordinea în care apar fiii în listă este arbitrară.

Folosirea listelor dublu înlănţuite şi circulare pentru heap-uri Fibonacci are două avantaje. În primul rând, putem şterge un nod dintr-o listă dublu înlănţuită şi circulară într-un timp O(1). În al doilea rând, putem concatena două liste de acest tip, obţinând o singură listă dublu înlănţuită şi circulară tot într-un timp O(1). În descrierea operaţiilor pe heap-uri Fibonacci ne vom referi informal la aceste operaţii pe liste.

Fiecare nod va conţine încă două câmpuri utile. Numărul de fii din lista fiilor nodului x este memorat în grad[x]. Câmpul de tip boolean marcat[x] va indica dacă nodul x a pierdut un fiu după ultima operaţie în care x a fost transformat în fiul unui alt nod. Nodurile nou create nu sunt marcate, iar un nod x devine nemarcat atunci când este transformat în fiul unui alt nod.

Un heap Fibonacci H este referit printr-un pointer min[H] al rădăcinii arborelui care conţine cheia minimă; acest nod este numit nodul minim al heap-ului Fibonacci. Dacă un heap Fibonacci este vid, atunci min[H] =NIL

Rădăcinile tuturor arborilor dintr-un heap Fibonacci sunt înlănţuite prin pointerii stânga şi dreapta, formând o listă dublu înlănţuită şi circulară, numită listă de rădăcini a heap-ului Fibonacci. Astfel, pointerul min [H] indică acel nod din lista de rădăcini care are cheia minimă. Ordinea nodurilor din lista de rădăcini este arbitrară. Un atribut pe care ne vom baza este şi numărul nodurilor n[H] al unui heap Fibonacci H.

13.4 Metoda de potenţial

122

Vom folosi în analiza complexităţii operaţiilor pe heap-uri Fibonacci metoda de potenţial .

Descriem în continuare cum lucrează metoda de potenţial. Plecăm de la o structură de date iniţială D0 asupra căreia se execută n operaţii. Pentru fiecare i=1,2,…,n, fie ci costul real al operaţiei i şi fie Di structura de date obţinută din Di-1 după aplicarea operaţiei i. O funcţie de potenţial Ф ataşează fiecărei structuri de date Di numărul Ф(Di ), care este potenţialul asociat structurii de date Di . Costul amortizat ĉi al operaţiei i pentru funcţia de potenţial Ф este definit astfel:

ĉi = ci + Ф(Di) - Ф(Di-1). (13.1)

Prin urmare, costul amortizat al fiecărei operaţii este costul real plus creşterea de potenţial datorată operaţiei.

Conform ecuaţiei (13.1), costul amortizat total al celor n operaţii este: n n n

ĉi = (ci + Ф(Di) - Ф(Di-1)) = ci + Ф(Dn) - Ф(D0) (13.2)

i=1 i=1 i=1

Costurile amortizate definite de ecuaţiile (13.1) şi (13.2) depind de alegerea funcţiei de potenţial Ф. Funcţii de potenţial diferite pot conduce la costuri amortizate diferite, care rămân însă margini superioare ale costurilor reale. De multe ori are loc o “negociere” la alegerea funcţiei de potenţial: cea mai bună funcţie de potenţial depinde de limitele de timp dorite.

Pentru un heap Fibonacci H vom indica prin t(H) numărul rădăcinilor din lista de rădăcini a lui H, iar prin m(H) numărul nodurilor marcate din H. Potenţialul unui heap Fibonacci este definit prin:

Ф(H)=t(H)+2m(H) (13.3)

De exemplu, potenţialul heap-ului Fibonacci din figura 13.8 este 5+2·3=11. Potenţialul unei mulţimi de heap-uri Fibonacci este egal cu suma potenţialelor heap-urilor Fibonacci conţinute. Vom presupune că o unitate de potenţial corespunde unui volum de calcul constant, cu o constantă suficient

123

de mare care acoperă orice calcul necesar care se execută într-un timp constant .

(a). min[H]

------ -------- ---------------- -------------------- --------------------------

(b). min[H]

Figura 13.8 Heap Fibonacci

124

23

7 3 17

24

18

38

52

30

46

26

41

39

35

23

7 3 17

24

18

38

52

30

46

26

41

39

35

(a) Un heap Fibonacci constând din 5 arbori , ce satisfac proprietatea de heap ordonat, şi care conţine 14 noduri . Linia punctată indică lista de rădăcini. Nodul care conţine valoarea 3 este nodul minim din heap. Nodurile marcate sunt haşurate cu negru. Potenţialul acestui heap Fibonacci este 5 + 2·3 =11.

(b) O reprezentare mai complexă care arată pointerii p (săgeţile orientate în sus), fiu (săgeţile în jos), şi stâng (săgeţile laterale). Aceste detalii vor fi omise în celelalte figuri deoarece toate informaţiile prezentate aici pot fi determinate din ceea ce apare în partea (a).

Vom presupune că aplicaţiile pentru heap-uri Fibonacci nu pornesc de la nici un heap. Astfel, potenţialul iniţial este 0 şi conform ecuaţiei (1.2.3) , potenţialul este nenegativ la orice moment de timp ulterior. O margine superioară a costului amortizat total este şi o margine superioară a costului actual pentru secvenţa de operaţii.

Grad maxim

În secţiunea următoarea vom efectua o analiză amortizată care se va baza pe cunoaşterea unei margini superioare D(n) a gradului maxim al oricărui nod dintr-un arbore Fibonacci având n noduri. Atunci când avem doar operaţii de interclasare pe heap-uri D(n)= [lg n]. În secţiunea 1.3 vom arăta că, dacă

includem şi operaţiile DESCREŞTE-CHEIE şi ŞTERGE, D(n) =O(lg n). 13.5 Operaţii cu heap-uri interclasabile

În această secţiune vom descrie şi analiza operaţiile heap-urilor interclasabile precum şi implementări pe heap-uri Fibonacci. Dacă se au în vedere doar aceste operaţii - CREAZĂ-HEAP, ÎNSEREAZĂ, MINIM, EXTRAGE-MIN, REUNEŞTE - fiecare heap Fibonacci este o colecţie de arbori binomiali "neordonaţi". Un arbore binomial neordonat este asemănător unui arbore binomial şi se defineşte , de asemenea, recursiv. Arborele binomial neordonat Uk constă dintr-un singur nod, iar un arbore binomial neordonat Uk constă din doi arbori binomiali neordonaţi Uk-1, rădăcina unuia din ei fiind (oricare) fiu al rădăcinii celuilalt. Astfel, avem următoarea lemă care conţine propietăţi pentru arborii binomiali neordonaţi:

Lema 13.1 Arborele binomial Uk are:

125

1. 2k noduri,2. înălţimea k,

3. exact ( ), noduri , la adâncimea i , pentru i = 0,1 ,...,k,4. gradul rădăcinii arborelui binomial Uk este k, grad mai mare decât al

oricărui alt nod. Într-o ordine oarecare, descendenţii rădăcinii sunt rădăcinile unor arbori U0,U1,...,Uk-1.

Astfel, deoarece un heap Fibonacci având n noduri este o colecţie de arbori binomiali neordonaţi, D(n) = lg n..

Ideea de bază , aplicată la definirea operaţiilor heap-urilor interclasabile pe heap-uri Fibonacci este de a întârzia anumite prelucrări cât mai mult posibil. Obţinerea unor operaţii performante poate fi în detrimentul altora. Dacă numărul arborilor unui heap Fibonacci este mic, atunci nodul minim necesar operaţiei EXTRAGE-MIN este determinat eficient. Dar, după cum se ştie pentru heap-uri binomiale, costul asigurării unui număr mic de arbori este ridicat: pentru inserarea unui nod într-un heap binomial, sau pentru reuniunea a două heap-uri binomiale , timpul de execuţie se poate ridica până la Ώ(lg n). După cum se va vedea, la inserarea unui nod nou sau la reuniunea a două heap-uri , nu vom încerca să consolidăm arborii din heap-ul Fibonacci. Consolidarea va fi lăsată în seama operaţiei EXTRAGE-MIN, operaţie care necesită găsirea nodului minim.

13.5.1 Crearea unui heap Fibonacci

Pentru a crea un heap Fibonacci vid , procedura HEAP-FIB-CREAZĂ, creează şi returnează un obiect heap Fibonacci H, cu n[H] = 0 şi min[H] = NIL; H nu conţine arbori. Deoarece t(H) = 0 şi m(H) = 0, potenţialul heap-ului Fibonacci vid este Φ(H) = 0. Costul amortizat al operaţiei HEAP-FIB-CREAZĂ este egal cu costul ei actual O(1).

13.5.2 Inserarea unui nod

126

ki

Procedura următoare inserează nodul x în heap-ul Fibonacci H, presupunând că nodul a fost alocat în prealabil şi că cheie[x] a fost de asemenea iniţializată.

HEAP-FIB-INSEREAZĂ (H,x)1. grad[x] = 02. p[x] = NIL

3. fiu[x] = NIL

4. stânga[x] = x5. dreapta[x] = x6. marcat[x] = FALS

7. concatenează lista de rădăcini care îl conţine pe x cu lista de rădăcini a lui H

8. dacă min[H] = NIL sau cheie[x] < cheie[min[H]] atunci9. min[H] = x10. Sdacă 11. n[H] = n[H] + 112. return

După iniţializarea câmpurilor nodului x în liniile 1-6 , făcându-l circular şi dublu înlănţuit, în linia 7, x este adăugat listei de rădăcini a lui H într-un timp actual O(1). Astfel, nodul x devine un arbore cu un singur nod şi care are proprietatea de ordonare de heap, deci un arbore binomial neordonat aparţinând heap-ului Fibonacci. Acest arbore nu are fii şi nu este marcat. În continuare, în liniile 8-10, este actualizat, dacă este necesar, pointerul la nodul minim din heap-ul Fibonacci H. În final, linia 11 incrementează n[H] marcând inserarea unui nod nou. Figura 13.9 prezintă inserarea nodului având cheia 21 în heap-ul Fibonacci din figura 13.8.

(a) min[H]

------ -------- ---------------- -------------------- --------------------------

127

23

7 3 17

24

18

38

52

30

46

26

41

39

35

(b) min[H]

------------------------------------------------------------------------------------------

Figura 13.9 Inserarea unui nod într-un heap Fibonacci.a) Un heap Fibonacci H.b) Heap-ul Fibonacci H după ce nodul având cheia 21 a fost inserat. Nodul devine un arbore cu proprietatea de heap şi adăugat listei de rădăcini, devenind fratele stâng al rădăcinii.

Procedura HEAP-FIB-INSEREAZĂ nu consolidează arborii din heap-ul Fibonacci. Dacă procedura HEAP-FIB-INSEREAZĂ este apelată consecutiv de k ori atunci se adaugă listei de rădăcini k arbori cu un singur nod.

Pentru a determina costul amortizat al operaţiei HEAP-FIB-INSEREAZĂ, fie H heap-ul Fibonacci dat ca intrare şi H' heap-ul Fibonacci rezultat. Atunci :

t (H') = t (H) +1m (H') = m (H)

şi creşterea potenţialului este:((t (H) + 1) + 2m (H)) - (t (H) + 2m (H)) = 1.Deoarece costul actual este O(1), costul amortizat este O(1) +1 = O(1).

13.5.3 Găsirea nodului minim

Nodul minim al unui heap Fibonacci H este dat de pointerul min (H), de unde costul actual al operaţiei este O(1). Deoarece potenţialul lui H nu se schimbă, costul amortizat al operaţiei este egal cu costul ei actual O(1).

13.5.4 Reuniunea a două heap-uri Fibonacci

Procedura următoare reuneşte heap-urile Fibonacci H1 şi H2, distrugând H1 şi H2 în timpul desfăşurării procesului.

128

723

3 17

24

18

38

52

30

46

26

41

39

35

21

HEAP-FIB-REUNEŞTE (H1,H2,H)1. Cheama HEAP-FIB-CREAZĂ(H)2. min[H] = min[H1]3. concatenează lista de rădăcini a lui H1 cu lista de rădăcini a lui H24. dacă (min[H1] = NIL ) sau (min [H2] ≠ NIL şi min[H2] < min[H2]) atunci5. min[H] = min[H2]6. Sdacă 7. n[H] = n[H1] + n[H2]8. eliberează obiectele H1 şi H29. return

Liniile 1-3 concatenează listele de rădăcini ale lui H1 şi H2 obţinându-se o listă de rădăcini nouă H . Liniile 4 şi 6 stabilesc nodul minim al lui H, iar linia 7 iniţializează n[H] cu numărul total de noduri. Obiectele H1 şi H2 sunt dealocate în linia 8, iar linia 9 returnează heap-ul Fibonacci H rezultat. Arborii heap-ului nu sunt consolidaţi, la fel ca şi în procedura HEAP-FIB-INSEREAZĂ. Potenţialul rămâne neschimbat şi anume:

Φ(H) - ( Φ(H1) + Φ(H2)) =

= (t(H) + 2m(H)) - ((t(H1) + 2m(H1)) +((t(H2) + 2m(H2))) = 0,

deoarece t(H) = t(H1) + t(H2) şi m(H) = m(H1) + m(H2). Costul amortizat al operaţiei HEAP-FIB-REUNEŞTE este astfel egal cu costul actual O(1) .

13.5.5 Extragerea nodului minim

Procesul de extragere al nodului minim este cel mai complicat dintre toate operaţiile prezentate în această secţiune. Consolidarea arborilor din lista de rădăcini este efectuată în cadrul acestei operaţii. Următorul algoritm extrage nodul minim. Algoritmul presupune că atunci când se şterge un nod dintr-o listă înlănţuită, pointerii rămaşi în listă sunt actualizaţi, dar pointerii din nodul eliminat sunt lăsaţi neschimbaţi. În algoritm se foloseşte o procedură auxiliară CONSOLIDEAZĂ care va fi prezentată în continuare.

HEAP-FIB-EXTRAGE-MIN (H,z)

129

1. z = min[H] 2. dacă z ≠ NIL atunci3. pentru fiecare fiu al lui z 4. adaugă x la lista de rădăcini a lui H5. p[x] = NIL

6. Spentru 7. şterge z din lista de rădăcini a lui H8. dacă z = dreapta [z] 9. atunci 10. min [H] = NIL

11. altfel12. min [H] = dreapta [z]13. CONSOLIDEAZĂ(H)14. Sdacă15. n[H] = n[H] –116. Sdacă17. returne

Conform figurii 13.10, procedura HEAP-FIB-EXTRAGE-MIN rupe legăturile între nodul rădăcină minim respectiv fiii săi şi şterge nodul minim din lista de rădăcini. Apoi consolidează lista de rădăcini prin înlănţuirea rădăcinilor de acelaşi grad, până când rămâne cel mult o rădăcină de fiecare grad .

Pornim în linia 1 prin reţinerea unui pointer z la nodul minim ; în final se va returna acest pointer. Dacă z = NIL atunci heap-ul Fibonacci H este vid şi prelucrarea este încheiată. În caz contrar, nodul z este şters din H în liniile 3-6 prin transformarea fiilor lui z în rădăcini şi ştergerea lui z din lista de rădăcini (linia 7). Dacă z = dreapta [z] atunci z fusese singurul nod din lista de rădăcini şi nu avusese nici un fiu, astfel încât, mai întâi, trebuie să facem heap-ul H vid. În caz contrar, stabilim pointerul min[H] în lista de rădăcini astfel încât să indice nodul minim rămas ( în acest caz, dreapta[z]) diferit de z . Figura 13.10 (b) prezintă heap-ul Fibonacci din figura 13.10 (a) după executarea instrucţiunii din linia 12.

(a) min[H]

------------------------------------------------------------------------------------------

130

723

3 17

24

18

38

52

30

46

26

41

39

35

21

(b) min[H]

------------------------------------------------------------------------------------------

(c) 0 1 2 3 A

w,x

------------------------------------------------------------------------------------------

(d) 0 1 2 3 A

w,x

------------------------------------------------------------------------------------------

131

723

17

24

18

38

52

30

46

26

41

39

35

21

723

17

24

18

38

52

30

46

26

41

39

35

21

723

17

24

18

38

52

30

46

26

41

39

35

21

(e) 0 1 2 3 A

w,x

------------------------------------------------------------------------------------------

(f) 0 1 2 3 A

x --------------------------------------------------------------------------------

w

(g) 0 1 2 3 A

x --------------------------------------------------------------------------------

w w

132

723

17

24

18

38

52

30

46

26

41

39

35

21

7

23

17

24

18

38

52

30

46

26

41

39

35

21

7

23

17

24

18

38

52

46

26

41

39

35

21

(h) 0 1 2 3 A

x ---------------------------------------------------------------------

w

(i) 0 1 2 3 A

w,x ---------------------------------------------------------------------

0 1 2 3 (j) A

w,x ---------------------------------------------------------------------

133

30

7

23

17

24

18

38

52

30

46

26

41

39

35

21

7

23

17

24

18

38

52

30

46

26

41

39

35

21

7

23

17

24

18

38

52

30

46

26

41

39

21

0 1 2 3 (k) A

w,x ---------------------------------------------------------------------

0 1 2 3 (l) A

w,x ---------------------------------------------------------------------

(m) min [H]

---------------------------------------------------------------------

134

35

7

23

17

24

18

38

52

30

46

26

41

39

35

21

7

23

17

24

18

38

52

30

46

26

41

39

35

21

7

23

17

24

18

38

52

30

46

26

41

39

35

21

Figura 13.10 Inserarea unui nod într-un heap Fibonacci.(a) Un heap Fibonacci H.(b) Situaţia obţinută după ştergerea nodului minim z din lista de rădăcini şi adăugarea la lista de rădăcini a fiilor lui z.(c)-(e) Tabloul A şi arborii după primele 3 iteraţii ale ciclului pentru din liniile 4-17 ale procedurii CONSOLIDEAZĂ. Lista de rădăcini este procesată pornind de la nodul minim şi urmând pointerii dreapta. Fiecare parte arată valorile lui w şi x la sfârşitul unei iteraţii.(f)-(h) Iteraţia următoare a ciclului pentru , cu valorile lui w şi x obţinute la sfârşitul fiecărei iteraţii a ciclului cât timp din liniile 7-15 . Partea (f) arată situaţia obţinută la prima trecere prin ciclul cât timp. Nodul cu cheia 23 a fost legat la nodul având cheia 7, nod care este acum indicat de x. În partea (g) , nodul având cheia 17 a fost legat la nodul având cheia 7, spre care încă indică x . În partea (h) , nodul având cheia 24 a fost legat la nodul având cheia 7. Deoarece A[3] nu indică nici un nod, la sfârşitul iteraţiei ciclului pentru A[3] va indica rădăcina arborelui rezultat.(i)-(l) Situaţiile obţinute după următoarele patru iteraţii ale ciclului cât timp.(m) Heap-ul Fibonacci H după reconstruirea listei de rădăcini din tabloul A şi după determinarea pointerului min[H].

Pasul următor în care reducem numărul de arbori din heap-ul Fibonacci constă în consolidarea listei de rădăcini a lui H; acesta este efectuat prin apelul CONSOLIDEAZĂ(H). Consolidarea listei de rădăcini constă din efectuarea repetată a paşilor următori, până când fiecare rădăcină din lista de rădăcini are o valoare distinctă pentru gradul său :

1. Găseşte două rădăcini x şi y din lista de rădăcini având acelaşi grad şi cheie[x] < cheie[y]

2. Înlănţuie y la x şterge y din lista de rădăcini şi include nodul y printre fiii lui x. Această operaţie este efectuată prin procedura HEAP-FIB-ÎNLĂNŢUIE. Câmpul grad[x] este incrementat, iar marcajul nodului y, dacă există, este şters.

CONSOLIDEAZĂ(H) 1. pentru i = 0 , D(n(H)) 2. A[i] = NIL

135

3. Spentru 4. pentru fiecare nod w din lista de rădăcini a lui H5. x = w6. d = grad[x]7. cât timp A[d] NIL 8. y = A[d]9. dacă cheie[x] > cheie[y] atunci10. interschimbă x y 11. Sdacă 12. HEAP-FIB-ÎNLĂNŢUIE(H,y,x)13. A[d] = NIL

14. d = d+115. Sciclu16. A[d] = x17. Spentru 18. min[H] = NIL

19. pentru i = 0, D(n[H]) 20. dacă A[I] NIL sau cheie[A[i]] < cheie[min[H]] atunci21. adaugă A[i] listei de rădăcini a lui H22. dacă min[H] = NIL sau cheie[A[i]] < cheie[min[H]] atunci23. min[H] = A[i] 24. Sdacă25. Sdacă26. Spentru 27. return

HEAP-FIB-ÎNLĂNŢUIE (H,y,x)1. şterge y din lista de rădăcini a lui H2. înlănţuie y ca fiu al lui x şi incrementează grad[x]3. marcat[y] = FALS

4. return

Procedura CONSOLIDEAZĂ foloseşte un tablou auxiliar A[0..D(n[H])]; dacă A[i] =y atunci y este o rădăcină cu grad[y] =i. Aceasta funcţionează după

136

cum urmează. În liniile 1 - 2 se iniţializează A atribuind fiecărui element valoarea NIL. Procesarea fiecărui nod w se încheie cu un nod x care poate fi , sau nu, identic cu w. Astfel, elementele tabloului A[grad[x]] sunt iniţializate cu x. În ciclul pentru din liniile 4-17 este examinat fiecare nod w din lista de rădăcini. Invariantul la fiecare iteraţie în ciclul for este că nodul x este rădăcina arborelui care conţine nodul w.

Ciclul cât timp din liniile 7-15 are predicatul invariant d = grad[x] (cu excepţia liniei 13 după cum vom vedea imediat). La fiecare iteraţie a ciclului cât timp A[d] indică o anumită rădăcină y. Deoarece d =grad[x]= grad[y], vom înlănţui x şi y. Cel care are cheia mai mică dintre x şi y devine părintele celuilalt, în urma operaţiei de înlănţuire; astfel, dacă este necesar, pointerii x şi y sunt interschimbaţi în liniile 9-11. În continuare y este legat la x prin apelul din linia 12, HEAP-FIB-ÎNLĂNŢUIE(H,y,x). În urma apelului , grad[x] este incrementat, iar grad[y] rămâne d. Deoarece nodul y nu mai este rădăcină, pointerul spre el din tabloul A este şters în linia 13. Deoarece după apelul HEAP-FIB-ÎNLĂNŢUIE valoarea grad[x] este incrementată, în linia 14 este restabilită proprietatea invariantului d = grad[x]. Ciclul cât timp este executat de atâtea ori până când A[d] = NIL, situaţie în care nu există alte rădăcini având acelaşi grad ca şi x. În linia 16 iniţializăm A[d] cu x şi efectuăm iteraţia următoarea ciclului pentru. Figurile 2.2 (c) - (e) prezintă tabloul A şi arborii rezultaţi după primele trei iteraţii ale ciclului pentru din liniile 4-17. La iteraţia următoare a ciclului pentru sunt realizate trei legături; rezultatele lor se pot vedea în figurile 2.2 (f) - (h). Figurile 2.2 (i)-(l) prezintă rezultatele următoarelor patru iteraţii ale ciclului pentru.

Rămâne să definitivăm operaţiile începute. După execuţia ciclului pentru din liniile 4–17, linia 18 videază lista de rădăcini iar în liniile 19–26 aceasta este reconstruită. Heap-ul Fibonacci rezultat este redat în figura 2.2 (m). După consolidarea listei de rădăcini, operaţiile efectuate de HEAP-FIB-EXTRAGE-MIN se încheie cu decrementarea valorii n[H] în linia 15 şi returnarea în linia 17 a unui pointer la nodul şters z.

Observăm că dacă anterior apelului HEAP-FIB-EXTRAGE-MIN toţi arborii din heap-ul Fibonacci sunt arbori binomiali neordonaţi, atunci arborii rezultaţi după apel sunt de asemenea binomiali neordonaţi. Arborii sunt modificaţi în două feluri. În primul rând, în liniile 3-6 din HEAP-FIB-EXTRAGE-MIN, fiecare fiu x al lui z devine o rădăcină şi fiecare arbore nou va fi un arbore binomial neordonat. În al doilea rând, arborii sunt înlănţuiţi prin HEAP-FIB-ÎNLĂNŢUIE doar dacă sunt de acelaşi grad. Deoarece înainte de crearea legăturilor toţi arborii sunt binomiali şi neordonaţi, cei doi arbori cu

137

k fii au fiecare o structură de tip Uk. Rezultă că arborele obţinut va avea o structură Uk+1.

Acum vom arăta că extragerea nodului minim dintr-un heap Fibonacci având n noduri are un cost amortizat O(D(n)). Fie H heap-ul Fibonacci pentru care aplicăm operaţia HEAP-FIB-EXTRAGE-MIN.

Calcularea costului actual al extragerii nodului minim poate fi făcută după cum urmează. O contribuţie O(D(n)) provine din faptul că nodul minim are cel mult D(n) fii care sunt procesaţi de HEAP-FIB-EXTRAGE-MIN şi din calculele efectuate în liniile 1-3 şi 18-26 în procedura CONSOLIDEAZĂ. Ne rămâne să analizăm contribuţia din partea ciclului pentru din liniile 4-17. După apelul procedurii CONSOLIDEAZĂ lungimea listei de rădăcini poate fii cel mult D(n)+t(H)-1, deoarece constă din nodurile iniţiale ale listei în număr de t(H), mai puţin nodul rădăcină extras şi plus numărul fiilor nodului extras care poate fi cel mult D(n). De fiecare dată, în ciclul cât timp din liniile 6-16 una din rădăcini este înlănţuită cu alta, astfel, calculul total efectuat de ciclul pentru este cel mult proporţional cu D(n)+t(H). Astfel, timpul total de execuţie este O(D(n)+t(H)).

Înaintea extragerii nodului minim, potenţialul este t(H)+2m(H), iar după extragere acesta este cel mult egal cu (D(n)+1)+2m(H), deoarece rămân cel mult D(n)+1 rădăcini şi nu se marchează noduri în timpul efectuării operaţiilor. Astfel, costul amortizat este cel mult :

O(D(n)+t(H))+((D(n)+1)+2m(H))-(t(H)+2m(H))=

= O(D(n))+O(t(H))-t(H)=

=O(D(n)),

deoarece putem scala unităţile de potenţial pentru a depăşi constanta ascunsă în O(t(H)). Intuitiv, costul efectuării fiecărei legături se datorează reducerii potenţialului în urma înlănţuirilor care micşorează cu 1 numărul de rădăcini.

13.6 Mărginirea gradului maxim

Pentru a demonstra că timpul amortizat al operaţiilor HEAP-FIB-EXTRAGE-MIN şi HEAP-FIB-ŞTERGE este O(lg n), trebuie să arătăm că marginea superioară D(n) a gradului oricărui nod dintr-un heap Fibonacci având n noduri este O(lg n). Atunci când toţi arborii din heap-ul Fibonacci sunt arbori binomiali neordonaţi, D(n) = [lg n]. Totuşi, tăierile care se

138

efectuează în HEAP-FIB-DESCREŞTE-CHEIE pot genera arbori care nu respectă proprietăţile arborilor binomiali neordonaţi. În această secţiune vom arăta că prin înlăturarea unui nod de la părintele lui, dacă acesta pierde doi fii,

atunci D(n) = O(lg n). Mai precis, vom arăta că D(n) < [log n], unde = (1 + )/2.

Ideea de bază a analizei este următoarea. Pentru fiecare nod x dintr-un heap Fibonacci fie dim(x) numărul nodurilor subarborelui cu rădăcina x, incluzându-l şi pe x. (Să observăm că x nu trebuie să fie în lista de rădăcini - poate fi orice nod.) Vom arăta că dim(x) depinde exponenţial de grad[x]. Să reţinem că grad[x] este actualizat pentru a exprima cu precizie gradul lui x.

Lema 13.2 Fie x un nod oarecare dintr-un heap Fibonacci şi presupunem că grad[x]= k. Notăm cu y1, y2, … ,yk, fiii lui x în ordinea în care au fost legaţi la x, de la cel mai devreme la cel mai recent.

Atunci, grad[y1] > 0 şi grad[yi] > i-2 pentru i = 2,3,…,k..

Demonstraţie. Este evident că grad[y1]>0.Pentru i > 2, observăm că atunci când yi a fost legat la x, celelalte

noduri y1,y2,…, yi-1 erau deja fii ai lui x, astfel că grad[x] > i-1. Nodul yi este legat la x numai dacă grad[x] = grad[yi], de unde rezultă că la acel moment are loc de asemenea grad[yi] > i-1. Din acel moment nodul yi poate pierde cel mult un fiu, deoarece, dacă şi-ar fi pierdut ambii fii, ar fi fost tăiată legătura sa cu x. În concluzie, grad[yi] > i-2.

Ajungem, în sfârşit, la acea parte a analizei noastre care justifică numele de “heap-uri Fibonacci”. După cum bine ştim, pentru k = 0,1,2,…, al k-lea număr Fibonacci este definit prin relaţia de recurenţă

0 dacă k = 0 Fk = 1 dacă k = 1 Fk--1 + Fk-2 dacă k > 2

Lema următoare oferă un alt mod de a exprima Fk.

Lema 13.3 Pentru orice k > 0, k

Fk+2 = 1+ Fi .

i =0

139

{

Demonstraţie. Demonstraţia este prin inducţie după k.

Dacă k = 0,

0

1 + Fi = 1+ F0 = 1 + 0 = 1 = F2

i =0 k-1

Presupunând acum că are loc ipoteza inducţiei, Fk+1 = 1 + Fi , avem:i =0

k-1 k

Fk+2 = Fk + Fk+1 = Fk + ( 1 + Fi ) = 1 + Fi . i=0 i=0

Lema următoare şi corolarul ei completează analiza. Lema foloseşte inegalitatea:

Fk+2 > k,unde este raportul de aur definit prin ecuaţia Fk+2 = Fk + Fk+1 ca fiind :

= ( 1 + )/2 = 1.61803… .

Lema 13.4 Fie x un nod oarecare dintr-un heap Fibonacci şi fie k =grad[x].

Atunci

dim(x)> Fk+2 > k , unde = ( 1 + )/2 = 1.61803… .

Demonstraţie. Notăm cu sk valoarea minimă posibilă pentru dim(z) pentru toate nodurile z care au proprietatea grad[z] = k. Evident că s0 = 1, s1 = 2, s2 = 3. Numărul sk este cel mult dim(z). Ca şi în lema 4.1, notăm y1, y2,… ,yk fiii lui x în ordinea în care au fost legaţi la x.Pentru a calcula o margine inferioară pentru dim(x) adunăm 1 pentru x şi 1 pentru primul fiu y1 (pentru care dim(y1)>1) şi aplicăm apoi lema 4.1 pentru ceilalţi fii. Avem astfel:

k

dim(x) > sk > 2 + s i-2 . i=2

140

Arătăm acum, prin inducţie în raport cu k, faptul că sk >Fk+2, pentru orice k nenegativ.

Cazurile de bază pentru k = 0 şi k =1 sunt evidente. Pentru pasul inductiv, presupunem că k > 2 şi si > Fi+2, pentru i = 0,1,

…,k-1. Avem: k k k

sk > 2 + si-2 > 2 + Fi = 1 + Fi = Fk+2. i=2 i=2 i=0

Ultima egalitate rezultă din lema 4.2.Am arătat astfel că dim(x) > sk > Fk+2 > k .

Corolarul 13.1 Gradul maxim D(n) al oricărui nod dintr-un heap Fibonacci având n noduri, este O(lg n).

Demonstraţie. Fie x un nod oarecare al unui heap Fibonacci cu n noduri şi fie k = grad[x]. Din lema 4.3 obţinem că n > dim(x) > k .

Logaritmând în baza obţinem k < log n. De fapt k < [log n] deoarece k este întreg.

Gradul maxim D(n) al oricărui nod este astfel O(lg n).

Rezolvarea unor probleme dintre cele propuse.

Rezolvări la capitolul 1. Structuri elementare de date

1. Algoritm de intrare intr-o coada circulara alocată intr-un vector x cu n elemente, cu faţa în f şi sfârşitul în s.

Intrare_coada_circulara (x,f,s,n)Daca (s = n şi f=1) sau (s=f-1) atunci ‘DEPASIRE’

141

Altfels = s + 1daca s>n atunci s=1sdacax [ s ] = inf

sdaca return

2. Algoritm de iesire dintr-o coada circulara alocată intr-un vector x cu n elemente, cu faţa în f şi sfârşitul în s.

Iesire_coada_circulara(x,f,s,n)Daca s = f atunci ‘COADA VIDA’ Altfel

Inf = x [ f ] ;f= f+1Daca f>n atunci f=f+1sdaca

sdacareturn

3. Doua stive alocate in acelasi vector :a) Disciplina de umplere:

Presupunem ca la un moment dat sirul nostru va arata astfel:V[1

]V[2

]V[3

]…

V[k1]

V[k2] … V[n]

Unde până la k1 avem prima stivă, iar de la k2 până la n avem cea de-a doua stivă.

b) Algoritmi de intrare-iesire a informaţiei a pentru stiva 1:

Intrare_stiva1(V,n,k1,a)Daca (k1 = n sau k1=k2-1) atunci ‘DEPASIRE’

altfelk1 = k1 + 1 ;v[k1] = a ;

sdacareturn

142

Iesire_stiva1(V,n,k1,a)Daca k1 = 0 atunci ‘STIVA VIDA’

altfela = v[k1]k1=k1-1

sdacareturn

c) Algoritmi de intrare-iesire a informaţiei a pentru stiva 2:

Intrare_stiva2(V,n,k2,a)Daca (k2 = k1+1 sau k2+n) atunci ‘DEPASIRE’

altfelk2 = k2 - 1 ;v[k2] = a;

sdacareturn

Iesire_stiva2(V,n,k2,a)Daca k2 = n atunci ‘STIVA VIDA’

altfela = v[k2]k2 = k2 + 1 ;

sdacareturn

4. Matrice patratica de ordin n in care toate elementele deasupra diagonalei principale sunt egale cu 0

d) Cate elemente pot fii diferite de 0? :

e) Aranjarea elementelor pe linii intr-o coloana

Matricea :

A[1,1]

0 0 … 0

A[2,1]

A[2,2]

0 … 0

143

A[3,1]

A[3,2]

A[3,3]

… 0

… … … … …A[n,1]

A[n,2]

A[n,3]

… A[n,n]

Sirul:

A[1,1]

A[2,1]

A[2,2]

A[3,1]

A[3,2]

A[3,3]

…A[n,1

]A[n,2] A[n,3] …

A[n,n]

B[1] B[2] B[3] B[4] B[5] B[6] …B[k-n]

B[k-(n-1)]

B[k-(n-2)]

… B[k]

f) Formula pentru k:

g) Formulele pentru i si j:

Mai rămâne să o faceţi.h) Algoritm de transformare din matrice in sir:

Transformare_Matrice_in_Sir(a,n,B) k = 0 ;

Pentru i = 1 la n Pentru j = 1 la i

k = k + 1B[ k ] = a [ i , j ] ;

Spentru

Spentru

Return

144

i) Algoritm de calcul pentru produsul normal este:

Prod_mat(A1,A2,n,MA)Pentru i=1,n

Pentru j=1,nMA[i,j]=0Pentru k=1,n

MA[i,j]=MA[i,j]+A1[i,k]*A2[k,j]Spentru

spentruspentrureturnPentru a găsi algoritmul dorit trebuie să înlocuim:A1[i,j] cu B1[(i(i-1)/2+j]A2[i,j] cu B2[(i(i-1)/2+j] şiMA[i,j] cu MB[(i(i-1)/2+j].

Rezolvări la capitolul 2.1. A=0.02 secunde Viteza de revoluţie pe secundă va fi R=7200/60= 120 R=1/120=0.0083 secunde R/2= 0.00415 L/D=1000/80000=0.010205 Deci: T=0.02+0.00415+0.010205=0.034355 secunde 2. Timpul total de citire a fişierului= 0.00415*8+0.010205*8000=81.6732, iar

T=81.67/8000=0.0102 secundeRezolvări la capitolul 3.1. Modelul reţea este un model care conţine înregistrări, date şi relaţii 1 la mai mulţi între înregistrări.

Reţelele sunt un mod natural de a reprezenta legăturile care se stabilesc între obiecte. În general reţelele sunt reprezentate cu ajutorul unei structuri matematice numită graf orientat.

La modelul reţea sunt doar două structuri fundamentale si anume : - îmregistrarea sau record (o colecţie de date logic legate între ele) - legătura sau set (o relaţie de unu-la-mai-multe sau unu-la unu între

două lnregistrări). 2. Să considerăm relaţia Carte la Autor.

145

Aeastă relaţie este, evident, mulţi la mulţi. Ea se transformă în:

Înregistrare de lagătură

Rezolvări la capitolul 4.1. Ceea ce se transcrie în stuctura externă modelul ierarhic este o arboresceţă grafică, un graf orientat, conex fără cicluri.2.Să considerăm relaţia Carte la Autor.

Aeastă relaţie este, evident, mulţi la mulţi.Aceeaşi relaţie folosită şi la problema 2. cap 3. se va transforma:

În două relaţii 1 la mulţi în care dublarea lui ‘Carteautor’ se face în mod util.

Rezolvări la capitolul 5.

1. R1=titlu(d_domeniu="stiinta" (carte►◄domenii))

2. R2=d_edit(oras="brasov" (edituri))

3. R3=titlu(nume_aut="Ion Ion" (carte►◄carteaut►◄ autor))

4. R4=titlu(nume_aut="Ion Ion" (carte►◄carteaut►◄ autor))\ titlu(nume_aut !="Ion Ion"

(carte►◄carteaut►◄ autor))Rezolvări la capitolul 6.

146

Carte Autor

Carte

CarteId AutorId

Autor

Carte Autor

Carte Carteautor Carteautor Autor

1.INORD_IT(RAD) STIVA = {Stiva este vidă} P=RAD {P conţine nodul care se viziteză} Repetă

RepetăDacă P ’ * ‘ atunci{Parcurgere pe stânga}

P=>STIVA P=LS(P) Ciclează

altfelEXIT

Sdacasciclu{Parcurgere pe dreapta} Dacă STIVA = atunci EXIT

Altfel P<=STIVA ; Scrie INFO(P);P= LD(P)

Sdaca Sciclu Return 3. Arborele va fi:

Rezolvări la capitolul 7.3. Fiul stâng al nodului i se găseşte în 2i deci algoritmul va fi:

list_fara_stâng(a,n)pentru i=1,n

daca a[i] ‘*’ atuncidaca ((2i < n) si (a[2i] ‘*’)) atunci

147

A

B C

D

E

F

G

H

scrie a[i]sdaca

sdacaspentrureturn

Rezolvări la capitolul 8. Arbori binari de căutare.1. Exercitiul 1. (Determinarea nodului cu cheie maximă)

MAX_BIN (Rad, Max)x = RadAtat timp cat LD(x) ≠ Nil x = LD(x)Max = KEY(x)sciclu

Return

2. Exercitiul 2. (determinarea predecesorului)PRED_BIN(x, y)

Daca LS(x) ≠ Nil atunciCheama MAX_BIN(LS(x), y)Return

sdacay = P(x)Atat timp cat y ≠ Nil si KEY(y)>KEY(x) executa

y = P(y)sciclu

Return

3. Exercitiul 3. (Cautarea binara recursiva)CAUT_BIN_REC(Rad, k, Rez,x)

x = RadDaca x = Nil sau k = KEY(x) atunci

Return sdacaDaca k < KEY(x) atunci

Cheama CAUT_BIN_REC(LS(x), k, Rez,x)Return

altfelCheama CAUT_BIN_REC( LD(x), k, Rez,x)Return

148

sdaca

Rezolvări la capitolul 9.1. h(k)=[m*((k*A) mod 1)] pentru A=(5-1)/2=0.6180339m=1000(k*A) mod 1 pentru k=61 va fi 0.700

pentru k=62 va fi 0.318pentru k=63 va fi 0.936pentru k=64 va fi 0.554pentru k=65 va fi 0.172

Deci locaţiile vor fi respectiv 700, 318, 936, 554, 172. 2. Cu verificarea liniară se obţine această secvenţă:

Cu verificare patratică cu funcţia h(k,i)=((k mod 11)+i+3i2) mod 11) se obţine:

149

10

23

10

23

3110

23

4

3110

23

415

3110

23

415

28

3110

23

4151728

3110

23

4151728

311088

23

415172859311088

23

3110

23

4

311010

23

10

23

4

153110

23

4

28

153110

2317

4

28

153110

882317

4

28

153110

882317

4

2859153110

Rezolvări la capitolul 10.

Pentru a insera cheia 60:- rădăcina e neplină- al doilea fiu al ei este tot neplin- al treilea fiu al acestuia din urmă este plin deci va trebui să fie rupt:Zona care ne interesează va arăta aşa:

Pe calea îngroşată se va face inserarea. După inserare aceeaşi zonă va arăta:

150

35

9 18 44 53 18

3 4 12 15 18

23 27 30 18

38 41 18

47 50 18

56 61 64 67 70 18

1 2 18

4 5 18

7 8 18

10 11

13 14

16 1719 21

25 26

28 29

31 33

36 37

39 40

42 43 45 46

48 49

51 5254 55

71 72

57 58

62 63

65 66

68 69

44 53 54

38 41 47 50 56 61 67 70

54 55 57 58 62 63

44 53 54

38 41 47 50 56 61 67 70

BIBLIOGRAFIE: [1] CORMEN T.H, LEISERSON C., RIVEST R. INTRODUCERE IN ALGORMI AGORA,CLUJ 1999[2] TOMESCU I.D. DATA STRUCTURES ED.UNlV BUCURESTI [3] IACOB P. BAZE SI STRUCTRI DE DATE notiţe de curs UNIV BRASOV 1998

151

54 55 57 58 60 62 63

structuri de date

Documents