[Powered by Google Translate] [Binārā meklēšana] [Patrick Schmid - Hārvarda] [Tas ir CS50. - CS50.TV] 

Ja es tev sarakstu ar Disney raksturs nosaukumiem alfabētiskā secībā un lūdza jums atrast Mickey Mouse, kā jūs iet par to izdarīt? Viens acīmredzams veids būtu skenēt sarakstu no sākuma un pārbaudīt katru vārdu, lai redzētu, vai tas ir Mickey. Bet kā jūs lasīt Aladdin, Alise, Ariel, un tā tālāk, jūs ātri saprast, ka sākot priekšā sarakstā nebija laba ideja. Labi, varbūt jums vajadzētu sākt strādāt atpakaļ no saraksta beigās. Tagad jūs lasīt Tarzan, sašuj, Snow White, un tā tālāk. Tomēr, tas nav šķist labākais veids, kā iet par to. 

Nu, vēl viens veids, ka jūs varētu iet par to izdarīt, ir mēģināt sašaurināt sarakstu vārdi, kas jums ir, lai apskatīt. Tā kā jūs zināt, ka tie ir alfabētiskā secībā, Jūs varētu vienkārši apskatīt nosaukumus vidū saraksta un pārbaudīt, ja Mickey Mouse ir pirms vai pēc šī nosaukuma. Aplūkojot pēdējo vārdu otrajā ailē jūs apzināties, ka M Mickey nāk pēc J Jasmine, tāpēc jūs vienkārši ignorēt pirmo pusi saraksta. Tad jūs, iespējams apskatīt augšpusē pēdējās slejas un redzēt, ka tas sākas ar Rapunzel. Mickey nāk pirms Rapunzel; izskatās, ka mēs varam ignorēt pēdējo aili, kā arī. Turpinot meklēšanas stratēģijas, jūs ātri redzēt, ka Mickey ir pirmajā pusē atlikušo vārdu sarakstu un beidzot atrast Mickey slēpjas starp Merlin un Minnie. 

Ko jūs tikko izdarīja, bija pamatā bināro meklēšanu. Tā kā šis vārds nozīmē, tas veic savu meklēšanu pēc stratēģiju bināro jautājumā. Ko tas nozīmē? Nu, ņemot vērā, sarakstu šķirotas preces, bināro meklēšanas algoritms bināro lēmumu - kreisi vai pa labi, lielāks vai mazāks nekā, alfabētiski pirms vai pēc - katrā punktā. Tagad, kad mums ir vārds, kas iet kopā ar šo meklēšanas algoritmu, pieņemsim apskatīt vēl viens piemērs, bet tas ar sarakstu šķirotu numuriem laiks. Saka, ka mēs meklējam numuru 144 šajā sarakstā sakārtoti numuriem. Tāpat kā līdz šim, mēs atrast numuru, kas ir pa vidu - kas šajā gadījumā ir 13 - un redzēt, ja 144 ir lielāks vai mazāks par 13. Tā kā tas ir acīmredzami lielāka nekā 13 mēs varam ignorēt visu, kas ir 13 vai mazāk un tikai koncentrēties uz atlikušo pusi. Tā kā mums tagad ir pat vienību skaitu pa kreisi, Mēs vienkārši izvēlēties numuru, kas ir tuvu vidū. Šajā gadījumā mēs izvēlamies 55. Mēs varētu būt tikpat viegli izvēlēti 89. Labi. Atkal, 144 ir lielāks par 55, tāpēc mums iet uz labo pusi. Par laimi mums, nākamais vidus skaits ir 144, viens mēs meklējam. Tātad, lai atrastu 144 izmantojot bināro meklēšanu, mēs esam spējīgi atrast tikai 3 soļi. Ja mēs būtu izmantota lineārā meklēt šeit, tas būtu jāņem mums 12 soļiem. Kā Faktiski, jo šī meklēšanas metode pusītes vienību skaitu tas ir skatīties uz katru soli, tas atradīs posteni tiek meklējot kas par žurnālu skaitu posteņu sarakstā. Tagad, ka mēs esam redzējuši 2 piemēri, pieņemsim to apskatīt daži pseudocode par rekursīvs funkciju, kas īsteno bināro meklēšanu. Sākot no augšas, mēs redzam, ka mums ir jāatrod funkciju, kas aizņem 4 argumentus: Galvenais, masīvs, min, un maks. Galvenais ir numurs, ko mēs meklējam, tā 144 iepriekšējā piemērā. Masīvs ir saraksts skaitļu ka mēs meklējam. Min un max ir indeksi minimālo un maksimālo amatos ka mēs šobrīd meklē. Tātad, kad mēs sākam, min būs nulle un maks būs maksimālais indekss masīvā. Kā mēs sašaurinātu meklēšanu uz leju, mēs atjaunināt min un max ir tikai diapazonā, ka mēs joprojām meklējam collas 

