4 tipuri de arbori în structura datelor explicate: proprietăți și aplicații

Ce este un arbore în structura de date?

Un arbore este un tip de structură de date care reprezintă date ierarhice. Are o structură neliniară constând din noduri conectate prin muchii. Printre celelalte tipuri de structuri de date care efectuează operații într-o structură de date liniară, complexitatea crește odată cu creșterea dimensiunii datelor. Cu toate acestea, structura de date arborescentă oferă acces mai rapid la date care sunt neliniare. Disponibilitatea diferitelor tipuri de structuri de date și a algoritmilor asociați acestora, performanța sarcinii a devenit un mod ușor și eficient.

Câteva terminologii asociate cu arbori în structura datelor sunt:

• Nod : nodul este o entitate dintr-o structură de date arborescentă care conține o cheie sau o valoare și pointeri către nodurile sale secundare.
• Nod copil : Un nod copil este descendentul oricărui nod.
• Nodurile frunză: nodurile care nu au niciun nod copil și sunt nodul cel mai de jos dintr-un arbore. Ele sunt numite și noduri externe.
• Rădăcină : este punctul cel mai de sus al unui copac.
• Nod intern : Nodul care are cel puțin un nod copil.
• Marginea: o margine se referă la conexiunea dintre oricare două noduri dintr-un arbore.
• Înălțimea unui nod: numărul de margini de la nod până la cea mai adâncă frunză.
• Adâncimea unui nod : Numărul de muchii de la rădăcină la nod.
• Înălțimea unui arbore : Înălțimea nodului rădăcină.
• Gradul unui nod : Numărul total de ramuri la acel nod.
• Pădure: O colecție de copaci disjunși.

Tipuri de arbori

1. Arbore binar

Arborele binar este un tip de structură de date arborescentă în care fiecare nod părinte are maximum două noduri copil. După cum sugerează și numele, binar înseamnă două, prin urmare, fiecare nod poate avea 0, 1 sau 2 noduri. O structură de date din arbore binar este prezentată în Figura 1. Nodul 1 din arbore conține doi pointeri, câte unul pentru fiecare nod copil. Nodul 2 are din nou câte două pointeri pentru cele două noduri copil. În timp ce nodurile 3, 5 și 6 sunt noduri frunză și, prin urmare, au pointeri nuli atât pe părțile din stânga cât și din dreapta.

