[Powered by Google Translate] [Binary Axtarış] [Patrick Schmid - Harvard Universiteti] [Bu CS50 edir. - CS50.TV] 

Mən əlifba sırası ilə siz Disney xarakterli adları siyahısı verdi və Mickey Mouse tapmaq üçün xahiş necə bunu barədə getmək istəyirsiniz? Bir Aşkar şəkildə əvvəldən siyahısını scan olacaq və Mickey varsa görmək üçün hər ad oldu. Amma s Ələddin, Alice, Ariel, oxumaq və kimi, tez siyahısına qarşısında başlayan yaxşı bir fikir deyil ki, həyata lazımdır. OK, bəlkə siz siyahısına sonunda geri iş başlamaq lazımdır. İndi Tarzan, Stitch, Qar Ağ və s oxuyun. Still, bu barədə getmək üçün ən yaxşı yol kimi görünür deyil. 

Yaxşı, siz bunu edə bilər ki, başqa yol daraltmak üçün cəhd edir siz baxmaq ki, adları siyahısı. Əgər onlar əlifba sırası bilirik ildən, Siz yalnız siyahısı ortasında adları baxmaq bilər Mickey Mouse bu ad əvvəl və ya sonra əgər və yoxlamaq. İkinci sütun son adı baxanda siz ki, Mickey M Jasmine üçün J sonra gəlir reallaşdırmaq istədiyiniz siz sadəcə siyahısının birinci yarısında ignore ediyorum. Sonra yəqin ki, son sütun üst baxmaq istədiyiniz və Rapunzel başlayır görürük. Mickey Rapunzel əvvəl gəlir, biz də son sütun iqnor edə bilər kimi görünür. Axtarış strategiya davam etdirərək, tez görəcəksiniz ki, Mickey adları qalan siyahısı birinci yarısında edir və nəhayət Mickey Merlin və Minnie arasında gizli tapa bilərsiniz. 

Yalnız nə əsasən ikili axtarış idi. Bu adı nəzərdə tutur ki, bu ikili məsələ öz axtarış strategiya həyata keçirir. Bu nə deməkdir? Yaxşı, sıralanır əşyaların siyahısını nəzərə alaraq, ikili axtarış alqoritm ikili qərar qəbul edir - sol və ya sağ, daha çox və ya daha az əvvəl və ya sonra əlifba sırası ilə çox - hər bir nöqtədə. İndi bu axtarış alqoritmi ilə yanaşı gedir ki, bir adı var ki, nin başqa bir misal baxaq, lakin bu zaman sıralanır nömrələri siyahısı. Biz sıralanır nömrələri bu siyahıda sayı 144 axtarır söyləyin. Əvvəl istəyirəm Sadəcə, biz ortada olan sayı tapmaq - Bu halda 13 - və 144-dən çox və ya 13-dən az olduqda görürük. O 13-dən çox aydın böyük olduğundan, biz 13 və ya daha az hər şeyi iqnor edə bilər və yalnız yarım qalan üzərində. Biz sol maddələr daha da sayı, çünki biz sadəcə orta yaxındır ki, bir sıra seçin. Bu halda biz 55 seçin. Biz yalnız asanlıqla 89 seçilmiş ola bilər. Okay. Yenə 144 55 daha böyükdür, belə ki, biz doğru gedin. Xoşbəxtlikdən bizim üçün, növbəti orta sayı 144-dir biz aradığınız bir. Ikili istifadə edərək 144 tapmaq üçün üçün, biz yalnız 3 adımda ildə tapa istəyirik. Burada xətti axtarış istifadə etsəniz, bu bizə 12 addımlar olardı. Əslində kimi, ildən bu axtarış metodu maddələr sayı yarıya indirir hər addımda baxmaq var, onu axtarır maddə tapa siyahısında maddələrin sayı log haqqında. İndi 2 nümunələr gördük ki, in nəzər edək binar axtarış həyata rekursiv funksiya üçün bəzi pseudocode. Üst başlayaraq, biz 4 arqumentlər edir ki, funksiyası tapmaq lazımdır ki, bax: əsas, dizi, min və max. Əsas biz əvvəlki Məsələn belə 144, axtarır ki sayı. Array biz axtarış ki nömrələri siyahısı. Min və max minimum və maksimum vəzifələrin göstəriciləri var Hal-hazırda baxırıq ki. Beləliklə, biz başlattığınızda, min sıfır olacaq və max serialın maksimum göstərici olacaq. Biz axtarış kiçildə kimi, min və max yeniləyir biz hələ daxil axtarır ki, yalnız bir sıra olmaq 