Pieņemsim izlaist līdz interesantu daļai pirmās. Pirmā lieta, ko mēs darām, ir atrast viduspunktā, indekss, kas ir pusceļā starp min un max masīva, ka mēs joprojām apsver. Tad mēs apskatīt vērtību masīva šajā viduspunktā vietā un redzēt, ja skaitlis, ko mēs meklējam, ir mazāks nekā šī taustiņa. Ja šajā pozīcijā skaits ir mazāks, tad tas nozīmē, ka galvenais ir lielāks nekā visas numuriem pa kreisi no šīs pozīcijas. Tātad, mēs varam zvanīt bināro meklēšanas funkciju atkal, bet šoreiz atjaunināšanas min un max parametrus, lai lasītu tikai pusi kas ir lielāks vai vienāds ar vērtību mēs vienkārši paskatījās. No otras puses, ja galvenais ir mazāks nekā skaits, ņemot vērā pašreizējo viduspunktā masīva, Mēs gribam doties pa kreisi un ignorēt visus numurus, kas ir lielāka. Atkal, mēs saucam bināro meklēšanu, bet šoreiz ar loku min un max UPDATED iekļaut tikai apakšējo pusi. Ja pie pašreizējā viduspunktā masīvā vērtība ir ne lielāki nekā ne mazāks kā atslēgu, tad tai ir jābūt vienādai ar atslēgu. Tātad, mēs varam vienkārši atgriezties pašreizējo viduspunktā indeksu, un mēs esam darīts. Visbeidzot, šī pārbaude šeit ir lietas, ka numurs faktiski nav masīvā numurus mēs meklējam. Ja maksimālais indekss diapazona ka mēs meklējam ir arvien mazāks par minimāli, tas nozīmē, ka mēs esam aizgājuši pārāk tālu. Tā skaits nebija ieejas masīvs, mēs atgriežamies -1 norādīt, ka nekas netika atrasts. 

Jums var būt ievērojuši, ka šis algoritms darbu, skaitļu saraksts ir sakārtots. Citiem vārdiem sakot, mēs varam atrast tikai 144 izmantojot bināro meklēšanu ja visi skaitļi ir pasūtīts no zemākā līdz augstākajam. Ja tas tā nav, mēs nespētu izslēgt pusi skaitu katrā posmā. Tātad mums ir 2 iespējas. Vai nu mēs varam pieņemt nešķirotu sarakstu un šķirot, pirms to izmanto bināro meklēšanu, vai mēs varam pārliecināties, ka skaitļu saraksts ir sakārtots, jo mēs pievienot numurus uz to. Tātad, tā vietā, šķirošanu tikai tad, kad mums ir jāmeklē, kāpēc ne saglabāt sarakstu sakārtoti visu laiku? 

Viens veids, kā uzturēt sarakstu numurus sakārtoti vienlaikus ļaujot viens pievienot vai pārvietot numurus no šī saraksta ir, izmantojot kaut ko sauc bināro meklēšanas koku. Binārs meklēšanas koks ir datu struktūra, kas ir 3 īpašības. Pirmkārt, pa kreisi apakškoka jebkura mezglā ir tikai vērtības, kas ir mazāk nekā vai vienāds ar mezglu vērtības. Otrkārt, tiesības apakškoka no mezgla tikai satur vērtības, kas ir lielākas nekā vai vienāds ar mezglu vērtības. Un, visbeidzot, gan kreiso un labo subtrees visu mezglu Ir arī bināro meklēšanas koku. Apskatīsim piemēru ar tiem pašiem numuriem mēs izmantojām agrāk. Attiecībā uz tiem no jums, kas nekad nav redzējuši datorzinātnes koks pirms, ļaujiet man sākt ar stāsta jums, ka datorzinātņu koks aug uz leju. Jā, atšķirībā kokiem jums ir pieraduši, No datora zinātnes koku saknes ir augšā, un lapas ir apakšā. Katrs maz kaste sauc mezglā, un mezgli ir saistīti viens ar otru ar malām. Tātad šī koka sakne ir mezglu vērtība ar vērtību 13, kas ir 2 bērni mezglus ar vērtībām 5 un 34. Apakškoka ir koks, kas veidojas tikai skatoties uz apakšiedaļu visa koku. 

