Lectia 7. Alte tipuri de arbori

Arbori AVL

Arborii AVL (Adelson-Veliskii şi Landis) elimină neajunsul major al arborilor binari: faptul că viteza de căutare depinde de ordinea în care sunt introduse cheile în arbore. Arborii AVL permit obţinerea unei viteze de căutare constante de complexitate O(n log₂n) prin garantarea faptului că arborele este echilibrat la orice moment.

Structura unui nod este cea a unui nod de arbore binar la care se mai adaugă un câmp numit BF (Balance Factor) care reprezintă diferenţa dintre înălţimea subarborelui drept (RH) şi înălţimea subarborelui stâng (LH). Fiecare nod dintr-un AVL are proprietatea că înălţimea subarborelui stâng diferă de înălţimea subarborelui drept cu cel mult o unitate, deci BF va avea una din valorile -1, 0 sau 1.

Adăugarea şi ştergerea nodurilor se face la fel ca în cazul arborilor binari de căutare. După adăugarea/ştergerea unui nod, se recalculează BF-ul pentru nodurile arborelui. Exemplu:

Dacă în urma unei operaţii de adăugare sau ştergere arborele nu mai este echilibrat (BF Ï {-1,0,1}), acesta trebuie echilibrat. Echilibrarea în cazul arborilor AVL se face prin intermediul operaţiei de rotire la stânga (BF>1) sau la dreapta (BF<1). Pivotul în jurul căruia se face rotirea este cel mai de jos nod care are BF Ï {-1,0,1}. Procedeul de rotire continuă până în momentul în care arborele redevine echilibrat.

Rotirea se face după modelul următor:

1. rotire la dreapta

2. rotire la stânga

Căutarea în arborii AVL se face la fel ca în arborii binari de căutare.

Arbori B

Arborii B (de la Balanced) sunt arbori de căutare echilibraţi proiectaţi pentru lucrul cu volume foarte mari de date (stocate pe suporturi de memorie externă).

Proprietăţile definitorii ale arborilor B sunt:

1. Toate nodurile au următoarele câmpuri:

a. n – numărul de chei stocate în nod

b. k₁,…,k_n – cheile stocate în nod cu proprietatea k₁<k₂<…<k_n

c. c₁,…,c_n+1 – pointeri la subarbori

2. Toate cheile din subarborele indicat de c_i sunt cuprinse între k_i-1<k_i; cheile din subarborele indicat de c₁ sunt mai mici decât k₁, iar cele din subarborele indicat de c_n+1 sunt mai mari decât k_n

3. Toate nodurile frunză se află la acelaşi nivel h

4. Fiecare arbore B are asociat un grad t>2. Toate nodurile, cu excepţia rădăcinii trebuie să aibă între t-1 şi 2t-1 noduri

Cele două avantaje majore ale arborilor B care îi recomandă pentru folosirea în situaţiile în care este necesară prelucrarea unui volum mare de date sunt:

· permite citirea mai multor chei la un singur acces la disc (gradul t este ales astfel încât dimensiunea unui nod corespunde dimensiunii unei pagini de disc)

· necesită accesarea a foarte puţine pagini pentru a efectua o căutare ()

Principalele operaţii care se efectuează pe un astfel de arbore sunt căutarea, adăugarea de chei şi ştergerea de chei.

Căutarea se face similar cu căutarea într-un arbore binar după următorul algoritm:

Adăugarea unei chei se face recursiv printr-o singură parcurgere în următorii paşi:

1. Dacă nodul rădăcină este plin (are 2t-1 chei), atunci se descompune.

2. Se porneşte procedura recursivă care parcurge arborele ca la căutare şi execută următoarele acţiuni pentru fiecare nod:

a. Dacă nodul este nod frunză se inserează cheia.

b. Dace nu este nod frunză:

i. Dacă nodul copil este plin se descompune.

ii. Se apelează procedura pentru nodul copil.

Operaţia de descompunere a unui nod cu 2t-1 chei presupune găsirea elementului median al nodului, mutarea acestuia în nodul părinte sau crearea unui nod nou în cazul rădăcinii şi descompunerea nodului iniţial în două noduri cu t-1chei. Exemplu de descompunere:

Se observă că toate inserările se fac într-un nod frunză, iar arborele creşte în sus, de la rădăcină, prin intermediul operaţiei de descompunere.

Pentru exemplificare vom considera următorul arbore B de grad t=2 (fiecare nod cu excepţia rădăcinii va avea între 2 şi 5 chei) cu două nivele:

Ştergerea unei chei se face similar cu adăugarea. Păstrarea proprietăţilor arborelui B în urma ştergerii unei chei se face prin două mecanisme:

· coborârea unei chei din nodul părinte/fiu în cazul în care acesta are cel puţin t chei sau este nodul rădăcină

· recompunerea nodului rădăcină în situaţia în care nodul rădăcină are 1 cheie şi nodurile copil au câte t-1 chei (astfel se realizează scăderea înălţimii arborelui)