Arbori

Studiul arborilor ca structuri ierarhice de date și al operațiilor specifice acestora.

Arborele — definiții și proprietăți fundamentale

Un arbore este un graf neorientat conex și fără cicluri. Definițiile echivalente sunt teren de grilă — un graf cu n vârfuri este arbore dacă îndeplinește oricare două dintre proprietățile: este conex, nu are cicluri, are exact n-1 muchii. Oricare două le implică pe a treia.

Alte caracterizări echivalente care se cer: între oricare două vârfuri există exact un lanț elementar; graful este conex minimal (eliminarea oricărei muchii îl deconectează) și fără cicluri maximal (adăugarea oricărei muchii creează exact un ciclu).

Un arbore cu rădăcină este un arbore în care un vârf este desemnat rădăcină; astfel apare o ierarhie cu vocabular propriu:

• tată (părinte) și fiu (descendent direct) — vecinul dinspre rădăcină, respectiv dinspre frunze;
• frați — fii ai aceluiași tată;
• frunză (nod terminal) — nod fără fii;
• nivelul (adâncimea) unui nod — lungimea drumului de la rădăcină la el (rădăcina pe nivelul 0 în majoritatea manualelor; unele numără de la 1 — la examen se citește convenția din enunț!);
• înălțimea arborelui — nivelul maxim.

O pădure este o mulțime de arbori — un graf fără cicluri, nu neapărat conex; o pădure cu n vârfuri și k componente are n-k muchii.

Greșeala clasică: a crede că orice graf cu n-1 muchii e arbore. Fals — n-1 muchii pot forma un ciclu plus vârfuri izolate; e nevoie și de conexitate (sau de absența ciclurilor).

Arbori binari — structură și reprezentare

Un arbore binar este un arbore cu rădăcină în care fiecare nod are cel mult doi fii, iar fii sunt etichetați: subarbore stâng și subarbore drept. Distincția stânga/dreapta contează: doi arbori cu aceleași noduri dar cu un fiu mutat din stânga în dreapta sunt arbori binari diferiți.

Tipuri speciale care apar la teorie:

• arbore binar complet (plin) — fiecare nod are 0 sau 2 fii și toate frunzele sunt pe același nivel; pe nivelul k se află 2^k noduri, iar un astfel de arbore de înălțime h are 2^(h+1) - 1 noduri în total;
• arbore binar aproape complet — toate nivelurile sunt pline cu excepția eventual a ultimului, completat de la stânga la dreapta (structura folosită de heap).

Proprietate de calcul frecventă: un arbore binar cu n noduri are înălțimea cel puțin log2(n) (rotunjit în jos) — cazul echilibrat — și cel mult n-1 — cazul degenerat, când arborele devine practic o listă înlănțuită.

Reprezentări în memorie:

• cu referințe descendente: fiecare nod reține informația plus adresele (sau indicii) fiului stâng și fiului drept; absența unui fiu se marchează cu o valoare convențională (NULL sau 0);
• secvențial (în vector), pentru arbori aproape compleți: rădăcina pe poziția 1, iar pentru nodul de pe poziția i, fiul stâng este pe poziția 2i, fiul drept pe 2i+1, iar tatăl pe i div 2 (numerotare de la 1);
• vectorul de tați: t[i] = tatăl nodului i, cu 0 pentru rădăcină — reprezentare comună cu arborii oarecare, cerută des la subiecte.

Parcurgerile arborelui binar

Cele trei parcurgeri în adâncime ale unui arbore binar diferă prin momentul vizitării rădăcinii — R = rădăcină, S = subarbore stâng, D = subarbore drept:

• preordine (RSD): rădăcină, apoi subarborele stâng, apoi cel drept;
• inordine (SRD): subarborele stâng, rădăcina, subarborele drept;
• postordine (SDR): subarborele stâng, subarborele drept, rădăcina la final.

Toate trei se scriu natural recursiv: funcția se autoapelează pe fiul stâng și pe fiul drept, iar poziția instrucțiunii de afișare între cele două apeluri decide tipul parcurgerii. Trucuri de verificare rapidă la grile: în preordine primul element afișat este rădăcina; în postordine ultimul element este rădăcina; în inordine, la un arbore binar de căutare, elementele apar sortate crescător.

Există și parcurgerea pe niveluri (în lățime): se vizitează nodurile nivel cu nivel, de la stânga la dreapta, folosind o coadă — analogul BFS din grafuri.

