Arborele binar în structura datelor: proprietăți, tipuri, reprezentare și beneficii

Printre diferitele tipuri de structuri de date se numără arbori binari care au mai multe utilizări decât majoritatea celorlalte tipuri. Cele mai notabile aplicații ale acestora includ programarea peer-to-peer, căutarea, criptografia, routerele de rețea cu lățime de bandă mai mare decât altele și jocurile video 3D. Vom discuta acum în detaliu ce sunt arborii binari în știința datelor, care sunt tipurile lor și cum sunt reprezentați.

Ce sunt arborii binari?

Dacă ați mai lucrat la arbori normali sau chiar știți despre elementele lor de bază, ați ști că nu există restricții când vine vorba de numărul de copii pe care diferite noduri au voie să-i aibă în acești copaci. Arborii binari sunt puțin diferiți în acest sens. Fiecare părinte sau nod din arbori binari poate avea maximum doi copii.

Toate nodurile dintr-un arbore binar au trei componente principale -

• un element de date
• o referință corectă
• o referință la stânga

Nodul care se află în partea de sus a arborelui este denumit nodul rădăcină. Nodurile părinte sunt cele care au copii. Nodurile copii și nodurile părinte sunt conectate între ele prin referințe. Nodurile care nu au copii sunt denumite noduri frunze.

Este clar că nodurile din arborii binari pot avea un copil, doi copii sau nici un copil. Arborii binari nu sunt structuri de date liniare, cum ar fi cozi, matrice, stive și liste legate. Ele sunt în schimb structuri de date ierarhice.

Consultați: Idei de proiecte Data Science pentru începători

Proprietăți importante ale nodurilor din arborii binari

O mai bună înțelegere a acestor proprietăți vă va ajuta să profitați la maximum de această discuție despre arborii binari. Adâncimea diferitelor noduri este definită ca numărul de noduri care există pe calea care conectează rădăcina la un anumit nod. De aceea, adâncimea nodului rădăcină este 0. Pe de altă parte, înălțimea diferitelor noduri dintr-un arbore binar este numărul de noduri care se află pe calea care conectează un anumit nod cu nodul rădăcină. De aceea, înălțimea nodurilor frunzelor este 0.

După cum puteți vedea clar, adâncimea unui nod este măsurată pornind de la nodul rădăcină și apoi coborând pentru a ajunge la acel nod. Pe de altă parte, când vine vorba de calcularea înălțimii, începem de la nodul în cauză și apoi călătorim către nodul rădăcină. În ambele ori, începem de la 0. Sunt oameni care măsoară și înălțimea și adâncimea de la 1 și nu de la 0, ceea ce nu este greșit și este ceea ce preferă diferiți oameni.

Acum, adâncimea maximă a unui nod este definită ca adâncimea unui arbore binar. În mod similar, înălțimea maximă a unui nod este definită ca înălțimea unui arbore binar. Deci, înălțimea și adâncimea unui arbore binar sunt întotdeauna aceleași.

Aflați mai multe: Structuri de date și algoritm în Python

Ce este un arbore binar de căutare?

Un arbore binar de căutare este cel mai comun dintre toate celelalte tipuri de arbori binari. Este un arbore binar specializat care vine cu proprietăți care sunt diferite și mai utile decât orice altă formă de arbore binar. Ce este mai exact un arbore de căutare binar sau BST? Așa cum sugerează și numele, un arbore de căutare binar este folosit pentru a căuta date în arbore.

Un BST vine cu proprietăți care îi permit să faciliteze căutări eficiente. Un BST este un arbore binar care are cheia nodului care este mai mică și mai mare decât nodurile din sub-arborele din dreapta și, respectiv, nodurile din sub-arborele din stânga.

Reprezentarea arborilor binari

1. Reprezentare legată

Arborii binari în reprezentare legată sunt stocați în memorie ca liste legate. Aceste liste au noduri care nu sunt stocate în locații de memorie adiacente sau învecinate și sunt legate între ele prin relația părinte-copil asociată cu arbori.

În această reprezentare, fiecare nod are trei părți diferite -

• indicator care indică către nodul din dreapta,
• indicator care indică către nodul stâng,
• element de date.

Aceasta este reprezentarea mai comună. Toți arborii binari constau dintr-un indicator rădăcină care indică în direcția nodului rădăcină. Când vedeți un nod rădăcină îndreptat către nul sau 0, ar trebui să știți că aveți de-a face cu un arbore binar gol. Indicatoarele dreapta și stânga stochează adresa copiilor din dreapta și din stânga copacului.

2. Reprezentarea secvenţială

Deși este mai simplă decât reprezentarea legată, ineficiența sa o face o reprezentare binară mai puțin preferată a celor două. Ineficiența constă în spațiul necesar pentru depozitarea diferitelor elemente ale arborelui. Reprezentarea secvențială folosește o matrice pentru stocarea elementelor arborescente.

Numărul de noduri pe care le are un arbore binar definește dimensiunea matricei care este utilizată. Nodul rădăcină al arborelui binar se află la primul index al matricei. Indicele la care este stocat un anumit nod va defini indicii la care vor fi stocați copiii din dreapta și din stânga nodului. Un arbore gol are nul sau 0 ca prim indice.

Tipuri de arbori binari

1. Arbori binari completi: Arborii binari completi sunt acei arbori binari ale căror noduri fie au doi copii, fie nu au niciunul. Cu alte cuvinte, un arbore binar devine un arbore binar complet atunci când, în afară de frunze, toate celelalte noduri ale sale au doi copii.
2. Arbori binari completi: arborii binari completi sunt cei care au toate nivelurile lor diferite complet umplute. Singura excepție de la aceasta ar putea fi ultimul lor nivel, ale cărui chei sunt predominant în stânga. O grămadă binară este adesea luată ca exemplu de arbore binar complet.
3. Arbori binari perfecți: arborii binari perfecți sunt arbori binari ale căror frunze sunt prezente la același nivel și ale căror noduri interne poartă doi copii. Un exemplu comun de arbore binar perfect este un arbore genealogic ancestral.
4. Arbori binari degenerați patologic: Arborii degenerați sunt acei arbori binari ale căror noduri interne au un singur copil. Nivelurile lor de performanță sunt similare cu listele legate. Aflați mai multe despre tipurile de arbore binar.

Citiți: Cele șase structuri de date cele mai frecvent utilizate în R

Beneficiile arborilor binari

1. O modalitate ideală de a merge cu modul ierarhic de stocare a datelor
2. Reflectați relațiile structurale care există în setul de date dat
3. Faceți inserarea și ștergerea mai rapide decât listele și matricele legate
4. Un mod flexibil de a păstra și de a muta datele
5. Sunt folosite pentru a stoca cât mai multe noduri
6. Sunt mai rapide decât listele legate și mai lente decât matricele atunci când vine vorba de accesarea elementelor

Concluzie

În acest blog, am discutat despre ce sunt arborii binari din structurile de date, precum și despre tipurile lor, reprezentările și beneficiile lor. Cele două utilizări majore ale arborilor sunt pentru căutarea și stocarea datelor și, prin urmare, sunt parte integrantă a studiului științei datelor și a domeniilor conexe.

Dacă sunteți curios să aflați despre arborii binari din structurile de date, știința datelor, consultați Programul Executive PG în știința datelor de la IIIT-B și upGrad, care este creat pentru profesioniști care lucrează și oferă peste 10 studii de caz și proiecte, ateliere practice practice, mentorat cu experți din industrie, 1-la-1 cu mentori din industrie, peste 400 de ore de învățare și asistență la locul de muncă cu firme de top.