Introducere în arbori în structura datelor
Înainte de a înțelege tipurile de arbori din structura de date, mai întâi, vom studia arborii din structura de date. Arborele din câmpul computerului este de asemenea denumit arbore din lumea reală, însă diferența dintre lumea reală și arborele câmpului de calcul este că este vizualizat ca cu susul în jos și rădăcina deasupra lui și ramură de la rădăcină la frunze de copac. Printre diverse aplicații din lumea reală, structura de date arbore este utilizată, deoarece poate demonstra relații între noduri diferite cu ierarhia părinte-copil. De asemenea, se numește structură de date ierarhice. Este cel mai popular pentru simplificarea și accelerarea căutării și sortării. Este considerată una dintre cele mai puternice și mai avansate structuri de date. Un arbore este o reprezentare a structurii de date neliniare. Un arbore poate fi arătat folosind diferite tipuri de date definite de utilizator sau primitive. Putem folosi tablouri, liste conectate la clase sau alte tipuri de structuri de date pentru a implementa arborele. Este un grup de noduri care sunt interrelaționate. Nodurile sunt atașate la margini pentru a demonstra relația.
Relații într-un arbore: În diagrama de mai sus, P este rădăcina arborelui, de asemenea, P este Părinte de Q, R și S. Q este copilul lui P. De aici Q, R și S sunt frați. Întrucât P este strănepot al A, B, C, D și E.
Ce sunt Copacii?
Un arbore este o structură de date ierarhice care stochează în mod natural informațiile în mod ierarhic. Structura de date Tree este una dintre cele mai eficiente și mai mature. Sunt reprezentate nodurile conectate de margini.
Proprietățile arborelui: fiecare copac are un nod rădăcină specific. Fiecare nod arbore poate fi traversat de un nod rădăcină. Se numește rădăcină, deoarece arborele era singura rădăcină. Fiecare copil are un singur părinte, dar părintele poate avea mulți copii.
Tipuri de arbori din structura datelor
Mai jos sunt tipurile de arbori dintr-o structură de date:
1. Arborele general
Dacă nu se pune nicio constrângere pe ierarhia arborelui, un arbore se numește arbore general. Fiecare nod poate avea un număr infinit de copii în Arborele General. Arborele este super-setul tuturor celorlalți copaci.
2. Arbore binar
Arborele binar este tipul de copac în care pot fi găsiți cei mai mulți doi copii pentru fiecare părinte. Copiii sunt cunoscuți drept copilul stâng și copilul drept. Acesta este mai popular decât majoritatea celorlalți copaci. Atunci când anumite constrângeri și caracteristici sunt aplicate într-un arbore binar, se folosesc și alte altele, cum ar fi arborele AVL, BST (arborele de căutare binară), arborele RBT etc. Când vom avansa, vom explica în detaliu toate aceste stiluri.
3. Arborele căutării binare
Arborele de căutare binară (BST) este o extensie arbore binară cu mai multe restricții opționale. Valoarea copilului stâng al unui nod trebuie în BST să fie mai mică sau egală cu valoarea părintească, iar valoarea copilului drept ar trebui să fie întotdeauna mai mare sau egală cu valoarea părintelui. Această proprietate Arbore de căutare binară o face ideală pentru operațiunile de căutare, deoarece putem determina cu exactitate la fiecare nod dacă valoarea este în subarbore stânga sau dreapta. Acesta este motivul pentru care Arborele Căutare este numit.
4. Arborele AVL
Arborele AVL este un arbore de căutare binar care se echilibrează. În numele inventatorilor Adelson-Velshi și Landis, numele AVL este dat. Acesta a fost primul copac care s-a echilibrat dinamic. Un factor de echilibrare este alocat pentru fiecare nod din arborele AVL, pe baza dacă arborele este echilibrat sau nu. Înălțimea copiilor cu noduri este de cel mult 1. viță de vie AVL. În arborele AVL, factorul de echilibru corect este 1, 0 și -1. Dacă arborele are un nod nou, atunci acesta va fi rotit pentru a se asigura că arborele este echilibrat. Acesta va fi apoi rotit. Operațiunile obișnuite, cum ar fi vizualizarea, introducerea și îndepărtarea necesită timp O (log n) în arborele AVL. Este aplicat mai ales atunci când lucrați cu operațiuni Lookups.
5. Arbore roșu-negru
Un alt tip de arbore de echilibrare automată este roșul-negru. Numele roșu-negru este dat deoarece arborele roșu-negru are fie roșu, fie negru pictat pe fiecare nod în funcție de proprietățile arborelui roșu-negru. Menține echilibrul pădurii. Chiar dacă acest arbore nu este un arbore complet echilibrat, operația de căutare durează doar O (log n) timp. Când noile noduri sunt adăugate în Red-Black Tree, atunci nodurile vor fi rotite din nou pentru a menține proprietățile Arborelui Roșu-Negru.
6. Arborele N-ary
Numărul maxim de copii din acest tip de arbore care poate avea un nod este N. Un arbore binar este un copac de doi ani, la fel ca cel mult 2 copii din fiecare nod binar. Un arbore complet N-ary este un copac în care copiii unui nod sunt 0 sau N.
Avantajele Arborelui
Acum vom înțelege avantajele arborelui:
- Arborele se reflectă în conexiunile structurale ale datelor.
- Arborele este folosit pentru ierarhizare.
- Oferă o procedură eficientă de căutare și inserare.
- Copacii sunt flexibili. Aceasta permite relocarea subteranelor cu efort minim.
Concluzie - Tipuri de arbori din structura datelor
Așadar, aici în acest articol, am văzut care este structura arborilor, care sunt diferitele tipuri de arbori din structura datelor și beneficiile acesteia. Sper că v-ați făcut o idee despre unii arbori comuni din structura datelor.
Articole recomandate
Acesta este un ghid pentru Tipuri de arbori din structura datelor. Aici vom discuta despre ce sunt arbori, 6 tipuri de arbori în structura de date, cu avantaje. Puteți parcurge și alte articole conexe pentru a afla mai multe -
- Conductă de date AWS
- Depozitarea datelor Oracle
- Baza de date multidimensională
- Structura de date Întrebări de interviu Java