Figura 1: O reprezentare a unui arbore binar ( https://www.javatpoint.com/binary-tree ).

Proprietățile unui arbore binar

• Numărul maxim de noduri la fiecare nivel al lui I este 2 i .
• Înălțimea arborelui din Figura 1 este 3, ceea ce înseamnă că numărul maxim de noduri va fi (1+2+4+8) =15.

• La înălțimea h, numărul maxim de noduri posibil este (20 + 21 + 22+….2h) = 2h+1 -1.

• La înălțimea h, numărul minim de noduri posibil este egal cu h+1.

• Un număr minim de noduri va reprezenta un arbore cu înălțime maximă și invers.

Chiar și arborii binari pot fi împărțiți în următoarele tipuri de arbori:

• Arborele binar complet: este un tip special de arbore binar. În această structură de date arborescentă, fiecare nod părinte sau un nod intern are fie doi copii, fie niciun nod copil.
• Arborele binar perfect: în acest tip de structură de date arborescentă , fiecare nod intern are exact două noduri copil și toate nodurile frunză sunt la același nivel.
• Arborele binar complet: Seamănă cu cel al arborelui binar complet, cu câteva diferențe.
• Fiecare nivel este complet umplut.
• Nodurile frunzelor se înclină spre stânga copacului.
• Nu este o cerință ca ultimul nod frunză să aibă fratele potrivit, adică un arbore binar complet nu trebuie să fie un arbore binar complet.
• Arborele degenerat sau patologic: Acești copaci au un singur copil fie la stânga, fie la dreapta nodului părinte.
• Arborele binar deformat: Este un arbore patologic sau degenerat în care arborele este dominat fie de nodurile din stânga, fie de nodurile din dreapta. Prin urmare, există două tipuri de arbori binari deformați, adică arborele binar înclinat la stânga sau arborele binar înclinat spre dreapta.
• Arbore binar echilibrat: diferența dintre înălțimea subarborelui din stânga și din dreapta pentru fiecare nod este fie 0, fie 1.

2. Arborele de căutare binar

Aceste structuri arborescente sunt neliniare și un nod este conectat la un număr de noduri. Nodul poate fi conectat la cel mult două noduri copil. Se numește arbore binar de căutare deoarece:

• Fiecare nod are maximum două noduri copil.
• Poate fi folosit pentru a căuta un element în timp 0(log(n)) și, prin urmare, cunoscut sub numele de arbore de căutare.

Figura: Un exemplu de arbore de căutare binar ( https://www.tutorialspoint.com/data_structures_algorithms/binary_search_tree.htm )

Proprietățile unui arbore binar de căutare sunt:

• Valoarea din toate nodurile unui subarboresc din stânga ar trebui să fie mai mică decât valoarea din nodul rădăcină.
• Valoarea în toate nodurile unui subarboresc drept ar trebui să fie mai mare decât valoarea în nodul rădăcină.

3. Arbore AVL

Arborii AVL sunt tipurile sau variantele unui arbore binar. Constă din proprietăți atât din arborele binar, cât și din arborele de căutare binar. Inventați de Adelson Velsky Lindas, acești copaci se auto-echilibrează, ceea ce înseamnă că înălțimea subarborelui din stânga și a arborelui din dreapta este echilibrată. Acest echilibru este măsurat în termeni de un factor de echilibrare.

Factorul de echilibrare:

• Este diferența dintre subarborele din stânga și subarborele din dreapta.
• Valoarea unui factor de echilibrare trebuie să fie 0, -1 sau 1. Prin urmare, fiecare nod al unui arbore AVL ar trebui să fie format dintr-o valoare a factorului de echilibrare, adică 0, -1 sau 1.
• Factorul de echilibru = (Înălțimea subarborelui din stânga – Înălțimea subarborelui din dreapta)
• Se spune că un arbore AVL este un arbore echilibrat dacă factorul de echilibru al fiecărui nod este între -1 și 1.

Valorile nodurilor altele decât -1, până la 1 într-un arbore AVL vor reprezenta un arbore dezechilibrat care trebuie echilibrat.

• Dacă un nod are un factor de echilibru de 1, înseamnă că subarborele din stânga este cu un nivel mai mare decât subarborele din dreapta.
• Dacă un nod are un factor de echilibru de 0, înseamnă că înălțimea subarborelui din stânga și a subarborelui din dreapta este egală.
• Dacă un nod are un factor de echilibru de -1, înseamnă că subarborele din dreapta este cu un nivel mai mare decât subarborele din stânga sau subarborele din stânga este cu un nivel mai jos decât subarborele din dreapta.

4. B-Arbore

B Tree este o formă mai generalizată a unui arbore binar de căutare. Este cunoscut și sub denumirea de arbore m way echilibrat pe înălțime, unde m este ordinea arborelui. Fiecare nod al arborelui poate avea mai mult de o cheie și mai mult de două noduri copil. În cazul unui arbore binar, nodurile frunzelor ar putea să nu fie la același nivel. Cu toate acestea, în cazul unui arbore B, toate nodurile frunzelor ar trebui să fie la același nivel.

Proprietățile unui arbore B:

• Cheile sunt stocate în ordine crescătoare pentru fiecare nod x.
• O valoare booleană „x.leaf” există în fiecare nod, ceea ce este adevărat dacă x este o frunză.
• Nodurile interne ar trebui să aibă cel mult chei „n-1”, unde n este ordinea arborelui. De asemenea, ar trebui să aibă un indicator pentru fiecare copil.
• Toate nodurile vor avea cel mult n copii și cel puțin n/2 copii, cu excepția nodului rădăcină.
• Nodurile frunzelor arborelui au aceeași adâncime.
• Nodul rădăcină va avea minim 1 cheie și cel puțin doi copii.
• Dacă n ≥ 1, atunci pentru orice arbore B cu n cheie cu înălțimea h și gradul minim t ≥ 2, h ≥ logt (n+1)/2.

Aplicații

• Arborele de căutare binar poate fi aplicat pentru căutarea unui element dintr-un set de elemente.
• Arborele heap sunt folosiți pentru sortarea heap.
• Routerele moderne folosesc un tip de arbore numit Tries pentru stocarea informațiilor de rutare.
• B-Trees și T-Trees sunt folosite în cea mai mare parte de bazele de date populare pentru a-și stoca datele.
• Un arbore de sintaxă este folosit de compilatori pentru a valida sintaxa fiecărui program scris.

Concluzie

Structurile de date oferă o modalitate organizată de stocare a datelor pentru o gestionare ușoară și o manipulare eficientă. Există diferite tipuri de structuri de date pentru diferite tipuri de date. Pe baza tipului de date care trebuie stocate, acestea sunt alese de utilizator.

Arborii sunt tipuri de astfel de structuri de date în care tipul ierarhic de date poate fi stocat. Datele sunt stocate în nodurile care stochează uneori referința pentru alte noduri numite noduri copii.

Pe baza numărului de noduri copii, copacii pot fi clasificați în diferite tipuri, așa cum este menționat în articol. Pe baza aranjamentului nodurilor în tipurile de arbore, fiecare structură de arbore are proprietăți asociate. Cu diferitele tipuri de operații care pot fi efectuate de diferitele clase de arbori, acest tip de structură de date și-a găsit aplicații în algoritmii de sortare și stocarea datelor.

Un Program Executive PG în Dezvoltare Software – Specializare în Dezvoltare Full Stack, organizat de upGrad & IIIT-Bangalore, vă poate ajuta să vă îmbunătățiți profilul și să vă asigurați oportunități mai bune de angajare ca programator.