Piemēram, kreisā apakškoka no mezgla 3 ir koks, ko rada mezglu 0, 1, 2 un. Tātad, ja mēs ejam atpakaļ uz bināro meklēšanas koku īpašības, mēs redzam, ka katrs koks mezgls atbilst visām 3 īpašībām, proti, kreisi apakškoka satur tikai vērtības, kas ir mazāks vai vienāds ar mezglu vērtības; tiesības apakškoka visu mezglu satur tikai vērtības, kas ir lielāka vai vienāda ar mezglu vērtības un gan kreisās un labās subtrees visu mezglu arī ir binārie meklēšanas koki. Kaut arī šī koks izskatās atšķirīgi, tas ir derīgs bināro meklēšanas koku par tiem pašiem numuriem. Kā Faktiski, ir daudz iespējamie veidi, kā jūs varat izveidot derīgs bināro meklēšanas koku no šiem skaitļiem. Nu, iesim atpakaļ uz pirmo mēs izveidojām. Tātad, ko mēs varam darīt ar šiem kokiem? Nu, mēs varam ļoti vienkārši atrast minimālās un maksimālās vērtības. Minimālās vērtības var atrast, vienmēr dodas uz kreiso pusi līdz nav vairāk mezgli apmeklēt. Savukārt, lai iegūtu maksimālo viens vienkārši tikai iet uz leju pa labi katrā laikā. 

Meklējot kādu citu numuru, kas nav minimālais vai maksimālais ir tikpat vienkārši. Saka, ka mēs meklējam skaita 89. Mēs vienkārši pārbaudītu vērtību katru mezglu un iet pa kreisi vai pa labi, atkarībā no tā, vai mezgla vērtība ir mazāka vai lielāka par viens mēs meklējam. Tātad, sākot saknē 13, redzam, ka 89 ir lielāks, un tāpēc mēs ejam uz labo pusi. Tad mēs redzam mezglu 34, un atkal mēs ejam uz labo pusi. 89 joprojām ir lielāka par 55, tāpēc mēs turpinām iet uz labo pusi. Mēs pēc tam nāk klajā ar mezglu ar vērtību 144 un iet pa kreisi. Lo un redzi, 89 ir labi tur. 

Vēl viena lieta, ko mēs varam darīt, ir izdrukāt visus numurus ar veicot inorder šķērsošana. Inorder šķērsošana nozīmē izdrukāt viss, kas kreisajā apakškoka seko apdrukāšana mezglā pati un pēc tam seko apdrukāšana viss, kas labi apakškoka. Piemēram, pieņemsim mūsu mīļākie bināro meklēšanas koku un izdrukāt skaitļus sakārtoti secībā. Mēs sākam pie saknes 13, bet līdz 13 drukāšanas mums ir izdrukāt viss kreisi apakškoka. Tāpēc mēs ejam līdz 5. Mums vēl ir iet dziļāk kokā līdz mēs atrast kreisās visvairāk mezglā, kas ir nulle. Pēc nulles drukāšanu, mēs ejam atpakaļ līdz 1 un izdrukāt ka out. Tad mēs ejam uz labo apakškoka, kas ir 2, un drukāt, ka out. Tagad, ka mēs esam darīts ar to apakškoka, mēs varam doties atpakaļ līdz 3 un izdrukāt to ārā. Turpinot atpakaļ uz augšu, mēs drukāt 5 un pēc tam 8. Tagad, kad mums ir pabeigts viss atstāja apakškoka, mēs varam izdrukāt 13 un sākt darbu pie labi apakškoka. Mēs hop līdz 34 gadiem, bet pirms 34 drukāšanas mums ir izdrukāt tās kreisajā apakškoka. Tāpēc mēs izdrukāt 21, tad mēs izdrukāt 34 un apmeklēt tās tiesības apakškoka. Tā 55 ir ne pa kreisi apakškoka, mēs to izdrukāt un tālāk uz tās tiesības apakškoka. 144 ir kreisā apakškoka, un tāpēc mēs izdrukāt 89, seko 144, un visbeidzot labo visvairāk mezgla 233. Tur jums ir tas, visi numuri ir izdrukāti, lai no zemākās uz augstāko. 

