O structură de date neliniară constă dintr-o colecție de elemente care sunt distribuite pe un plan, ceea ce înseamnă că nu există o astfel de secvență între elemente, deoarece există într-o structură de date liniară.
Diagramă de comparație
| Bazele de comparație | Copac | Grafic |
|---|---|---|
| cale | Doar unul dintre două noduri. | Sunt permise mai multe căi. |
| Nodul rădăcină | Are un singur nod rădăcină. | Graficul nu are un nod rădăcină. |
| buclele | Nu sunt permise bucle. | Graficul poate avea bucle. |
| Complexitate | Mai puțin complexă | Mai complexe comparativ |
| Tehnici de traversare | Pre-comandă, comandă și post-comandă. | Căutare de primă căutare și căutare în profunzime. |
| Număr de margini | n-1 (unde n este numărul de noduri) | Nedefinit |
| Tipul modelului | Ierarhic | Reţea |
Definiția Tree
Un arbore este o colecție finită de elemente de date denumite în mod uzual ca noduri. Așa cum se menționează mai sus, un arbore este o structură de date neliniară care aranjează elementele de date în ordine sortată. Acesta este folosit pentru a arăta o structură ierarhică între diferitele elemente de date și pentru a organiza datele în ramuri care corelează informațiile. Adăugarea unei noi margini într-un copac duce la formarea bucla sau a circuitului.
Există mai multe tipuri de arbori, cum ar fi un arbore binar, arbore binar de căutare, copac AVL, arbore binar filetat, copac B etc. Compresia datelor, stocarea fișierelor, manipularea expresiei aritmetice și arborii de joc sunt o parte din aplicarea arborelui structură de date.
Proprietățile arborelui:
- Există un nod desemnat în partea superioară a arborelui cunoscut sub numele de rădăcină a copacului.
- Elementele de date rămase sunt împărțite în subseturi disjuncte denumite subtree.
- Arborele este extins în înălțime spre partea de jos.
- Un copac trebuie să fie conectat, ceea ce înseamnă că trebuie să existe o cale de la o rădăcină la toate celelalte noduri.
- Nu conține bucle.
- Un arbore are n-1 margini.
Există diverși termeni asociați cu arborii, cum ar fi nodul terminal, marginea, nivelul, gradul, adâncimea, pădurea etc. Printre acești termeni, unele dintre ele sunt descrise mai jos.
- Edge - O linie care conectează două noduri.
- Nivel - Un copac este împărțit în nivele astfel încât nodul rădăcină să fie la nivelul 0. Apoi, copiii săi imediate sunt la nivelul 1, iar copiii săi imediate sunt la nivelul 2 și așa mai departe până la nodul terminal sau frunze.
- Grad - Este numărul de subtrezi ai unui nod dintr-un arbore dat.
- Adâncime - Este nivelul maxim al oricărui nod dintr-un arbore dat și, de asemenea, cunoscut ca înălțime .
- Nod terminale - Nodul cel mai înalt nivel este nod terminal, în timp ce alte noduri, cu excepția terminalelor și a nodului rădăcină, sunt cunoscute ca noduri non-terminale.
Definiția Graph
Un grafic este, de asemenea, o structură de date matematică neliniară care poate reprezenta diferite tipuri de structură fizică. Se compune dintr-un grup de vârfuri (sau noduri) și un set de muchii care leagă cele două noduri. Vertexurile din grafic sunt reprezentate ca puncte sau cercuri, iar marginile sunt arătate ca arce sau segmente de linie. O margine este reprezentată de E (v, w) unde v și w sunt perechile de vârfuri. Îndepărtarea unei margini dintr-un circuit sau dintr-un grafic conectat creează un subgraf care este un copac.
Graficele sunt clasificate în diferite categorii, cum ar fi direcționarea, non-direcționate, conectate, ne-conectate, simple și multigrafice. Rețeaua de calculatoare, sistemul de transport, graficul rețelei sociale, circuitele electrice și planificarea proiectului sunt unele dintre aplicațiile structurii datelor grafice. Se utilizează, de asemenea, în tehnica de management numită PERT (tehnica de evaluare și evaluare a programului) și CPM (metoda căii critice) în care este analizată structura graficului.
Proprietățile unui grafic:
- Un vârf dintr-un grafic poate fi conectat la orice număr de alte vârfuri folosind marginile.
- O margine poate fi bidirecționată sau direcționată.
- O margine poate fi ponderată.
În grafic, de asemenea, folosim termeni precum vârfuri adiacente, cale, ciclu, grad, grafic conectat, grafic complet, grafic ponderat etc. Să înțelegem câțiva dintre acești termeni.
- Vârfurile adiacente - Un vârf a este adiacent vârfului b dacă există o margine (a, b) sau (b, a).
- Cale - O cale de la un vârf aleatoriu w este o secvență adiacentă de vârfuri.
- Ciclu - Este o cale în care primul și ultimul punct sunt aceleași.
- Grad - Este un număr de margini care intră pe un vârf.
- Graf conectat - Dacă există o cale de la un vârf aleatoriu la orice alt vârf, atunci graficul este cunoscut ca un grafic conectat.
Diferențele cheie între arbore și grafic
- Într-un arbore există o singură cale între oricare două vârfuri, în timp ce un grafic poate avea căi unidirecționale și bidirecționale între noduri.
- În arbore, există un singur nod rădăcină și fiecare copil poate avea doar un singur părinte. Pe de altă parte, într-un grafic, nu există niciun concept al nodului rădăcină.
- Un copac nu poate avea bucle și bucle de auto-bucle, în timp ce graficul poate avea bucle și bucle de auto-bucle.
- Graficele sunt mai complicate, deoarece pot avea bucle și bucle de auto-bucle. Dimpotrivă, copacii sunt simpli în comparație cu graficul.
- Arborele este traversat folosind tehnici precomandate, în ordine și post-comandă. Pe de altă parte, pentru traversarea graficelor, folosim BFS (Breadth First Search) și DFS (Depth First Search).
- Un arbore poate avea n-1 margini. Dimpotrivă, în grafic, nu există un număr predefinit de margini și depinde de grafic.
- Un arbore are o structură ierarhică, în timp ce graficul are un model de rețea.
Concluzie
Graful și arborele sunt structura de date neliniară care este utilizată pentru a rezolva diferite probleme complexe. Un grafic este un grup de vârfuri și muchii în care o muchie conectează o pereche de vârfuri, în timp ce un copac este considerat un grafic minim conectat care trebuie să fie conectat și fără bucle.
