de Tiago Antunes

O introducere în copaci în programare: oxigenul unei codificări eficiente

O introducere a copacilor in programare oxigenul unei codificari eficiente

De multe ori doriți să salvați informații în programul dvs. și să le accesați de multe ori. Și îl veți stoca adesea într-o structură de date foarte simplă: o matrice. Și de multe ori funcționează foarte bine! Dar uneori este nevoie doar de un lot de timp pentru a termina.

Așadar, pentru a optimiza acest tip de program, mulți oameni deștepți au dezvoltat niște lucruri ciudate pe care le numim structuri de date. Astăzi voi aborda câteva elemente de bază despre acest subiect și voi discuta despre o structură specifică despre care este adesea întrebat în timpul interviurilor de codare și care îi face pe toți nebuni: Copacii.

Nu mă voi scufunda prea mult în cod, ci doar în teoria modului în care funcționează totul. Există milioane de mostre de cod online, așa că aruncați o privire după una după ce înțelegeți cum funcționează copacii!

1612132808 144 O introducere a copacilor in programare oxigenul unei codificari eficiente
Da … Care?

Deci, ce este cu adevărat o structură de date?

Conform Wikipedia:

” A structură de date este un format de organizare și stocare a datelor care permite eficient acces și modificare ”

Acest lucru înseamnă practic că nu este altceva decât cod scris pentru a crea un mod complex de stocare a datelor. Există o mulțime de structuri de date pe care le puteți implementa și fiecare are o sarcină specifică. Ele pot merge de la cele foarte simple – cum ar fi listele legate – la structuri foarte complexe – cum ar fi graficele.

Copacii sunt suficient de complexi pentru a fi foarte rapizi la ceea ce fac, dar suficient de simpli încât să fie de înțeles. Și un lucru la care sunt foarte buni este să găsească valori cu o utilizare minimă a memoriei.

Dar cum măsurați cât de eficientă este cu adevărat o structură de date?

Ați văzut vreodată o notație ciudată pe care oamenii o folosesc online, cum ar fi O (n)? Aceasta se numește Big O Notation și este modalitatea standard de a evalua performanța structurilor și algoritmilor. O mare pe care îl folosim este reprezentarea celui mai rău scenariu: având ceva care este O (n) (cu n fiind numărul de elemente din interior) înseamnă că în cel mai rău caz este nevoie de timp n, ceea ce este foarte bun.

În paranteză am scris n care este echivalentul scrierii expresiei y = x → . Se scalează proporțional. Dar uneori avem expresii diferite:

  • O (1)
  • O (jurnal (n))
  • Pe)
  • O (n²)
  • O (n³)
  • Pe!)
  • O (e ^ n)

Cu cât rezultatul unei funcții este mai mic, cu atât este mai eficientă o structură.
Există mai multe tipuri de copaci. Vom vorbi despre BST (copaci de căutare binară) și copaci AVL (copaci echilibrați automat) care au proprietăți diferite:

O introducere a copacilor in programare oxigenul unei codificari eficiente
După cum puteți vedea, copacii AVL sunt mult mai eficienți, dar mult mai complexi!

Ok, ai vorbit despre toată această notație ciudată … deci cum funcționează copacii?

Arborele de nume provine din reprezentarea sa reală: are o rădăcină, frunze și ramuri și este adesea reprezentat astfel:

1612132808 562 O introducere a copacilor in programare oxigenul unei codificari eficiente
Observați cum 6 nu este o frunză, deoarece nu este la capătul unei ramuri!

Există câteva denumiri pe care le folosim, și anume părinte și copil, care au o relație unică. Dacă X este părinte al y apoi y este copilul lui X. În această imagine, 2 este părinte de 5, apoi 5 este copil de 2. Fiecare nod – fiecare poziție cu o valoare – poate avea doar 1 părinte și 2 copii.

Dar pe lângă toate acestea, nu există un model care să fie urmat, astfel încât acest arbore nu este chiar atât de util … Deci ar trebui să adăugăm câteva reguli pentru a crea o structură bună a datelor.

Arborii binari de căutare

Atunci intervin copacii de căutare binară! În loc să plaseze în mod aleatoriu noduri copil, acestea urmează o ordine specifică:

  • Dacă nu există noduri, atunci prima valoare introdusă devine rădăcină a copacului.
  • Dacă există noduri, atunci inserarea ia următorii pași: începând de la rădăcină, dacă valoarea pe care o introduceți este mai mică decât nodul curent, treceți prin ramura din stânga, altfel treceți prin cea dreaptă. Dacă vă aflați într-un loc gol, atunci acolo este locul în care vă aparține valoarea!

Acest lucru s-ar putea simți puțin confuz la început, dar să scriem un pseudo cod pentru a-l simplifica:

//This code won't compile in any language (that I know of) and only serves to demonstrate how the code would look like
def insert(Node n, int v) {    if n is NULL:        return createNode(v)    else if n.value < v:        n.right = insert(n.right, v)    else:        n.left = insert(n.left, v)    return n}

