Un arbore este una dintre cele mai utilizate structuri de date în informatică , emulând o structură arborescentă ca un set de noduri conectate. Este un graf conectat care nu conține cicluri. Majoritatea surselor adaugă, de asemenea, o condiție ca marginile graficului să nu fie îndreptate. Pe lângă aceste trei restricții, unele surse afirmă că muchiile unui grafic nu trebuie ponderate.
Se spune că un copac este orientat dacă nicio margine nu intră în rădăcină.
Un nod este o instanță a unuia dintre cele două tipuri de elemente de graf, corespunzătoare unui obiect de natură fixă. Un nod poate conține o valoare, o stare sau o reprezentare a unei structuri de informații individuale sau a arborelui însuși. Fiecare nod de arbore are zero sau mai multe noduri copil care sunt mai jos în arbore (prin convenție, copacii „cresc” în jos, nu în sus, așa cum fac copacii adevărați). Un nod care are un copil este numit un nod părinte al copilului său (sau un nod predecesor sau un nod mai vechi). Fiecare nod are cel mult un părinte. Înălțimea unui nod este lungimea maximă a unei căi descendente de la acel nod la cel mai de jos nod (nod de margine), numit frunză . Înălțimea nodului rădăcină este egală cu înălțimea întregului arbore. Adâncimea de imbricare a unui nod este egală cu lungimea căii către nodul rădăcină.
Nodul fără strămoși (cel mai de sus) se numește nodul rădăcină . Acesta este nodul în care încep majoritatea operațiunilor din arbore (deși unii algoritmi încep de la „frunze” și rulează până ajung la rădăcină). Toate celelalte noduri pot fi atinse mergând de la nodul rădăcină de-a lungul marginilor (sau legăturilor) (conform definiției formale, fiecare astfel de cale trebuie să fie unică). În diagrame, este de obicei descris în partea de sus. În unii copaci, cum ar fi grămezi , nodul rădăcină are proprietăți speciale. Fiecare nod de arbore poate fi considerat ca nodul rădăcină al unui subarbore care „crește” din acel nod.
Un subarboresc este o parte a unei structuri de date asemănătoare arborelui care poate fi reprezentată ca un arbore separat. Orice nod al arborelui T împreună cu toate nodurile sale descendențe este un subarboresc al arborelui T . Pentru orice nod dintr-un subarboresc, fie trebuie să existe o cale către nodul rădăcină al acelui subarbore, fie nodul însuși trebuie să fie nodul rădăcină. Adică, un subarbore este asociat cu nodul rădăcină de către un întreg arbore, iar relația unui subarbore cu toate celelalte noduri este definită prin conceptul de subarbore corespunzător (prin analogie cu termenul „ subset corespunzătoare ”).
Există două tipuri principale de copaci. Într -un arbore recursiv sau un arbore neordonat , contează doar structura arborelui în sine, fără a lua în considerare ordinea copiilor pentru fiecare nod. Un arbore în care este dată o ordine (de exemplu, fiecărei margini care duce la un descendent i se atribuie un număr natural diferit ) se numește arbore cu margini denumite sau un arbore ordonat cu o structură de date dată înainte de denumire, numită structură de date arborescentă ordonată .
Arborii ordonați sunt cei mai des întâlniți printre structurile arborilor. Un arbore binar de căutare este un tip de arbore ordonat.
Există multe moduri diferite de a reprezenta copacii. Cea mai obișnuită reprezentare descrie nodurile ca înregistrări situate în memoria alocată dinamic cu pointeri către descendenții, strămoșii lor (sau ambii) sau ca elemente ale unei matrice , legate între ele prin relații definite de pozițiile lor în matrice (de exemplu, un heap binar ). ).
În teoria grafurilor, un arbore este un graf aciclic conex . Un arbore înrădăcinat este un grafic cu vârful selectat ca rădăcină. În acest caz, oricare două vârfuri conectate printr-o muchie moștenesc relația părinte-copil. Un grafic deconectat format numai din copaci se numește pădure .
O enumerare pas cu pas a elementelor arborelui de-a lungul legăturilor dintre nodurile strămoși și nodurile descendente se numește tree traversal . Adesea, o operație poate fi efectuată prin parcurgerea indicatorului peste noduri individuale. O traversare în care fiecare nod strămoș este privit înainte de descendenții săi se numește traversare pre- ordonată sau traversare în ordine directă (mers de pre-comandă), iar când descendenții sunt priviți la început, apoi strămoșii, apoi traversarea se numește post -parcurgere ordonata sau traversare in ordine inversa (mers post-comanda). Există, de asemenea, o traversare simetrică , care vizitează mai întâi subarborele din stânga, apoi nodul, apoi subarborele din dreapta și o traversare în lățime , care vizitează nodurile nivel cu nivel (nivelul N al arborelui este setul de noduri cu înălțimea N). ). Fiecare nivel este parcurs de la stânga la dreapta.
| Arborele (structura de date) | |
|---|---|
| Arbori binari | |
| Arbori binari cu auto-echilibrare |
|
| B-copaci |
|
| arbori de prefix |
|
| Partiționarea binară a spațiului | |
| Arbori non-binari |
|
| Despărțirea spațiului |
|
| Alți copaci |
|
| Algoritmi | |
| Structuri de date | |
|---|---|
| Liste | |
| Copaci | |
| Contează | |
| Alte | |