Ilk maraqlı hissəsi keçmək edək. Biz ilk şey, orta tap ortasında biz hələ nəzərdən ki, serialın min və max arasında olduğunu index. Sonra biz orta yerdə serialın dəyəri baxmaq biz axtarır ki sayı əsas az olduqda və görürük. Ki, vəziyyəti sayı az olarsa, sonra əsas ki, vəziyyəti sol bütün nömrələri daha böyük deməkdir. Beləliklə, biz yenə ikili axtarış funksiyası zəng edə bilərsiniz lakin bu zaman yalnız yarısı oxumaq min və max parametrləri updating ki və ya daha çox biz yalnız baxdı dəyəri bərabərdir. Digər tərəfdən, əsas serialın cari orta olan saydan az olarsa, biz sola getmək və daha çox olan bütün nömrələr ignore etmək istəyirəm. Yenə min və max Updated çeşidi ilə ikili axtarış lakin bu zaman zəng yalnız aşağı yarım daxildir. Serialın cari orta olan dəyəri nə varsa, daha böyük, nə də əsas daha kiçik, o, əsas bərabər olmalıdır. Beləliklə, biz sadəcə, mövcud orta göstərici ola bilər, və biz tamamlayın. Nəhayət, burada bu çek halda üçün ki sayı biz axtarış nömrələr sıra həqiqətən deyil. Əgər biz axtarır ki, bir sıra maksimum index minimum daha heç azdır ki, biz çox getdi sonra deməkdir. Sayı daxil array deyil olduğundan, biz -1 qayıtmaq heç bir şey qeyd edib. 

Siz, bu alqoritm işləmək üçün qeyd ola bilər nömrələrin siyahısına sıralanır var. Başqa sözlə, biz yalnız ikili axtarış istifadə edərək 144 tapa bilərsiniz bütün nömrələri aşağı olan ən yüksək əmr olunur. Bu halda deyil, biz hər addımda nömrələri yarısı istisna edə bilməz. Belə ki, 2 variantları var. Ya biz, ikili axtarış istifadə edərək əvvəl çeşidlənməmiş siyahısını almaq və sıralayabilirsiniz və ya biz bu nömrələrin əlavə kimi nömrələrin siyahısına sıralanır əmin edə bilərsiniz. Belə ki, əvəzinə biz axtarmaq üçün yalnız zaman çeşidlənməsi ki, niyə hər zaman sıralaması siyahısını saxlamaq deyil? 

Eyni zamanda imkan isə nömrələrin siyahısını saxlamaq üçün bir yol sıralanır Bu siyahı sayı əlavə və ya hərəkət ikili axtarış ağac deyilən bir şey istifadə edir. A ikili axtarış ağac 3 xüsusiyyətləri var ki, data strukturu. Birincisi, hər node sol subtree az olan yalnız dəyərlər şey və ya node dəyəri bərabər. İkincisi, bir node hüququ subtree yalnız daha çox olan dəyərləri ehtiva və ya node dəyəri bərabər. Bütün qovşaqlarının və nəhayət, sol və sağ subtrees həm də ikili axtarış ağacları daxildir. Biz əvvəllər istifadə olunan eyni nömrə ilə nümunə baxaq. Kompüter elm ağac əvvəl görüldü heç vaxt olan sizin üçün, Mənə bir kompüter ağac aşağı artır ki, siz izah edərək başlamaq imkan verir. Bəli, vərdiş ağaclar fərqli olaraq, kompüter elm ağac kökü, üst edir və yarpaqları altında var. Hər bir kiçik qutu bir node adlandırırlar və qovşaqlarının kənarları bir-birinə bağlıdır. Belə ki, bu ağacın kökü, dəyəri 13 ilə node dəyəri hansı dəyərlər 5 və 34 ilə 2 uşaq qovşaqlarının var. A subtree yalnız bütün ağac bir alt bölüm baxaraq formalaşır ki, ağac. 

