[Powered by Google Translate] Paano mo ire-kumatawan sa lahat ng iyong mga miyembro ng pamilya sa isang computer? Kami maaaring gamitin lamang ng isang listahan, ngunit may isang malinaw na hierarchy dito. 

Ipagpalagay natin na kami ay nagsisimula sa iyong lola sa tuhod, Alice. Siya ay may 2 anak, Bob at ang iyong lolo, Charlie. Charlie ay may 3 bata, iyong tiyuhin, Dave, iyong tiyahin, Eba, at ang iyong ama, Fred. Ikaw lamang Fred bata. 

Bakit-aayos ng iyong mga miyembro ng pamilya sa ganitong paraan maging mas mahusay kaysa sa simpleng representasyon ng listahan? Isang kadahilanan ay na ito hierarchical istraktura, tinatawag na 'puno,' ay naglalaman ng karagdagang impormasyon kaysa sa isang simpleng listahan. Alam namin ang familial relasyon sa pagitan ng lahat lamang sa pamamagitan ng pagsusuri sa puno. Gayundin, maaari itong mapabilis ang hitsura-up na oras tremendously, kung puno data ay pinagsunod-sunod. 

Hindi namin maaaring samantalahin na dito, ngunit gagamitin namin makita ang isang halimbawa ng mga ito sa lalong madaling panahon. Ang bawat tao ay kinakatawan ng isang node sa tree. Node node anak pati na rin bilang isang magulang na node. Ito ang mga teknikal na mga tuntunin, kahit na kapag gumagamit ng puno para sa mga bagay bukod sa mga pamilya. Alice ng node ay may 2 bata at walang mga magulang, habang ang Charlie ng node ay may 3 bata at 1 magulang. 

Isang dahon node ay isa na ay hindi magkakaroon ng anumang mga bata sa labas gilid ng puno. Ang pinakamataas na node ng puno, ang root node, ay walang magulang. 

Isang puno ng binary ay isang partikular na uri ng puno, na node ang bawat isa ay, sa pinakamarami, 2 bata. Narito ang struct ng isang node ng isang binary puno sa C. Node bawat ay may ilang mga data na nauugnay dito at 2 pointer sa iba pang mga node. 

Sa aming pamilya puno, ang mga kaugnay na data ay ang pangalan ng bawat tao. Narito ito ay isang int, bagaman maaari itong maging anumang. Bilang ito ay lumiliko out, isang binary tree ay hindi magiging isang mahusay na representasyon para sa isang pamilya, dahil ang mga tao ay madalas na may higit sa 2 bata. 

Ang isang binary puno ng paghahanap ay isang espesyal na, na nakaayos uri ng binary puno na nagbibigay-daan sa amin upang tingnan ang halaga nang mabilis. Maaaring napansin mo ang bawat node sa ibaba ang ugat ng isang puno ay ang root ng ibang puno, na tinatawag na 'subtree.' Narito, ang mga ugat ng puno ay 6, at sa bata, 2, ay ang root ng isang subtree. 

Sa isang binary puno ng paghahanap ang lahat ng mga halaga ng isang node karapatan subtree ay mas mataas kaysa sa halaga ang node. Dito: 6. Well, ang mga halaga sa kaliwa subtree isang node ay mas mababa kaysa sa halaga ang node. Kung kailangan namin ang mga duplicate na halaga, Maaari naming baguhin ang alinman sa mga ng maluwag na hindi pagkakapareho, ibig sabihin magkakahawig na mga halaga ay maaaring mahulog sa alinman sa kaliwa o kanan, hangga't namin pare-pareho ang tungkol dito sa buong. Punong kahoy na ito ay isang binary puno ng paghahanap dahil ito ay sumusunod sa mga panuntunang ito. 

Ito ay kung paano hitsura nito ay magiging kung naka-namin ang lahat ng mga node sa C structs. Pansinin na kung ang isang bata ay nawawala, pointer ay null. Paano namin suriin upang makita kung 7 sa tree? Simulan namin sa root. Pitong mas malaki kaysa sa 6, kaya kung ito ay sa tree, dapat itong maging sa kanan. Pagkatapos, mas mababa sa 8, kaya dapat itong iwanang. Dito, aming natagpuan 7. Ngayon, susuriin namin para sa 5. Limang ay mas mababa sa 6, kaya dapat itong maging sa kaliwa. Limang mas malaki kaysa sa 2, kaya dapat itong karapatan, at ito ay din mas malaki sa 4, kaya dapat itong kanan muli. Subalit, may bata hindi dito. Pointer ay null. Nangangahulugan ito na 5 ay wala sa aming puno. 

Maaari naming maghanap sa binary puno na may mga sumusunod na code: Sa bawat node, suriin namin upang makita kung namin nahanap ang halaga na aming hinahanap. Kung hindi namin mahanap ito, namin matukoy kung ito ay kailangang maging sa kaliwa o kanan at suriin na subtree. Loop na ito ay patuloy ang tree hanggang doon ay walang anak node sa alinman sa kaliwa o kanan. 

Tandaan na ang 5 ay hindi sa tree. Paano namin ipasok ito? Ang proseso ay mukhang katulad upang maghanap. Namin umulit tree na nagsisimula mula 6, kaliwa sa 2, karapatan sa 4, at sa muli, ngunit 4 ay hindi anak sa bandang ito. Ito ang magiging bagong posisyon para sa 5, at ito ay magsimula sa walang mga bata. 

Kung gaano kabilis ang pagpapatakbo sa isang binary puno ng paghahanap? Tandaan na Bigohnotation naglalayong magbigay ng isang pang-itaas bound. Sa pinakamasama kaso, aming puno ay maaaring lamang ay isang naka-link na listahan na nangangahulugan na ang pagpapasok ng, pagtanggal, at paghahanap Maaaring tumagal ng oras na proporsyonal sa ang bilang ng mga node sa tree. Ito ay O (n). 

Halimbawa, ang mga sumusunod ay isang may-bisang puno ng binary paghahanap. Gayunpaman, kung sinusubukan naming upang mahanap 9, mayroon kami sa pagbagtas bawat node. Ito ay walang mas mahusay kaysa sa isang naka-link na listahan. May perpektong, namin gusto ang bawat node ng aming puno ng paghahanap ng binary sa 2 bata. Ganitong paraan, ang pagpapasok ng, pagtanggal at paghahanap ay tumagal, sa pinakamalala, O (log n) oras. Ang puno mula sa bago maaaring maging mas balanced, tulad nito. Ngayon, hinahanap anumang halaga tumatagal, hindi hihigit sa, 3 hakbang. Puno na ito ay balanced, kahulugan na may minimal na lalim kaugnay sa bilang ng mga node. 

Naghahanap para sa isang halaga sa isang balanseng puno ng binary paghahanap ay katulad sa binary paghahanap sa isang pinagsunod-sunod array. Sa katunayan, kung hindi namin kailangan upang ipasok o tanggalin ang mga item, kumikilos sila eksaktong parehong paraan. Gayunman, ang isang mala-punong balangkas ay mas mahusay para sa handling pagpapasok at pagtanggal 

Ang pangalan ko ay ng Bannus Van der Kloot. Ito ay CS50.