[Powered by Google Translate] Jinsi gani unaweza kuwakilisha wanachama wote wako katika familia ya kompyuta? Tunaweza tu kutumia orodha, lakini kuna ngazi ya wazi hapa. 

Hebu sema tuko mwanzo na bibi kubwa-yako, Alice. Yeye ana wana 2, Bob na babu yako, Charlie. Charlie ana watoto 3, mjomba wako, Dave, shangazi yako, Hawa, na baba yako, Fred. Wewe ni mtoto wa Fred tu. 

Kwa nini kuandaa familia yako kwa njia hii kuwa bora zaidi kuliko uwakilishi rahisi orodha? Moja ya sababu ni kwamba hii muundo wa kihierarkia, iitwayo 'mti,' ina habari zaidi kuliko orodha rahisi. Tunajua mahusiano ya kifamilia kati ya kila mtu tu kwa kuchunguza mti. Pia, inaweza kuharakisha kuangalia-up wakati kiasi kikubwa, kama data mti ni Iliyopangwa. 

Hatuwezi kuchukua faida ya kwamba hapa, lakini tutaweza kuona mfano wa hii hivi karibuni. Kila mtu ni kuwakilishwa na nodi kwenye mti. Nodes unaweza kuwa nodes mtoto kama vile nodi mzazi. Haya ni maneno ya kitaalamu hata wakati wa kutumia miti kwa ajili ya mambo badala ya familia. Nodi Alice ina watoto 2 na wazazi, wakati nodi Charlie ana watoto 3 na 1 mzazi. 

nodi jani ni moja kwamba hana watoto wowote makali ya nje ya mti. nodi topmost ya mti, nodi mizizi, hana mzazi. 

mti binary ni aina maalum ya mti, ambayo ina kila node, saa wengi, watoto 2. Hapa ni struct ya nodi ya mti binary katika C. Kila nodi ina baadhi ya data yanayohusiana na hayo na 2 kuyatumia kwa nodes nyingine. 

Katika familia mti wetu, data zinazohusiana ilikuwa jina la kila mtu. Hapa ni int, ingawa inaweza kuwa kitu chochote. Kama zinageuka, mti binary isingekuwa uwakilishi mzuri kwa ajili ya familia, tangu watu mara nyingi kuwa na watoto zaidi ya 2. 

tafuta binary mti ni maalum, aliamuru ya aina ya mti binary ambayo inaruhusu yetu kuangalia maadili haraka. Unaweza kuwa niliona kwamba kila nodi chini mizizi ya mti ni mizizi ya mti mwingine, aitwaye 'subtree.' Hapa, mizizi ya mti ni 6, na mtoto wake, 2, ni mizizi ya subtree. 

Katika mti binary tafuta maadili yote ya nodi haki subtree ni kubwa zaidi kuliko thamani ya nodi. Hapa: 6. Naam, maadili katika subtree nodi wa kushoto wa ni chini ya thamani ya nodi. Kama tunahitaji kushughulikia maadili duplicate, tunaweza kubadili aidha ya wale wa usawa wa huru, maana maadili kufanana unaweza kuanguka ama upande wa kushoto au kulia, muda mrefu kama sisi ni thabiti kuhusu hilo hela. Mti huu ni binary tafuta mti kwa kuwa inafuatia sheria hizi. 

Hii ni jinsi bila kuangalia kama sisi akageuka nodes wote katika structs C. Ona kwamba kama mtoto ni kukosa, pointer ni null. Jinsi gani sisi kuangalia kuona kama ni 7 katika mti? Sisi kuanza katika mizizi. Saba, ni mkubwa kuliko 6, hivyo kama ni katika mti, ni lazima kuwa na haki. Kisha, ni chini ya 8, hivyo ni lazima kushoto. Hapa, tumepata 7. Sasa, sisi itabidi kuangalia kwa 5. Tano ni chini ya 6, hivyo ni lazima kwa upande wa kushoto. Tano, ni mkubwa kuliko 2, hivyo ni lazima kuwa na haki, na pia ni mkuu kuliko 4, hivyo ni lazima haki tena. Hata hivyo, kuna mtoto yeyote hapa. pointer ni null. Hii ina maana kwamba ni 5 si katika mti wetu. 

Tunaweza kutafuta mti binary kwa kificho zifuatazo: Katika kila nodi, sisi kuangalia kuona kama tumepata thamani sisi ni kuangalia kwa. Kama hatuwezi kupata hiyo, sisi kuamua kama ni lazima kuwa na juu na kushoto au kulia kuangalia kwamba subtree. Kitanzi hii itaendelea chini ya mti mpaka hakuna nodi mtoto juu ya aidha kushoto au kulia. 

Kumbuka kwamba 5 hakuwa katika mti. Jinsi gani sisi kuingiza? mchakato inaonekana sawa na kutafuta. Sisi iterate chini mti kuanzia 6, kushoto na 2, haki ya 4, na haki tena, lakini hana mtoto 4 upande huu. Hii itakuwa ni nafasi mpya kwa ajili ya 5, na itakuwa kuanza na watoto. 

Jinsi ya kufunga ni shughuli ya juu ya mti binary search? Kumbuka kwamba Bigohnotation inataka kutoa amefungwa juu. Katika kesi mbaya, mti yetu inaweza tu kuwa orodha zilizounganishwa maana kwamba insertion, kufutwa, na tafuta inaweza kuchukua muda sawia na idadi ya pingili katika mti. Hii ni O (n). 

Kwa mfano, zifuatazo ni halali binary tafuta mti. Hata hivyo, kama sisi kujaribu kupata 9, tuna traverse kila nodi. Ni hakuna bora kuliko orodha zinazoungwa. Kimsingi, sisi wanataka kila nodi ya binary wetu mti tafuta kuwa na watoto 2. Kwa njia hii, insertion, kufuta na tafuta bila kuchukua, saa mbaya, O (logi n) wakati. mti mbele inaweza kuwa zaidi ya uwiano, kama hii. Sasa, akatazama juu thamani yoyote inachukua, saa wengi, 3 hatua. Mti huu ni sawa, maana kwamba ni ndogo ina kina jamaa na idadi ya nodi. 

Kuangalia kwa thamani katika mti uwiano binary tafuta ni sawa na tafuta binary kwenye safu Iliyopangwa. Kwa kweli, kama hatuna haja ya kuingiza au kufuta vitu, wanatenda hasa kwa njia hiyo. Hata hivyo, muundo wa mti ni bora kwa ajili ya kuchukua insertions na kufuta maneno 

Jina langu ni Bannus Van der Kloot. Hii ni CS50.