Un ghid pentru începători pentru copacii binari

Dacă ați urmat un curs de structuri de date în diploma de informatică sau sunteți programator autodidact, este posibil să fi întâlnit termenul „Arbori binari”. Deși pot părea puțin copleșitoare și complexe, conceptul de copac binar este destul de simplu.

Citiți mai departe pe măsură ce disecăm copacii binari și de ce sunt un concept de bază necesar pentru programatori.

Ce sunt copacii binari?

Arborii binari sunt printre una dintre primele structuri de date pe care studenții sunt predate într-un curs de structuri de date. Un arbore binar este format din mai multe noduri, iar fiecare nod al arborelui binar conține doi indicatori care indică nodurile de date copil stânga și dreapta.

Primul nod dintr-un arbore binar se numește „rădăcină”. Nodurile ultimului nivel dintr-un copac se numesc frunze.

Fiecare nod conține un element de date și două pointeri de nod. Un copac binar gol este reprezentat de un indicator nul. După cum probabil v-ați dat seama, copacii binari pot avea doar doi copii (de unde și numele).

Tipuri de structuri binare de arbori

Există mai multe structuri binare diferite în funcție de modul în care sunt poziționate nodurile. Un copac binar se numește copac binar complet atunci când fiecare nod din copac are fie zero, fie doi copii. Într-un copac binar perfect, toate nodurile au doi copii și frunzele sunt toate la aceeași adâncime.

Legate de: Cele mai bune moduri de a învăța cum să codificați gratuit

Un arbore binar complet are noduri completate în fiecare nivel, cu excepția ultimului nivel. În copacii binari complet, nodurile sunt concentrate pe partea stângă a rădăcinii. O altă structură comună este un arbore binar echilibrat; în această structură, înălțimile subarborilor din dreapta și din stânga trebuie să difere cel mult de unul. De asemenea, este necesar ca subarborii din stânga și din dreapta să fie, de asemenea, echilibrați.

Este important să rețineți că înălțimea arborelui binar echilibrat este O (logn), unde n este numărul de noduri din arbore.

În unele cazuri, dacă fiecare nod are doar un copil stânga sau dreapta, atunci arborele binar poate deveni un arbore binar înclinat. Apoi se va comporta ca o listă legată, astfel de copaci sunt numiți și copac degenerat.

Ce sunt copacii de căutare binari?

Un arbore binar de căutare (BST) este în esență un arbore binar ordonat cu o proprietate specială cunoscută sub numele de proprietatea „arborele binar de căutare”. Proprietatea BST înseamnă că nodurile cu o valoare a cheii mai mică decât rădăcina sunt plasate în subarborele din stânga, iar nodurile cu o valoare a cheii mai mare decât rădăcina fac parte din subarborele din dreapta.

Proprietatea BST trebuie să fie adevărată pentru fiecare nod părinte ulterior din arbore.

Arborii binari de căutare oferă inserare și căutare rapidă. Operațiunile de inserare, ștergere și căutare au o complexitate de timp în cel mai rău caz de O (n), care este similar cu o listă legată.

Beneficiile copacilor binari

Arborii binari oferă multe avantaje, motiv pentru care rămân o structură de date foarte utilă. Ele pot fi utilizate pentru a arăta relațiile structurale și ierarhiile într-un set de date. Mai important, arborii binari permit căutarea, ștergerea și inserarea eficientă.

De asemenea, este foarte ușor să implementați și să întrețineți un arbore binar. Un arbore binar oferă programatorilor avantajele unui tablou ordonat și al unei liste legate; căutarea într-un arbore binar este la fel de rapidă ca într-o matrice sortată, iar operațiile de inserare sau ștergere sunt la fel de eficiente ca în listele legate.

Arborii binari sunt structuri de date importante

Arborii binari sunt o structură de date foarte importantă și este crucial ca programatorii să se simtă confortabil să le aplice în programele lor. Adesea, intervievatorii cer probleme simple de arbori binari precum traversări, adâncime maximă, oglindire etc.

Vă recomandăm să înțelegeți conceptul arborelui binar și să fiți familiarizați cu problemele tipice ale interviului.

TreeViz: o modalitate simplă de a vizualiza structurile de date

Citiți în continuare

Despre autor