Pievienojot kaut uz koku ir salīdzinoši nesāpīga, kā arī. Viss, kas mums jādara, ir pārliecināties, ka mēs izpildiet 3 binārā meklēšanas koku īpašības un pēc tam ievietot vērtību, kur ir telpa. Pieņemsim, ka mēs vēlamies, lai ievietotu vērtību 7. Tā 7 ir mazāk nekā 13, mēs ejam pa kreisi. Bet tas ir lielāks par 5, lai mēs traversa pa labi. Tā kā tas ir mazāk nekā 8 un 8 lapu mezglā, mēs pievienojam 7 līdz kreisajā bērnam gada 8. Voila! Mēs esam pievienojuši vairākus mūsu bināro meklēšanas koku. 

Ja mēs varam pievienot lietas, mēs labāk varētu izdzēst lietas, kā arī. Diemžēl mums, dzēšot ir nedaudz sarežģītāk - nav daudz, bet tikai nedaudz. Ir 3 dažādi scenāriji, kas mums ir jāapsver dzēšot elementus no binārā meklēšanas kokiem. Pirmkārt, vienkāršākais lieta ir tā, ka elements ir lapu mezglā. Šajā gadījumā mēs vienkārši izdzēsiet to un iet uz mūsu biznesu. Saka, ka mēs vēlamies izdzēst 7 ka mēs tikko pievienotās. Nu, mēs vienkārši atrast, noņemiet to, un tas arī viss. Nākamais gadījums ir tad, ja mezglā ir tikai 1 bērns. Šeit mēs varam dzēst mezglā, bet mums vispirms ir jāpārliecinās savienot apakškoka kas tagad atstāj parentless uz mātes mezglā mēs vienkārši izdzēsts. Saka, ka mēs vēlamies, lai izdzēstu 3 no mūsu koka. Mēs ņemam bērnu elements šajā mezglā un pievienojiet to mātes mezglā. Šajā gadījumā, mēs tagad pievienojot no 1 līdz 5 x. Tas darbojas bez problēmām, jo ​​mēs zinām, saskaņā ar bināro meklēšanas koku īpašumu, ka kreisajā apakškoka gada 3 viss bija mazāks nekā 5. Tagad, 3'S apakškoka ir rūpēsies, mēs varam izdzēst. Trešais un pēdējais gadījums ir vissarežģītākais. Tas ir gadījums, kad mezglu mēs vēlamies izdzēst ir 2 bērni. Lai to izdarītu, mums vispirms ir jāatrod mezglu, kas ir nākamo lielāko vērtību, swap divus, un pēc tam izdzēsiet mezglu jautājumu. Paziņojums mezglu, kas ir nākamais lielākais vērtību nevar būt 2 bērni sevi jo tās kreisajā bērns būtu labāks kandidāts par nākamo lielāko. Tādēļ, dzēšot mezglu ar 2 bērniem sasniedz pārnešana no 2 mezgliem, un pēc tam atmetot strādājot ar 1 no 2 iepriekšminētos noteikumus. Piemēram, pieņemsim, ka mēs vēlamies izdzēst saknes mezglā, 13. Pirmā lieta, ko mēs darām, ir mums atrast nākamo lielāko vērtību kokā kas šajā gadījumā ir 21. Mēs tad mijmaiņas 2 mezglus, padarot 13 lapu un 21 Centrālā grupa mezglā. Tagad mēs varam vienkārši izdzēst 13. 

Kā pieminēja iepriekš, ir daudz iespējamie veidi, kā padarīt derīgu bināro meklēšanas koku. Diemžēl mums, daži ir sliktāks nekā citi. Piemēram, kas notiek, ja mēs izveidotu bināro meklēšanas koku no sakārtoti sarakstu numuriem? Visi numuri ir tikai pievienota labi pie katra soļa. Ja mēs gribam, lai meklētu numuru, Mums nav citas izvēles, bet tikai apskatīt labi pie katra soļa. Tas nav labāk nekā lineāri meklēšanā vispār. Kaut arī mēs nesedz tos šeit, tur ir citi, daudz sarežģītāka, datu struktūras, kas padara pārliecināts, ka tas nenotiek. Tomēr viena vienkārša lieta, ko var darīt, lai izvairītos no šī ir līdz tikai nejauši shuffle ievades vērtībām. Tas ir ļoti maz ticams, ka ar izlases izredzes iegrozījās sarakstu numuriem ir sakārtots. Ja tas tā būtu, kazino nevarētu palikt biznesā uz ilgu laiku. 

Tur jums ir to. Jūs tagad zināt par bināro meklēšanu un bināro meklēšanas koku. Es esmu Patriks Schmid, un tas ir CS50. [CS50.TV] Viens acīmredzams veids būtu skenēt sarakstu no ... [pīkstiens] ... Vienību skaits ... yep [Smejas] ... Post mezgla 234 ... augh. >> Yay! Tas bija -