Problemă tipică de subiect: reconstituirea arborelui din două parcurgeri. Din preordine + inordine (sau postordine + inordine) arborele se reconstruiește unic: primul element din preordine este rădăcina, care împarte inordinea în subarborele stâng și cel drept, apoi se repetă recursiv. Din preordine + postordine, în general, arborele nu este unic determinat — capcană de teorie.

Greșeala frecventă de execuție: la parcurgerea manuală, elevii vizitează rădăcina și fiii direct, uitând că întreg subarborele stâng se epuizează înainte de a trece mai departe. Parcurgerea se face pe subarbori, nu pe noduri individuale.

Arbori binari de căutare

Un arbore binar de căutare (ABC) este un arbore binar în care, pentru fiecare nod: toate valorile din subarborele stâng sunt mai mici decât valoarea nodului, iar toate valorile din subarborele drept sunt mai mari. Condiția se aplică întregilor subarbori, nu doar fiilor direcți — un nod din subarborele stâng aflat la două niveluri distanță tot trebuie să fie mai mic decât strămoșul; verificarea doar a relației tată-fiu este eroarea clasică de validare.

Consecința fundamentală: parcurgerea în inordine a unui ABC produce valorile în ordine crescătoare. Aceasta este și metoda standard de a verifica dacă un arbore binar este ABC.

Căutarea unei valori pornește din rădăcină: dacă valoarea căutată e mai mică, se coboară în stânga; dacă e mai mare, în dreapta; dacă e egală, s-a găsit. Pe un arbore echilibrat, drumul are lungimea O(log n) — la fiecare pas se elimină jumătate din noduri, exact ca la căutarea binară în vector sortat.

Inserarea urmează același drum și adaugă noul nod ca frunză, în poziția unde căutarea a eșuat.

Cazul degenerat, cerut la teorie: dacă valorile se inserează în ordine crescătoare (sau descrescătoare), arborele devine un lanț cu înălțimea n-1, iar căutarea degradează la O(n) — avantajul față de lista liniară dispare complet. Forma ABC-ului depinde deci de ordinea inserării, nu doar de mulțimea valorilor.

La ștergere, cazul interesant este nodul cu doi fii: valoarea lui se înlocuiește cu cea mai mare valoare din subarborele stâng (predecesorul în inordine) sau cu cea mai mică din subarborele drept (succesorul), apoi se șterge acel nod, care are cel mult un fiu.

Heap-ul și arborii oarecare

Heap-ul (max-heap) este un arbore binar aproape complet în care fiecare nod are valoarea mai mare sau egală decât valorile fiilor săi — proprietatea de heap. Consecință imediată: maximul se află în rădăcină. În min-heap relația e inversă și rădăcina ține minimul.

Atenție la confuzia cu ABC: heap-ul ordonează doar pe verticală (tată față de fii); între fiul stâng și fiul drept nu există nicio relație de ordine, iar parcurgerea în inordine a unui heap NU produce un șir sortat.

Fiind aproape complet, heap-ul se memorează într-un vector: fiii nodului i sunt 2i și 2i+1 (numerotare de la 1). Operațiile de bază, ambele O(log n):

• inserarea: noul element se pune pe prima poziție liberă (ultima din vector) și urcă prin interschimbări cu tatăl cât timp încalcă proprietatea de heap (cernere în sus);
• extragerea maximului: rădăcina se scoate, ultimul element trece în rădăcină și coboară, schimbându-se mereu cu fiul cel mai mare, până se reface proprietatea (cernere în jos).

Heap-ul este implementarea standard a cozii de priorități și stă la baza sortării HeapSort, cu complexitate O(n log n) garantată.

Arborii oarecare (fiecare nod poate avea oricâți fii) se reprezintă cel mai des prin vectorul de tați: t[i] = tatăl nodului i, iar pentru rădăcină t[i] = 0. Prelucrări cerute la examen: rădăcina este nodul cu t[i] = 0; frunzele sunt nodurile care nu apar ca valoare în vector; numărul fiilor nodului k este numărul aparițiilor lui k în vector; drumul de la un nod la rădăcină se obține urcând din tată în tată. O alternativă de reprezentare este transformarea în arbore binar prin convenția fiu stâng — primul fiu, fiu drept — următorul frate.

Test — 6 întrebări ca la examen