Mti wa utafutaji wa binary - hifadhidata iliyopangwa iliyo na nodi, viungo viwili vya nodi zingine, kulia na kushoto. Nodi ni kitu cha darasa ambacho kina data, na NULL ni ishara inayoashiria mwisho wa mti.
Mara nyingi hujulikana kama BST, ambayo ina sifa maalum: nodi kubwa kuliko mzizi ziko upande wake wa kulia, na ndogo zaidi upande wa kushoto.
Nadharia ya jumla na istilahi
Katika mti wa utafutaji wa binary, kila nodi, bila kujumuisha mzizi, imeunganishwa kwa ukingo ulioelekezwa kutoka nodi moja hadi nyingine, inayoitwa mzazi. Kila mmoja wao anaweza kushikamana na idadi ya kiholela ya nodes, inayoitwa watoto. Nodes bila "watoto" huitwa majani (nodes za nje). Vipengele ambavyo sio majani huitwa ndani. Nodi zilizo na mzazi sawa ni ndugu. Nodi ya juu kabisa inaitwa mzizi. Katika BST, kabidhi kipengee kwa kila nodi na uhakikishe kuwa wana sifa maalum iliyowekwa kwa ajili yake.
istilahi za miti:
- Kina cha nodi ni nambari ya kingo iliyofafanuliwa kutoka kwa mzizi hadi kwake.
- Urefu wa nodi ni nambari ya kingo iliyofafanuliwa kutoka kwayo hadi kwenye jani la ndani kabisa.
- Urefu wa mti huamuliwa na urefu wa mzizi.
- Mti wa utafutaji wa njia mbili ni muundo maalum, hutoa uwiano bora wa urefu na idadi ya nodi.
- Urefu h na nodi N zaidi ya O (logi N).
Unaweza kuthibitisha hili kwa urahisi kwa kuhesabu nodi katika kila ngazi, kuanzia mzizi, ukichukulia kuwa ina idadi kubwa zaidi yazo: n=1 + 2 + 4 + … + 2 h-1 + 2 h.=2 h + 1 - 1 Kutatua hili kwa h kunatoa h=O (logi n).
Faida za mbao:
- Akisi uhusiano wa kimuundo wa data.
- Inatumika kuwakilisha madaraja.
- Hakikisha usakinishaji na utafutaji unaofaa.
- Miti ni data inayoweza kunyumbulika sana, hukuruhusu kuhamisha miti midogo kwa bidii kidogo.
Njia ya utafutaji
Kwa ujumla, ili kubaini kama thamani iko katika BST, anzisha mti wa utafutaji wa mfumo shirikishi kwenye mzizi wake na ubaini ikiwa inakidhi mahitaji:
- kuwa kwenye mzizi;
- kuwa katika mti mdogo wa kushoto wa mzizi;
- katika mti mdogo wa kulia wa mzizi.
Ikiwa hakuna rejista ya msingi imeridhika, utafutaji wa kujirudia unafanywa katika mti mdogo unaolingana. Kuna chaguo mbili za kimsingi:
- Mti hauna kitu - rudisha uongo.
- Thamani iko kwenye nodi ya mzizi - rudisha kweli.
Ikumbukwe kwamba mti wa utafutaji wa binary wenye utaratibu ulioendelezwa kila mara huanza kutafuta kwenye njia kutoka kwenye mzizi hadi kwenye jani. Katika hali mbaya zaidi, huenda hadi kwenye jani. Kwa hiyo, wakati mbaya zaidi ni sawa na urefu wa njia ndefu zaidi kutoka kwenye mizizi hadi jani, ambayo ni urefu wa mti. Kwa ujumla, hapa ndipo unapohitaji kujua inachukua muda gani kutafuta kama kipengele cha kukokotoa cha idadi ya thamani zilizohifadhiwa kwenye mti.
Kwa maneno mengine, kuna uhusiano kati ya idadi ya nodi katika BST na urefu wa mti, kulingana na "umbo" wake. Katika hali mbaya zaidi, nodes zina mtoto mmoja tu, na mti wa utafutaji wa binary wenye usawa ni orodha iliyounganishwa. Kwa mfano:
50
/
10
15
30
/
20
Mti huu una nodi 5 na urefu=5. Kupata maadili katika safu ya 16-19 na 21-29 itahitaji njia ifuatayo kutoka kwa mzizi hadi kwenye jani (nodi iliyo na thamani 20), i.e., itachukua muda sawia na idadi ya nodi. Bora zaidi, wote wana watoto 2, na majani yanapatikana kwa kina sawa.
Mti huu wa utafutaji wa binary una nodi 7 na urefu=3. Kwa ujumla, mti kama huu (mti kamili) utakuwa na urefu wa takriban logi 2 (N), ambapo N ni idadi ya nodi kwenye mti.. Thamani ya kumbukumbu 2 (N) ni idadi ya nyakati (2) ambazo N inaweza kugawanywa kabla ya sifuri kufikiwa.
Kufupisha: wakati mbaya zaidi unaohitajika kutafuta katika BST ni O (urefu wa mti). Mti mbaya zaidi wa "mstari" ni O (N), ambapo N ni idadi ya nodi kwenye mti. Bora zaidi, mti "kamili" ni O(logi N).
BST kuingiza jozi
Ninashangaa ni wapi panafaa kuwanode mpya iko katika BST, unahitaji kuelewa mantiki, lazima iwekwe mahali ambapo mtumiaji anaipata. Kwa kuongeza, unahitaji kukumbuka sheria:
- Nakala rudufu haziruhusiwi, kujaribu kuingiza thamani iliyorudiwa kutaondoa ubaguzi.
- Mbinu ya kuingiza hadharani hutumia mbinu ya "msaidizi" ya kujirudia rudia ili kuingiza.
- Njia iliyo na thamani mpya kila wakati huwekwa kama jani katika BST.
- Njia ya kuingiza hadharani hurejesha utupu, lakini mbinu ya msaidizi hurejesha nodi ya BST. Inafanya hivi ili kushughulikia kesi ambapo nodi iliyopitishwa kwake ni batili.
Kwa ujumla, mbinu ya usaidizi inaonyesha kuwa ikiwa mti asilia wa utafutaji wa binary hauna kitu, matokeo yake ni mti wenye nodi moja. Vinginevyo, matokeo yatakuwa kiashirio kwa nodi ile ile ambayo ilipitishwa kama hoja.
Kufuta katika mfumo wa mfumo wa jozi
Kama unavyoweza kutarajia, kufuta kipengele kunahusisha kutafuta nodi ambayo ina thamani ya kuondolewa. Kuna mambo kadhaa katika msimbo huu:
- BST hutumia kisaidia, mbinu ya kufuta iliyojaa kupita kiasi. Ikiwa kipengele unachotafuta hakiko kwenye mti, basi njia ya msaidizi hatimaye itaitwa n==null. Hii haizingatiwi kuwa kosa, mti haubadilika tu katika kesi hii. Mbinu ya kisaidizi cha kufuta hurejesha thamani - kiashirio kwa mti uliosasishwa.
- Jani linapoondolewa, kuondolewa kutoka kwa mti wa utafutaji wa mfumo shirikishi huweka kielekezi kinacholingana cha mtoto cha mzazi wake kubatilisha, au mzizi kubatilisha iwapo kinachoondolewanodi ni mzizi na haina watoto.
- Kumbuka kwamba simu ya kufuta lazima iwe mojawapo ya yafuatayo: root=delete (root, key), n.setLeft (delete (n.getLeft (), key)), n.setRight (delete(n. getRight(), ufunguo)). Kwa hivyo, katika visa vyote vitatu ni sawa kwamba njia ya kufuta inarudi tu batili.
- Utafutaji wa nodi iliyo na thamani ya kufutwa unapofaulu, kuna chaguzi tatu: nodi ya kufutwa ni jani (haina watoto), nodi ya kufutwa ina mtoto mmoja, ina mbili. watoto.
- Kifundo kinachoondolewa kina mtoto mmoja, unaweza kubadilisha na mtoto, na kurudisha kielekezi kwa mtoto.
- Ikiwa nodi ya kufutwa ina sifuri au watoto 1, basi mbinu ya kufuta "itafuata njia" kutoka kwenye mzizi hadi nodi hiyo. Kwa hivyo wakati mbaya zaidi ni sawia na urefu wa mti, kwa utafutaji na kuingiza.
Ikiwa nodi ya kuondolewa ina watoto wawili, hatua zifuatazo huchukuliwa:
- Tafuta nodi ya kufutwa, kwa kufuata njia kutoka kwenye mzizi kwenda humo.
- Tafuta thamani ndogo zaidi ya v katika mti mdogo wa kulia, ukiendelea kwenye njia inayoelekea kwenye jani.
- Ondoa thamani ya v kwa kujirudia, fuata njia sawa na katika hatua ya 2.
- Hivyo, katika hali mbaya zaidi, njia kutoka kwenye mizizi hadi kwenye jani hufanywa mara mbili.
Mpangilio wa mapito
Traversal ni mchakato unaotembelea nodi zote kwenye mti. Kwa sababu mti wa utafutaji wa C binary ni muundo wa data usio na mstari, hakuna upitishaji wa kipekee. Kwa mfano, wakati mwingine algorithms kadhaa za kupitaimejumuishwa katika aina mbili zifuatazo:
- kina cha kuvuka;
- pasi ya kwanza.
Kuna aina moja tu ya kuvuka upana - kukwepa kiwango. Mzunguko huu wa kutembelea nodi ngazi ya chini na kushoto, juu na kulia.
Kuna aina tatu tofauti za vivuko vya kina:
- Kupitisha Agizo la Awali - kwanza tembelea mzazi kisha mtoto wa kushoto na kulia.
- Passing InOrder - kumtembelea mtoto wa kushoto, kisha mzazi na mtoto wa kulia.
- Past PostOrder - kumtembelea mtoto wa kushoto, kisha mtoto wa kulia, kisha mzazi.
Mfano wa mapito manne ya mti wa utafutaji wa binary:
- Agizo la Mapema - 8, 5, 9, 7, 1, 12, 2, 4, 11, 3.
- InOrder - 9, 5, 1, 7, 2, 12, 8, 4, 3, 11.
- PostOrder - 9, 1, 2, 12, 7, 5, 3, 11, 4, 8.
- LevelOrder - 8, 5, 4, 9, 7, 11, 1, 12, 3, 2.
Kielelezo kinaonyesha mpangilio ambao nodi hutembelewa. Nambari 1 ni nodi ya kwanza katika kipito fulani, na 7 ni nodi ya mwisho.
Njia hizi za jumla zinaweza kuwakilishwa kama algoriti moja, ikizingatiwa kuwa kila nodi hutazamwa mara tatu. Ziara ya Euler ni kutembea kuzunguka mti wa jozi ambapo kila kingo huchukuliwa kama ukuta ambao mtumiaji hawezi kuuvuka. Katika matembezi haya, kila nodi itatembelewa ama upande wa kushoto, au chini, au kulia. Ziara ya Euler, ambayo hutembelea nodi zilizo upande wa kushoto, husababisha kihusishi kupitiwa. Wakati nodi zilizo chini zinatembelewa, hupitiwa kwa mpangilio. Na wakati nodi za kulia zinatembelewa - patakupita hatua kwa hatua.
Urambazaji na Utatuzi
Ili kurahisisha kuelekeza kwenye mti, tengeneza vipengele ambavyo hukagua kwanza ikiwa ni mtoto wa kushoto au kulia. Ili kubadilisha nafasi ya nodi, lazima kuwe na ufikiaji rahisi wa pointer kwenye nodi ya mzazi. Kutekeleza mti kwa usahihi ni ngumu sana, kwa hivyo unahitaji kujua na kutumia michakato ya kurekebisha. Mti wa utafutaji wa binary wenye utekelezaji mara nyingi huwa na viashiria ambavyo havionyeshi mwelekeo wa safari.
Ili kubaini haya yote, kipengele cha kukokotoa kinatumika ambacho hukagua kama mti unaweza kuwa sahihi, na kusaidia kupata hitilafu nyingi. Kwa mfano, inakagua ikiwa nodi ya mzazi ni nodi ya mtoto. Na assert(is_wellformed(mizizi)) makosa mengi yanaweza kupatikana mapema. Kwa kutumia sehemu kadhaa za kutatuliwa ndani ya chaguo hili la kukokotoa, unaweza pia kubainisha ni kiashiria kipi si sahihi.
Function Konsolenausgabe
Kitendo hiki huelekeza mti mzima kwenye kiweko na kwa hivyo ni muhimu sana. Agizo ambalo lengo la pato la mti linatekelezwa ni:
- Ili kufanya hivi, kwanza unahitaji kubainisha ni taarifa gani itatolewa kupitia nodi.
- Na pia unahitaji kujua urefu na upana wa mti ili kuhesabu ni nafasi ngapi ya kuondoka.
- Vitendaji vifuatavyo vinakokotoa maelezo haya kwa mti na kila mti mdogo. Kwa kuwa unaweza tu kuandika kwa mstari wa kiweko kwa mstari, utahitaji pia kuchapisha mstari wa mti kwa mstari.
- Sasa tunahitaji njia nyingine ya kujiondoamti mzima, si mstari kwa mstari tu.
- Kwa usaidizi wa kitendakazi cha utupaji taka, unaweza kusoma mti na kuboresha kwa kiasi kikubwa algoriti ya utoaji, kwa kadiri ya kasi inavyohusika.
Hata hivyo, chaguo hili la kukokotoa litakuwa gumu kutumia kwenye miti mikubwa.
Nakili kijenzi na kiharibu
Kwa sababu mti si muundo mdogo wa data, ni bora utekeleze kiunda nakala, kiharibu, na opereta mgawo. Mwangamizi ni rahisi kutekeleza kwa kurudia. Kwa miti mikubwa sana, inaweza kushughulikia "lundo kufurika". Katika kesi hii, imeundwa mara kwa mara. Wazo ni kuondoa jani linalowakilisha thamani ndogo zaidi ya majani yote, hivyo ni upande wa kushoto wa mti. Kukata majani ya kwanza hutengeneza mapya, na mti huo husinyaa hadi kukoma kuwapo tena.
Kiunda nakala pia kinaweza kutekelezwa kwa kujirudia, lakini kuwa mwangalifu ikiwa ubaguzi utatupwa. Vinginevyo, mti haraka unachanganya na unakabiliwa na makosa. Ndiyo sababu toleo la kurudia linapendekezwa. Wazo ni kupitia mti wa zamani na mti mpya, kama vile ungefanya kwa mharibifu, na kuunda nodi zote zilizo kwenye mti wa zamani lakini sio mpya.
Kwa mbinu hii, utekelezaji wa mti wa utafutaji wa binary huwa katika hali nzuri kila wakati na unaweza kuondolewa na kiharibifu hata katika hali isiyokamilika. Ikiwa ubaguzi utatokea, unachohitaji kufanya ni kuamuru mharibifu kufuta mti uliomalizika. mwendeshaji wa kaziinaweza kutekelezwa kwa urahisi kwa kutumia Copy & Swap.
Kuunda mti wa utafutaji wa binary
Miti mojawapo ya utafutaji wa mfumo wa jozi ina ufanisi wa ajabu ikisimamiwa ipasavyo. Baadhi ya sheria za miti ya utafutaji ya binary:
- Nodi ya mzazi ina angalau nodi 2 za watoto.
- Njia ya mtoto ya kushoto kila wakati huwa ndogo kuliko nodi ya mzazi.
- Nodi halali ya mtoto kila wakati huwa kubwa kuliko au sawa na nodi ya mzazi.
Safu ambayo itatumika kuunda mti wa utafutaji wa mfumo wa jozi:
- Mkusanyiko kamili wa thamani saba katika mpangilio ambao haujapangwa.
- Thamani ya kwanza katika safu ni 10, kwa hivyo hatua ya kwanza ya kujenga mti ni kuunda nodi ya mizizi 10, kama inavyoonyeshwa hapa.
- Kwa seti ya nodi za mizizi, maadili mengine yote yatakuwa watoto wa nodi hii. Ukirejelea sheria, hatua ya kwanza kuchukuliwa ili kuongeza 7 kwenye mti ni kulinganisha na nodi ya mizizi.
- Ikiwa thamani ya 7 ni chini ya 10, itakuwa nodi ya kushoto ya mtoto.
- Ikiwa thamani ya 7 ni kubwa kuliko au sawa na 10, itasogezwa kulia. Kwa kuwa 7 inajulikana kuwa chini ya 10, imeteuliwa kama nodi ya kushoto ya mtoto.
- Fanya ulinganisho wa kujirudia kwa kila kipengele.
- Kwa kufuata mchoro sawa, fanya ulinganisho sawa dhidi ya thamani ya 14 katika mkusanyiko.
- Kulinganisha thamani 14 na nodi ya mzizi 10, ukijua kuwa 14 ndiye mtoto sahihi.
- Kupitia safu,fika 20.
- Anza kwa kulinganisha safu na 10, yoyote kubwa zaidi. Kwa hivyo nenda kulia na ulinganishe na 14, ana zaidi ya miaka 14 na hana mtoto upande wa kulia.
- Sasa kuna thamani ya 1. Kwa kufuata muundo sawa na maadili mengine, linganisha 1 hadi 10, ukienda kushoto na kulinganisha na 7 na hatimaye kwa mtoto 1 wa kushoto wa nodi ya 7.
- Ikiwa thamani ni 5, linganisha na 10. Kwa kuwa 5 ni chini ya 10, pita kushoto na ulinganishe na 7.
- Kwa kujua kuwa 5 ni chini ya 7, endelea chini ya mti na ulinganishe 5 na thamani 1.
- Ikiwa 1 hana mtoto na 5 ni mkubwa kuliko 1, basi 5 ni mtoto halali wa nodi 1.
- Mwishowe weka thamani 8 kwenye mti.
- Wakati 8 ni chini ya 10, isogeze upande wa kushoto na ulinganishe na 7, 8 ni kubwa kuliko 7, kwa hivyo isogeze kulia na ukamilishe mti, na kufanya 8 kuwa mtoto anayefaa wa 7.
Kupata na kutathmini umaridadi rahisi wa miti bora ya utafutaji wa mfumo wa binary. Kama mada nyingi katika upangaji, nguvu ya miti ya utafutaji ya binary inatokana na uwezo wake wa kutatua data katika vipengele vidogo vinavyohusiana. Kuanzia sasa na kuendelea, unaweza kufanya kazi na mkusanyiko kamili wa data kwa njia iliyopangwa.
Masuala Yanayowezekana ya Utafutaji wa Binary
Miti ya utafutaji kwa njia mbili ni nzuri, lakini kuna tahadhari chache za kukumbuka. Kawaida zinafaa tu ikiwa zina usawa. Mti wenye usawa ni mti ambao ndani yaketofauti kati ya urefu wa miti ndogo ya nodi yoyote kwenye mti ni angalau moja. Hebu tuangalie mfano ambao unaweza kusaidia kufafanua sheria. Hebu tufikirie kwamba safu huanza kama ya kupangwa.
Ukijaribu kutekeleza algoriti ya mti wa utafutaji wa binary kwenye mti huu, itafanya kazi sawasawa kana kwamba inarudiwa tu kupitia safu hadi thamani inayohitajika ipatikane. Nguvu ya utafutaji wa binary iko katika uwezo wa kuchuja haraka thamani zisizohitajika. Wakati mti hauko sawia, hautatoa faida sawa na mti uliosawazishwa.
Ni muhimu sana kuchunguza data ambayo mtumiaji anafanya kazi nayo wakati wa kuunda mti wa utafutaji wa mfumo wa binary. Unaweza kujumuisha taratibu kama vile mpangilio nasibu kabla ya kutekeleza mti wa utafutaji wa binary kwa nambari kamili ili kusawazisha.
Mifano ya kukokotoa utafutaji kwa njia mbili
Tunahitaji kubainisha ni aina gani ya mti itatokea ikiwa 25 itawekwa kwenye mti ufuatao wa utafutaji wa binary:
10
/
/
5 15
/ /
/ /
2 12 20
Unapoingiza x kwenye mti T ambao bado hauna x, ufunguo x huwekwa kila wakati kwenye jani jipya. Kuhusiana na hili, mti mpya utaonekana kama:
10
/
/
5 15
/ /
/ /
2 12 20
25
Utapata mti wa aina gani ikiwa utaingiza 7 kwenye mti ufuatao wa utafutaji wa binary?
10
/
/
5 15
/ /
/ /
2 12 20
Jibu:
10
/
/
/
5 15
/
/
2 7 12 20
Mti wa utafutaji wa binary unaweza kutumika kuhifadhi kitu chochote. Faida ya kutumia mti wa utaftaji wa binary badala ya orodha iliyounganishwa ni kwamba ikiwa mti una usawa na zaidi kama mti "kamili" kuliko "mstari", uwekaji, utaftaji, na shughuli zote za kufuta zinaweza kutekelezwa ili kutekelezwa. Saa ya O(logi N).