Acum ce se întâmplă aici? Mai întâi verificăm dacă locul în care ne aflăm acum este gol. Dacă este, creăm un nod în acel loc cu funcția createNode. Dacă nu este gol, atunci trebuie să vedem unde ar trebui să ne plasăm nodul.

Această demonstrație arată cum funcționează:

O introducere a copacilor in programare oxigenul unei codificari eficiente
Sursa este: http://www.mathwarehouse.com/programming/gifs/binary-search-tree.php

Astfel putem căuta orice valoare din arbore fără a fi nevoie să parcurgem toate nodurile. Grozav!

Dar nu merge întotdeauna la fel de bine ca în gif-ul de mai sus. Ce se întâmplă dacă obținem așa ceva?

1612132809 470 O introducere a copacilor in programare oxigenul unei codificari eficiente
Hopa, cel mai rău scenariu!

În acest caz, comportamentul arborelui te face să parcurgi toate nodurile. De aceea, cel mai prost caz de eficiență al unui BST este de O (n), ceea ce îl face lent.
Ștergerea din BST este, de asemenea, ușoară:

  • Dacă un nod nu are copii → eliminați nodul
  • Dacă un nod are un copil → conectați nodul părinte la nodul său nepot și eliminați nodul
  • Dacă un nod are 2 copii → înlocuiți nodul cu cel mai mare copil al său (copilul din stânga din dreapta) → vezi imaginea de mai jos
1612132810 927 O introducere a copacilor in programare oxigenul unei codificari eficiente
Înlăturarea numărului 12 se întâmplă prin înlocuirea lui 12 cu 9

Deci, acum știți tot ce aveți nevoie despre BST. Destul de cool nu?

Dar dacă ai vrea MEREU ai un copac eficient? Ce ai face?

Dacă aveți această necesitate, copacii AVL pot face asta destul de bine pentru dvs. În schimb, acestea sunt de milioane de ori mai complexe decât BST, dar urmează aceeași organizație ca înainte.

Un arbore AVL este un arbore auto-echilibrat care are operațiuni specifice (numite rotații) care permit arborelui să rămână echilibrat. Aceasta înseamnă că fiecare nod din copac va avea o diferență de înălţime între cele două ramuri copil de maximum 1.

Cu aceasta, arborele va avea întotdeauna o înălțime a jurnalului (n) (n fiind numărul de elemente) și acest lucru vă permite să căutați elemente într-un mod cu adevărat eficient.

1612132810 542 O introducere a copacilor in programare oxigenul unei codificari eficiente
Există 11 elemente și înălțimea este 4. Deci asta înseamnă că programul ar face cel mult 4 căutări în jos! Acest lucru este cu adevărat eficient, deoarece fiecare nivel de jos menține numărul dublu de elemente ale nivelului său superior

Așa că acum vezi cât de buni și perfecti sunt copacii echilibrați. Dar cum să le faci este adevărata întrebare. Am menționat cuvântul adâncime înainte, așa că hai să o înțelegem mai întâi.

1612132811 531 O introducere a copacilor in programare oxigenul unei codificari eficiente
O frunză are înălțimea 0 și un nod care nu are frunze are o înălțime maximă a copiilor săi plus 1

Înălțimea este ceea ce ne permite să înțelegem dacă arborele nostru este echilibrat sau nu. Și cu aceasta putem determina unde este problema și putem aplica funcțiile de echilibrare: rotații. Acestea sunt funcții cu adevărat simple, care constau în schimbul de noduri între ele pentru a elimina diferența de înălțime, dar ar putea părea foarte ciudate la început.

Există 4 operații:

  • Rotație la stânga
  • Rotire dreapta
  • Rotație stânga-dreapta
  • Rotație Dreapta-Stânga
1612132811 240 O introducere a copacilor in programare oxigenul unei codificari eficiente
Nodul în care înălțimea copiilor a fost mai mare de 1 suferă o rotație (imaginați-vă un loc gol cu ​​înălțimea de -1, dacă îl calculați: balans (6) = 1 – -1 = 2)

Uau, a fost ciudat … cum funcționează rotațiile?

Rotațiile sunt ciudate la început și vă sugerez să verificați câteva animații care funcționează.

Încercați cu proprii copaci pe acest site: https://www.cs.usfca.edu/~galles/visualization/AVLtree.html

Vă permite să vedeți dinamic rotațiile care se întâmplă și este un instrument excelent!
Există doar patru cazuri, așa că înțelegerea lor va fi ușoară.

1612132811 440 O introducere a copacilor in programare oxigenul unei codificari eficiente
Rotație Dreapta-Stânga. Nu este altceva decât 2 rotații de bază!

Asta este tot pentru acum!

Copacii sunt destul de ușor de înțeles și, prin practică, puteți lucra cu ei cu ușurință. Aplicarea lor în codul dvs. este o cheie majoră pentru a vă face programele mult mai eficiente.

Dacă aveți întrebări despre ceva cu care nu ați înțeles, nu sunteți de acord sau doriți să sugerați, nu ezitați să mă contactați Stare de nervozitate sau prin e-mail!

E-mail: tiago.melo.antunes [at] tehnico [dot] ulisboa [dot] pt