5 tipuri de arbore binar în structura datelor explicate

Un arbore binar este o structură de date arborescentă neliniară care conține fiecare nod cu maximum 2 copii. Numele binar sugerează numărul 2, astfel încât orice arbore binar poate avea un copil stâng și drept.

Un indicator ilustrează un arbore binar către nodul cel mai de sus, cunoscut de obicei sub numele de rădăcina arborelui. Fiecare nod dintr-un arbore binar conține date, un pointer către copilul din stânga și un indicator către copilul din dreapta. Pointerii sunt folosiți pentru a implementa un arbore binar. Indicatorul rădăcină indică primul nod din arbore. Pentru a crea un arbore binar, trebuie mai întâi să creați un nod.

După ce vă familiarizați cuce este arborele binar în structura de date , trebuie să cunoașteți și operațiunile de bază efectuate pe un arbore binar.Puteți efectua funcții precum inserarea unui element, eliminarea unui element, căutarea unui element și traversarea arborelui binar.

Oricearbore binar din structura de date este utilizat în două moduri diferite în calcul.În primul rând, ele sunt folosite pentru a accesa nodurile în funcție de etichete sau valori specifice legate de fiecare nod. În al doilea rând, ele sunt utilizate ca reprezentări de date cu o structură ramificată relevantă.

Înainte de a trece prin diferitetipuri de arbore binar , să ne familiarizăm mai întâi cu terminologiile folosite într-un arbore binar.

Nod: Deține o valoare de date într-un arbore binar.

Rădăcină: Cel mai înalt nod din orice arbore binar se numește rădăcina unui arbore.

Dimensiune: denotă numărul de noduri dintr-un arbore binar.

Nod părinte: Un nod dintr-un arbore binar cu un copil.

Nod copil: este un nod care provine dintr-un nod părinte care se îndepărtează de rădăcina arborelui binar.

Nod intern: este un nod cu cel puțin un copil într-un arbore binar.

Nodul frunză: este un nod fără copil.Este alternativ un nod extern.

Adâncimea unui arbore de noduri: este calculată în contextul unui anumit nod.Este denumit numărul de muchii de la un anumit nod până la rădăcină.

Lungimea căii interne a unui arbore: se referă la suma nivelurilor fiecărui nod intern dintr-un arbore binar.

Lungimea căii externe a unui arbore: este definită ca suma nivelurilor fiecărui nod extern dintr-un arbore binar.

Înălțimea nodului într-un arbore: este numărul de muchii de la un anumit nod până la cel mai adânc nod de frunză al arborelui binar.Înălțimea rădăcinii va fi întotdeauna mai mare decât cea a altor noduri din arborele binar.

Acum să verificăm detaliile a 5tipuri de arbore binar.

Tipuri de arbore binar

1. Arborele binar complet

Acestarbore binar în structura de date este cunoscut și sub numele de arbore binar propriu și arbore binar strict.Este unul dintre cele mai fundamentaletipuri de arbore binar din structura datelor.Un arbore binar complet este definit ca un arbore binar în care fiecare nod ar trebui să aibă doi copii sau deloc.

Este, alternativ, caracterizat ca un arbore binar în care fiecare nod cuprinde doi copii, cu excepția nodurilor frunze. Nodurile în care este stocată adresa nodului rădăcină se numesc noduri copii ale rădăcinii. Acele noduri lipsite de copii se numesc noduri de frunze.

Trebuie să parcurgeți toate nodurile pentru a verifica dacă un arbore este un arbore binar. Codul va returna „False” dacă orice nod are un copil. Va returna „True” dacă toate nodurile au 0 sau 2 copii.

Iată proprietățile unui arbore binar complet:

• Numărul de noduri de frunze este egal cu numărul de noduri interne + 1. De exemplu, dacă numărul de noduri interne este 4, numărul de noduri de frunze este egal cu 5.
• Numărul maxim de noduri și numărul de noduri dintr-un arbore binar sunt egale. Este reprezentat ca 2h+1 -1.
• Numărul minim de noduri într-un arbore binar complet este 2h-1.
• Înălțimea minimă a unui arbore binar complet este log 2 (n+1) – 1.
• Înălțimea maximă a unui arbore binar complet este h = (n+1)/2.

2. Arborele binar perfect

Un arbore binar perfect este unul dintre aceletipuri de arbori binari în care fiecare nod trebuie să aibă 0 sau 2 copii, iar nivelul fiecărui nod frunză trebuie să fie același.Cu alte cuvinte,arborii binari perfecți din structura de date sunt definiți ca acei copaci în care toate nodurile interioare posedă două ramuri și acele noduri fără ramuri (noduri de frunze) există la același nivel.

