"Bună, Amigo!"
— Bună, Rishi!
— Mi-am găsit vechile însemnări acolo și ți-am pregătit niște materiale interesante. Cred că vei fi interesat să-l auzi.
"Să auzim. Întotdeauna găsești ceva interesant care mai târziu se dovedește a fi foarte util."
"OK. Astăzi vreau să vă vorbesc despre copaci , așa că voi începe cu grafice ."
„ Un grafic este un sistem de puncte și linii care le conectează. Punctele sunt numite vârfuri ale graficului, iar liniile sunt numite muchiile graficului. De exemplu:”
„Un grafic este foarte convenabil de utilizat ca model matematic pentru diferite procese și sarcini din lumea reală. Multe sarcini și algoritmi diferiți au fost inventați pentru grafice, așa că sunt folosiți destul de des.”
„ De exemplu, să presupunem că vârfurile sunt orașe, iar marginile sunt drumuri. Apoi, căutarea celui mai scurt drum între orașe devine: „dată un grafic, găsiți calea cea mai scurtă între două vârfuri”.
„Dar calea de la A la B nu este întotdeauna aceeași cu calea de la B la A. Deci, uneori, este de preferat să aveți două linii diferite. Pentru a face acest lucru, liniile (marginile graficului) sunt înlocuite cu săgeți. În cu alte cuvinte, graficul poate avea două săgeți: una de la A la B și alta de la B la A."
„Dacă graficul folosește săgeți, atunci se numește grafic direcționat ; dacă are doar linii, atunci se numește grafic nedirecționat ”.
„Fiecare vârf poate avea propriul său număr de muchii. De asemenea, un vârf poate să nu aibă deloc muchii. În schimb, un vârf poate fi conectat prin muchii la orice alt vârf. Dacă fiecare pereche de vârfuri dintr-un grafic este conectată printr-o muchie, atunci se numește un grafic complet. ”
„Dacă puteți folosi muchii pentru a ajunge la fiecare vârf dintr-un grafic, atunci se numește un graf conectat . Un graf care are trei vârfuri separate și fără muchii este tot un grafic, dar îl numim un graf deconectat .”
„Pentru a forma un graf conectat din N vârfuri, aveți nevoie de cel puțin N-1 muchii. Acest tip de graf se numește arbore.”
„În plus, de obicei, un vârf este ales pentru a fi rădăcina copacului , iar restul sunt declarate a fi ramuri. Ramurile de copac care nu au propriile ramuri se numesc frunze . De exemplu:”
„Dacă fiecare element al arborelui are doi copii, atunci se numește arbore binar . Cu alte cuvinte, pot exista fie 0, fie 2 ramuri. Puteți vedea un arbore binar în dreapta sus.”
„ Un copac se numește arbore binar complet când fiecare ramură are 2 copii și toate frunzele (vârfurile fără copii) sunt pe același rând.”
"De exemplu:"
„De ce este nevoie de acești copaci?”
"Oh, copacii sunt folosiți în multe locuri. În general, arborii binari sunt date structurate sortate."
"Ce-i asta?"
„Da, este foarte simplu. Stocăm o anumită valoare în fiecare vârf. Și fiecare element urmează o regulă: valoarea stocată în copilul din dreapta trebuie să fie mai mare decât valoarea stocată în vârf, iar valoarea stocată în copilul din stânga trebuie să fie mai mare decât valoarea stocată în vârf. să fie mai mică decât valoarea stocată în vârf. Această ordonare face posibilă găsirea rapidă a elementelor arborelui de care aveți nevoie."
— Poți să clarifici ce înseamnă asta?
„Elementele arborelui sunt de obicei sortate prin adăugare. Să presupunem că avem 7 elemente: 13, 5, 4, 16, 8, 11, 10”
„Iată cum sunt adăugate elementele în copac”.
„Dacă căutăm numărul 7 din acest arbore, atunci așa va merge căutarea”
"0) Începeți de la rădăcină."
„1a) Este 7 egal cu 13? Nu”
„1b) Este 7 mai mare decât 13? Nu, așa că ne trecem la subarborele din stânga.”
"2a) Este 7 egal cu 5? Nu."
"2b) Este 7 mai mare decât 5? Da, așa că ne mutăm la subarborele din dreapta."
"3a) Este 7 egal cu 8? Nu"
"3b) Este 7 mai mare decât 8? Nu, așa că ne deplasăm în subarborele din stânga."
"4a) Nu există niciun subarboresc din stânga, ceea ce înseamnă că numărul 7 nu este în arbore."
"Ah. Cu alte cuvinte, trebuie doar să verificăm vârfurile de pe calea de la rădăcină la locația posibilă a numărului dorit. Da, asta este într-adevăr rapid."
„Mai mult, dacă arborele este echilibrat, atunci va trebui să treci doar prin aproximativ 20 de vârfuri pentru a căuta un milion de elemente”.
„Sunt de acord – nu sunt foarte mulți”.
„Ce vrei să spui prin arbore echilibrat?”
„Un copac care nu este distorsionat, adică nu are ramuri lungi. De exemplu, dacă elementele au fost deja sortate când am construit copacul, atunci am fi făcut un copac foarte lung format dintr-o ramură. ”
"Hmm. Ai dreptate. Deci ce facem?"
„După cum probabil ați ghicit deja, cel mai eficient copac are ramuri care au aproximativ aceeași lungime. Apoi, fiecare comparație aruncă cea mai mare parte din subarborele rămas”.
— Deci, trebuie să reconstruim copacul?
„Da. Trebuie să fie „echilibrat” – să fie făcut cât mai aproape posibil de un arbore binar complet.”
„Pentru a rezolva această problemă, s-au inventat arbori cu auto-echilibrare. Dacă arborele devine distorsionat după adăugarea unui element, atunci reordonează ușor elementele pentru a face totul OK. Iată un exemplu de echilibrare:”
„Unii dintre acești copaci sunt cunoscuți ca copaci roșu -negri ”.
„De ce se numesc roșu-negru?”
"Inventatorul lor a desenat toate nodurile folosind două culori. O culoare era roșie, iar cealaltă era neagră. Diferitele vârfuri se supun unor reguli diferite. Aceasta formează întreaga bază pentru procedura de echilibrare."
"De exemplu:"
"Deci care sunt aceste reguli?"
"1) Un vârf roșu nu poate fi copilul unui vârf roșu."
"2) Adâncimea neagră a fiecărei frunze este aceeași (adâncimea neagră se referă la numărul de vârfuri negre de pe calea de la rădăcină)."
„3) Rădăcina copacului este neagră”.
„Nu voi explica cum funcționează asta – probabil că capul tău explodează deja.”
— Da. Procesorul meu scoate puţin fum.
"Iată un link pentru tine. Dacă vrei, poți citi mai multe despre el aici."
Link către material suplimentar
— Și acum, du-te să ia o pauză.
GO TO FULL VERSION