"Hi, Amigo!"
"Hello, Rishi!"
"Nakita ko ang aking mga lumang tala doon at naghanda ako ng ilang kawili-wiling materyal para sa iyo. Sa tingin ko ay magiging interesado kang marinig ito."
"Pakinggan natin ito. Palagi kang nakakahanap ng isang bagay na kawili-wili na sa ibang pagkakataon ay nagpapatunay na lubhang kapaki-pakinabang."
"OK. Ngayon gusto kong sabihin sa iyo ang tungkol sa mga puno , kaya magsisimula ako sa mga graph ."
" Ang graph ay isang sistema ng mga punto at linya na nag-uugnay sa kanila. Ang mga punto ay tinatawag na vertices ng graph, at ang mga linya ay tinatawag na mga gilid ng graph. Halimbawa:"
"Ang isang graph ay napaka-maginhawang gamitin bilang isang mathematical na modelo para sa iba't ibang mga proseso at gawain sa totoong mundo. Maraming iba't ibang mga gawain at algorithm ang naimbento para sa mga graph, kaya medyo madalas na ginagamit ang mga ito."
"Halimbawa, ipagpalagay na ang mga vertice ay mga lungsod, at ang mga gilid ay mga kalsada. Pagkatapos, ang paghahanap para sa pinakamaikling kalsada sa pagitan ng mga lungsod ay nagiging: «mabigyan ng graph, hanapin ang pinakamaikling landas sa pagitan ng dalawang vertices». "
"Ngunit ang landas mula A hanggang B ay hindi palaging pareho sa landas mula B hanggang A. Kaya, kung minsan ay mas gusto ang pagkakaroon ng dalawang magkaibang linya. Upang gawin ito, ang mga linya (mga gilid ng graph) ay pinapalitan ng mga arrow. Sa sa madaling salita, ang graph ay maaaring magkaroon ng dalawang arrow: isa mula A hanggang B, at isa pa mula B hanggang A."
"Kung ang graph ay gumagamit ng mga arrow, kung gayon ito ay tinatawag na isang nakadirekta na graph ; kung mayroon lamang itong mga linya, kung gayon ito ay tinatawag na isang hindi nakadirekta na graph ."
"Ang bawat vertex ay maaaring magkaroon ng sarili nitong bilang ng mga gilid. Ang isang vertex ay maaari ding walang mga gilid . ito ay tinatawag na kumpletong graph. "
"Kung maaari mong gamitin ang mga gilid upang maabot ang bawat taluktok sa isang graph, kung gayon ito ay tinatawag na isang konektadong graph. Ang isang graph na may tatlong magkahiwalay na mga vertice at walang mga gilid ay isang graph pa rin, ngunit tinatawag namin itong isang nakadiskonektang graph."
"Upang bumuo ng konektadong graph mula sa N vertices, kailangan mo ng hindi bababa sa N-1 na mga gilid. Ang ganitong uri ng graph ay tinatawag na puno."
"Bukod dito, karaniwang isang vertex ang pinipili upang maging ugat ng puno , at ang iba ay idineklara bilang mga sanga. Ang mga sanga ng puno na walang sariling mga sanga ay tinatawag na dahon . Halimbawa:"
"Kung ang bawat elemento ng puno ay may dalawang anak, kung gayon ito ay tinatawag na binary tree . Sa madaling salita, maaaring mayroong alinman sa 0 o 2 sanga. Makakakita ka ng binary tree sa kanang itaas."
" Ang isang puno ay tinatawag na isang kumpletong binary tree kapag ang bawat sanga ay may 2 anak, at ang lahat ng mga dahon (mga vertices na walang mga bata) ay nasa parehong hilera."
"Halimbawa:"
"Bakit kailangan ang mga punong ito?"
"Oh, ang mga puno ay ginagamit sa maraming lugar. Sa pangkalahatan, ang mga binary tree ay pinagsunod-sunod na structured data."
"Ano yan?"
"Oo, napakasimple nito. Nag-iimbak kami ng isang tiyak na halaga sa bawat vertex. At ang bawat elemento ay sumusunod sa isang panuntunan: ang halagang nakaimbak sa kanang bata ay dapat na mas malaki kaysa sa halagang nakaimbak sa tuktok, at ang halaga na nakaimbak sa kaliwang bata ay dapat mas mababa sa halagang nakaimbak sa vertex. Ginagawang posible ng pag-order na ito na mabilis na mahanap ang mga elemento ng puno na kailangan mo."
"Maaari mo bang linawin kung ano ang ibig sabihin nito?"
"Ang mga elemento ng puno ay karaniwang pinagbubukod-bukod sa pamamagitan ng pagdaragdag. Ipagpalagay na mayroon tayong 7 elemento: 13, 5, 4, 16, 8, 11, 10"
"Narito kung paano idinagdag ang mga elemento sa puno."
"Kung hinahanap natin ang numero 7 sa punong ito, kung gayon ay ganito ang magiging paghahanap"
"0) Magsimula sa ugat."
"1a) Ang 7 ba ay katumbas ng 13? Hindi"
"1b) Mas malaki ba ang 7 sa 13? Hindi, kaya lumipat tayo sa kaliwang subtree."
"2a) Ang 7 ba ay katumbas ng 5? Hindi."
"2b) Mas malaki ba ang 7 sa 5? Oo, kaya lumipat tayo sa kanang subtree."
"3a) Ang 7 ba ay katumbas ng 8? Hindi"
"3b) Mas malaki ba ang 7 sa 8? Hindi, kaya lumipat tayo sa kaliwang subtree."
"4a) Walang natitirang subtree, ibig sabihin ang numero 7 ay wala sa puno."
"Ah. Sa madaling salita, kailangan lang nating suriin ang mga vertices sa landas mula sa ugat hanggang sa magiging lokasyon ng nais na numero. Oo, iyon ay talagang mabilis."
"Higit pa, kung balanse ang puno, kakailanganin mo lamang na dumaan sa mga 20 vertices upang maghanap ng isang milyong elemento."
"Sumasang-ayon ako - hindi iyon masyadong marami."
"Ano ang ibig mong sabihin ng balanseng puno?"
"Isang puno na hindi baluktot, ibig sabihin, walang mahahabang sanga. Halimbawa, kung ang mga elemento ay pinagsunod-sunod na noong itinayo natin ang puno, kung gayon ay gumawa tayo ng napakahabang puno na binubuo ng isang sanga. "
"Hmm. Tama ka. So anong gagawin natin?"
"Tulad ng malamang na nahulaan mo na, ang pinaka mahusay na puno ay may mga sanga na humigit-kumulang sa parehong haba. Pagkatapos ay itinatapon ng bawat paghahambing ang pinakamalaking bahagi ng natitirang subtree."
"So, kailangan nating buuin muli ang puno?"
"Oo. Kailangan itong «balanse» — upang gawin nang mas malapit hangga't maaari sa isang kumpletong binary tree."
"Upang lutasin ang problemang ito, naimbento ang mga puno sa pagbalanse sa sarili. Kung nasira ang puno pagkatapos magdagdag ng isang elemento, bahagyang inaayos nito ang mga elemento upang maging OK ang lahat. Narito ang isang halimbawa ng pagbabalanse:"
"Ang ilan sa mga punong ito ay kilala bilang mga pulang -itim na puno."
"Bakit sila tinatawag na pula-itim?"
"Ang kanilang imbentor ay gumuhit ng lahat ng mga vertices gamit ang dalawang kulay. Ang isang kulay ay pula, at ang isa ay itim. Ang iba't ibang mga vertex ay sumusunod sa iba't ibang mga panuntunan. Ito ang bumubuo ng buong batayan para sa pamamaraan ng pagbabalanse."
"Halimbawa:"
"So ano ang mga patakarang ito?"
"1) Ang isang pulang vertex ay hindi maaaring maging anak ng isang pulang taluktok."
"2) Ang itim na lalim ng bawat dahon ay pareho (itim na lalim ay tumutukoy sa bilang ng mga itim na vertices sa landas mula sa ugat)."
"3) Ang ugat ng puno ay itim."
"Hindi ko ipapaliwanag kung paano ito gumagana — malamang sumasabog na ang ulo mo."
"Oo. Ang aking processor ay nagbibigay ng kaunting usok."
"Narito ang isang link para sa iyo. Kung gusto mo, maaari mong basahin ang higit pa tungkol dito."
"At ngayon, magpahinga ka na."
GO TO FULL VERSION