În acest context, nivelul unui nod este distanța sau înălțimea de la nodul rădăcină. Puteți considera un arbore binar perfect ca un arbore binar complet în care ultimul nivel este, de asemenea, complet ocupat.

Învațăcursuri de știință a dateloronline de la cele mai bune universități din lume.Câștigați programe Executive PG, programe avansate de certificat sau programe de master pentru a vă accelera cariera.

3. Arborele binar complet

Un arbore binar complet este unul dintre acele tipuri de arbore binar în structura de date în care toate nivelurile arborelui sunt complet completate.Ultimul nivel al arborelui binar poate fi sau nu complet umplut. Cu toate acestea, fiecare nod trebuie să fie situat în poziția cea mai din stânga în ultimul nivel al nodului. Nodurile trebuie incluse din stânga.

Sunt unul dintretipurile esențiale de arbori binari , deoarece oferă cel mai bun raport între numărul de noduri și înălțimea unui copac.

Iată proprietățile cheie ale unui arbore binar complet:

• Numărul maxim de noduri este de 2 h+1 – 1.
• Numărul minim de noduri este de 2 ore .
• Înălțimea minimă este log 2 (n+1) – 1.

4. Arborele binar echilibrat

În arborii binari echilibrați, înălțimea unui arbore este log 2 din numărul total de noduri. Să presupunem că înălțimea arborelui este h și numărul total de noduri ale arborelui este n. Ecuația pentru a calcula înălțimea este h = log(n). Diferența maximă de înălțime dintre un sub-arborele din dreapta și un sub-arborele din stânga trebuie să fie „1”.

Diferența poate avea alte valori precum 0 și -1. Aceste tipuri de arbori binari sunt denumite și arbori AVL.Unul dintre exemplele binecunoscute de arbori binari echilibrați este arborele roșu-negru.

Puteți implementa următorul cod pentru a rula un arbore binar echilibrat.

clasa privată Node {

valoare int privat;

Nodul privat stânga;

dreptul de nod privat;

}

public boolean isBalanced(Nodul n) {

dacă (balancedtreeHeight(n) > -1)

returnează adevărat;

returnează fals;

}

public int balancedtreeHeight(Nodul n) {

dacă (n == nul)

returnează 0;

int h1 = balancedtreeHeight(n.right);

int h2 = balancedtreeHeight(n.stânga);

dacă (h1 == -1 || h2 == -1)

întoarcere -1;

dacă (Math.abs(h1 – h2) > 1)

întoarcere -1;

dacă (h1 > h2)

returnează h1 + 1;

întoarce h2 + 1;

}

Verificați programele noastre din SUA - Data Science

5. Arborele binar degenerat

Un arbore binar degenerat este unul dintre tipurile mai puțin frecvent utilizatede arbore binar de căutare .Este un arbore binar în care fiecare nod are un singur copil, adică un copil stânga sau dreapta. Niciun nod nu ar trebui să aibă atât copii din stânga, cât și din dreapta.

Citiți articolele noastre populare din SUA - Data Science

Concluzie

Este esențial să înțelegețice este arborele binar în structura de date dacă doriți să îl utilizați pentru diverse aplicații.Implementarea diferitelor funcții pe arbori binari vă poate ajuta în organizarea și stocarea eficientă a datelor.

Studierea mai multor tipuri de arbori binari vă ajută să efectuați operațiuni mai eficient în complexitatea timpului. Fundamentele științei datelor, inclusivstructura de date din arbore binar, vă ajută să vă începeți cu ușurință călătoria științei datelor.Ulterior, puteți lucra la proiecte avansate de știință a datelor pentru a vă îmbunătăți abilitățile și portofoliul.

Începeți cu călătoria dvs. de învățare automată pe upGrad

Dacă doriți să învățați știința datelor, puteți urma programul de master în știința datelor upGrad . Acest curs de 24 de luni oferă abilități precum Python, Implementarea modelelor ML, procesarea BD folosind Spark, Analytics predictiv și statistici și modele ML supravegheate și nesupravegheate. Cursul este potrivit pentru manageri ambițioși, absolvenți de MBA, ingineri și profesioniști din diverse domenii.

Finalizarea acestui curs vă va ajuta să lucrați ca inginer de date, analist de date mari, inginer de învățare automată și științific de date.