[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.