Məsələn, node 3-sol subtree the qovşaqlarının 0, 1, 2 yaratdığı ağac. Belə ki, biz ikili axtarış ağac xüsusiyyətləri geri əgər, biz, ağac hər node yəni bütün 3 xassələri uyğun bax sol subtree yalnız az və ya node dəyəri eyni dəyərlər ehtiva edir; bütün qovşaqlarının hüququ subtree yalnız daha çox və ya node dəyəri eyni dəyərlər ehtiva edir; və bütün qovşaqlarının sol və sağ, həm də subtrees də ikili axtarış ağacları daxildir. Bu ağac müxtəlif görünür baxmayaraq, bu düzgün ikili axtarış ağac ədəd eyni üçün. Əslində kimi, yaratmaq bilər ki, çox mümkün yolları var bu nömrələr cari ikili axtarış ağac. Yaxşı, biz yaradılmış ilk bir geri imkan verir. Belə ki, bu ağacları ilə nə edə bilər? Bəli, biz çox sadəcə minimum və maksimum dəyərləri tapa bilərsiniz. Minimum dəyərlər həmişə sola gedərək bilər səfər çox qovşaqlarının var qədər. Əksinə, maksimum tapmaq üçün sadəcə yalnız hər vaxt doğru enir. 

Hər hansı digər sayı tapmaq minimum və ya maksimum deyil kimi asandır. Biz sayı 89 aradığınız söyləyin. Biz sadəcə, hər bir node dəyəri kontrol və sol və ya sağ getmək node dəyəri az və ya daha çox olub asılı olaraq biz aradığınız bir. Belə ki, 13-kök başlayaraq, biz 89 daha çox olduğunu görürük və biz doğru gedin. Sonra 34 üçün node görmək və yenə biz doğru gedin. 89 hələ 55-dən çox, belə ki, biz doğru gedir davam edir. Biz 144 dəyəri ilə node ilə gəlmək və sol gedin. Yalnız və dərhal, 89 sağ var. 

Biz nə edə bilər ki, başqa bir şey bir inorder traversal həyata tərəfindən bütün nömrələri çap edir. Bir inorder traversal sol subtree hər şeyi çap etmək deməkdir node özü çap izlədi və sonra sağ subtree hər şeyi həyata çap izlədi. Məsələn, bizim sevimli ikili axtarış ağac qoy və sorted üçün nömrələri çap. Biz 13-kök başlamaq, lakin çap 13 əvvəl çap etmək sol subtree hər şey. Belə ki, 5 gedin. Biz hələ ki, sol ən node tapmaq qədər ağac daha aşağı getmək olan sıfır. Çap sıfır sonra, biz 1-geri getmək və çap. Sonra 2 olan, sağ subtree getmək və çap. İndi biz ki, subtree ilə tamamlayın biz 3-geri getmək və onu çap edə bilərsiniz. Qədər geri davam, biz 8 sonra 5 çap və. İndi biz bütün başa ki, subtree sol biz 13 çap və sağ subtree haqqında iş başlaya bilərsiniz. Biz 34-aşağı hop, amma çap 34 əvvəl biz onun sol subtree çap var. Belə ki, 21 çap, sonra biz 34 çap və onun sağ subtree ziyarət almaq. 55 heç sol subtree ildən, biz onu çap və onun sağ subtree üçün davam edir. 144 bir sol subtree var və belə biz, 144 sonra 89 çap 233 və nəhayət sağ ən node. Burada o, bütün nömrələri aşağı olan ən yüksək üçün çap olunur. 

