În acest tutorial, veți afla despre structura datelor arborelui. De asemenea, veți afla despre diferite tipuri de copaci și terminologiile utilizate în copac.
Un arbore este o structură de date ierarhică neliniară care constă din noduri conectate prin margini.
Un copac
De ce structura datelor arborescente?
Alte structuri de date cum ar fi matrici, listă legată, stivă și coadă sunt structuri de date liniare care stochează date secvențial. Pentru a efectua orice operație într-o structură de date liniară, complexitatea timpului crește odată cu creșterea dimensiunii datelor. Dar, nu este acceptabil în lumea de calcul de astăzi.
Diferite structuri de date în arbore permit accesul mai rapid și mai ușor la date, deoarece este o structură de date neliniară.
Terminologii de copaci
Nodul
Un nod este o entitate care conține o cheie sau o valoare și indicatori către nodurile sale copil.
Ultimele noduri ale fiecărei căi se numesc noduri frunze sau noduri externe care nu conțin o legătură / pointer către noduri copil.
Nodul care are cel puțin un nod copil se numește nod intern .
Margine
Este legătura dintre oricare două noduri.
Nodurile și marginile unui copac
Rădăcină
Este cel mai înalt nod al unui copac.
Înălțimea unui nod
Înălțimea unui nod este numărul de margini de la nod la cea mai adâncă frunză (adică cea mai lungă cale de la nod la un nod frunză).
Adâncimea unui nod
Adâncimea unui nod este numărul de margini de la rădăcină la nod.
Înălțimea unui copac
Înălțimea unui copac este înălțimea nodului rădăcină sau adâncimea celui mai adânc nod.
Înălțimea și adâncimea fiecărui nod dintr-un copac
Gradul unui nod
Gradul unui nod este numărul total de ramuri ale acelui nod.
pădure
O colecție de copaci disjuncti se numește pădure.
Crearea pădurii dintr-un copac
Puteți crea o pădure tăind rădăcina unui copac.
Tipuri de copaci
- Arborele binar
- Arborele de căutare binar
- Arborele AVL
- Arborele B
Traversarea copacilor
Pentru a efectua orice operație pe un copac, trebuie să ajungeți la nodul specific. Algoritmul de traversare a arborelui ajută la vizitarea unui nod necesar din arbore.
Pentru a afla mai multe, vă rugăm să vizitați traversarea copacului.
Aplicații Tree
- Arborii de căutare binari (BST) sunt utilizați pentru a verifica rapid dacă un element este prezent într-un set sau nu.
- Heap este un fel de copac care este folosit pentru sortarea heap.
- O versiune modificată a unui arbore numit Tries este utilizată în routerele moderne pentru a stoca informații de rutare.
- Cele mai populare baze de date folosesc copaci B și copaci T, care sunt variante ale structurii copacului pe care am învățat-o mai sus pentru a stoca datele lor.
- Compilatoarele folosesc un arbore de sintaxă pentru a valida sintaxa fiecărui program pe care îl scrieți.