Ağac bir şey əlavə həmçinin nisbətən ağrısız edir. Biz bütün biz 3 ikili axtarış ağac xassələri riayət əmin edir yer olduğu və sonra dəyər daxil edin. Gəlin biz 7 dəyəri daxil etmək istəyirik deyirlər. 7-dən az 13 olduğu üçün, sol gedin. Lakin 5-dən böyük, buna görə biz doğru axır. Bu 8 və 8 bir yarpaq node deyil az olduğundan, biz 8-sol uşaq üçün 7 əlavə edin. İşte! Biz ikili axtarış ağac bir sıra əlavə etdik. 

Biz şeyi əlavə edə bilərsiniz, biz daha yaxşı həmçinin şeyi silmək mümkün. Təəssüf ki, bizim üçün, silmə bir az daha mürəkkəbdir - çox, lakin yalnız bir az deyil. Hesab edirik ki, 3 müxtəlif ssenariləri var binar axtarış ağac elementləri silerken. Birincisi, asan iş element bir yarpaq node olmasıdır. Bu halda, biz sadəcə silin və biznes ilə getmək. Biz yalnız əlavə edib ki, 7 silmək istədiyiniz söyləyin. Bəli, biz sadəcə tapmaq, aradan qaldırılması və bu. Node yalnız 1 uşaq var növbəti haldır. Burada node silə bilərsiniz, ancaq ilk əmin etmək indi kimsəsiz qalan subtree qoşulmaq üçün node və valideyn biz yalnız silindi. Biz ağac 3 silmək istədiyiniz söyləyin. Biz node uşaq element almaq və node müəssisənin əlavə edin. Bu halda, biz indi 5 1 əlavə edirik. Biz bilirik çünki Bu, ikili axtarış ağac əmlak görə, problem olmadan işləyir 3-sol subtree ki, hər şey az 5 idi. 3 in subtree qayğı indi ki, biz onu silə bilərsiniz. Üçüncü və son halda ən kompleksidir. Biz silmek, istədiyiniz node 2 övladı var Bu belədir. Bunu etmək üçün, biz ilk, növbəti ən böyük dəyəri var ki, node tapmaq iki dəyişdirmək və sonra bu node silin. Növbəti böyük dəyər 2 uşaq özü ola bilməz ki node edək onun sol uşaq növbəti böyük üçün daha yaxşı namizəd olacağını ildən. Buna görə də, 2 övladı bir node silmə, 2 qovşaqlarının dəyişdirmə təşkil və sonra silmek 2 yuxarıda qeyd olunan qaydalarına 1 işləndiyini. Məsələn, qoy biz kök node, 13 silmək istəyirsiniz. Biz ilk şey biz ağac növbəti böyük dəyər tapmaq deyil ki, bu halda, 21-dir. Biz 13 bir yarpaq və 21 mərkəzi qrup node edilməsi, 2 qovşaqlarının dəyişdirmək. İndi biz sadəcə 13 silə bilərsiniz. 

Əvvəllər üçün alluded, cari ikili axtarış ağac etmək üçün bir çox mümkün yolları var. Təəssüf ki, bizim üçün, bəziləri daha pisdir. Biz ikili axtarış ağac qurmaq Məsələn, nə olar sayı sıralanır siyahısı? Bütün nömrələri yalnız hər bir addım doğru əlavə olunur. Biz bir sıra axtarmaq istəyirsinizsə, biz heç bir seçimi var, lakin yalnız hər bir addım doğru baxmaq. Bu bütün xətti axtarış daha yaxşı deyil. Biz burada onları əhatə edəcək, baxmayaraq ki, daha mürəkkəb, digər var Bu baş vermir ki, əmin olun data strukturlar. Lakin, bu qarşısını almaq üçün edilə bilər ki, sadə bir şey deyil yalnız təsadüfi shuffle giriş dəyərlər. Bu təsadüfi təsadüfən nömrələri qarışdırılmış siyahısı çeşidlənir ehtimalı var. Bu halda olsaydı, kazinolarda uzun iş qalmaq olmaz. 

Burada var. İndi ikili axtarış və ikili axtarış ağac bilirik. Mən Patrick Schmid oldum və bu CS50 edir. [CS50.TV] Bir Aşkar yolu siyahısını scan olardı ... [beep] ... Əşyaların sayı ... yep [Gülür] ... 234 ... augh və node göndərin. >> Yay! Idi -