[Powered by Google Translate] [Бинарни Пребарување] [Патрик Шмид - Универзитетот Харвард] [Ова е CS50. - CS50.TV] 

Ако ти даде листа на Дизни карактер имиња по азбучен ред и те праша да се најде Мики Маус, како ќе одат за тоа? Еден очигледен начин ќе биде да го скенира листата од почетокот и проверете секое име да се види дали тоа е Мики. Но, како што ќе прочитате Аладин, Алис, Ариел, и така натаму, вие брзо ќе сфатат дека со почеток во предниот дел на листа не е добра идеја. Океј, можеби ќе треба да почнат да работат наназад од крајот на листата. Сега ќе прочитате Тарзан, бод, Снежана, и така натаму. Сепак, ова не изгледа како на најдобар начин да се обратите за тоа. 

Па, уште еден начин на кој можете да се обратите за тоа е да се обиде да го стесните листа на имиња кои ќе мора да се погледне. Бидејќи знаете дека тие се по азбучен ред, може само да се погледне на имиња во средината на листата и проверете дали Мики Маус е пред или после ова име. Гледајќи презиме во втората колона дека ќе сфатат дека М за Мики доаѓа по J за јасмин, , па можете едноставно ќе ги игнорира првата половина на листата. Тогаш веројатно ќе се погледне на врвот на последната колона и види дека тоа започнува со Rapunzel. Мики доаѓа пред Rapunzel; изгледа како можеме да го игнорираме последната колона, како и. Продолжување на пребарување стратегија, вие брзо ќе се види дека Мики е во првата половина од преостанатите листа на имиња и конечно најде Мики крие меѓу Мерлин и Мини. 

Што ли само не беше во основа бинарни пребарување. Бидејќи ова име имплицира, го врши својата потрага стратегија во бинарен прашање. Што значи ова? Па, со оглед на листа на подредени позиции, бинарна пребарување алгоритам прави бинарни одлука - лево или десно, поголема или помала од, по азбучен ред пред или после - на секоја точка. Сега кога имаме име кое оди заедно со ова пребарување алгоритам, ајде да погледнеме еден пример, но овој пат со листа на подредени броеви. Велат ние сме во потрага по бројот 144 во оваа листа на подредени броеви. Исто како и порано, ги наоѓаме број, кој е во средината - кој во овој случај е 13 - и види дали 144 е поголема или помала од 13. Бидејќи тоа е јасно поголема од 13, ние може да го игнорира она што е 13 или помалку и само се концентрира на преостанатите половина. Бидејќи ние сега имаат дури и број на ставки лево, ние едноставно изберете број кој е блиску до средината. Во овој случај ние да изберат 55. Ние би можеле да исто како лесно избрани 89. Во ред. Повторно, 144 е поголем од 55, па ќе одиме кон десно. За среќа за нас, следниот средината број е 144, оној што го барате. Значи, со цел да се најде 144 користење на бинарни пребарување, ние сме во можност да го најдете во само 3 чекори. Ако ние би ги користеле линеарно пребарување тука, тоа ќе нè однесеше 12 чекори. Како што, впрочем, бидејќи ова пребарување метод половини на бројот на предмети тоа треба да се погледне во на секој чекор, ќе најдете ставка што е во потрага по во врска со најавите на бројот на ставки во листата. Сега дека ние сме виделе 2 примери, ајде да ги разгледаме во некои pseudocode за рекурзивен функција што ја спроведува бинарни пребарување. Почнувајќи од врвот, можеме да видиме дека ние треба да се најде функција која трае 4 аргументи: клуч, низа, мин, и макс. Клучот е бројот што го барате, па 144 во претходниот пример. Низа е на листата на броеви кои се бараат. Мин и макс се индексите на минималната и максималната позиции дека ние сме во моментов во потрага на. Па кога ќе почне, мин ќе биде нула и макс ќе биде максималната индекс на низата. Како што насочите пребарување надолу, ние ќе ги ажурира мин и макс да биде само опсег што ние се уште се гледа внатре 

Ајде да прескокнете на интересен дел во прв план. Првото нешто што ние направите е да најдете средина, на индекс, кој е на половина пат помеѓу MIN и MAX на низата дека ние се уште размислува. Тогаш ние се погледне на вредноста на низата во тоа средина локација и види дали бројот што го барате е помала од онаа клуч. Ако бројот на таа позиција е помала, тогаш тоа значи дека клучот е поголем од сите броеви од лево на таа позиција. Значи можеме да го наречеме бинарни пребарување функција повторно, но овој пат ажурирање на мин и макс параметри за да прочитате само половина што е поголема или еднаква на вредноста ние само погледна. Од друга страна, ако клучот е помал од бројот на моменталната средина на низа, ние сакаме да одиме на лево и да го игнорира сите броеви кои се многу поголеми. Повторно, ние го нарекуваме бинарен за пребарување, но овој пат со спектар на мин и макс ажурирани да се вклучат само на долната половина. Ако вредноста на тековната средина во низа не е ниту поголема од ниту помала од клуч, тогаш тоа мора да биде еднаква на клучот. Така, ние едноставно може да се врати на тековната средина индекс, и ние ќе завршиш. Конечно, оваа проверка е тука за случајот дека бројот всушност не е во низа од броеви што се бараат. Ако максималната индексот на опсег дека ние сме во потрага по е секогаш помал од минималниот, тоа значи дека ние сме отишле предалеку. Бидејќи бројот не беше во влез низа, ние се врати -1 за да се покаже дека ништо не беше пронајдена. 

Може да се забележи дека за овој алгоритам на работа, листата на броеви мора да бидат подредени. Со други зборови, ние може само да најде 144 користење на бинарни пребарување ако сите броеви се подредени од најниските до највисоките. Ако ова не е случај, ние не би можеле да се исклучат половина на броеви во секој чекор. Значи имаме 2 опции. Или можеме да преземе несортиран листа и сортирање пред да го користите бинарни пребарување, или можеме да бидете сигурни дека на листата на броеви се подредени како што ние додадете броеви во неа. Така, наместо на сортирање само кога мораме да пребарување, зошто да не чува листа подредена на сите времиња? 

Еден начин да чувате листа на броеви подредени додека истовремено овозможувајќи еден да додадете или преместување броеви од листата е со користење на нешто што се нарекува бинарен пребарување дрво. А бинарни пребарување дрво е податочна структура која има 3 својства. Прво, лево поддрво на било кој јазол содржи само вредности кои се помалку од или еднаква на вредноста на јазол. Второ, право поддрво на еден јазол содржи само вредности кои се поголеми од или еднаква на вредноста на јазол. И, конечно, и лево и десно subtrees на сите јазли Исто така, бинарна пребарување дрвја. Ајде да погледнеме еден пример со истите бројки што се користи претходно. За оние од вас кои никогаш не сте виделе компјутерски науки дрвото пред, дозволете ми да започне со ти го кажувам дека компјутерски науки дрво расте надолу. Да, за разлика од дрвја сте навикнати да, коренот на компјутерски науки дрво е на врвот, а лисјата се на дното. Секоја мала кутија се нарекува јазол, и јазли се поврзани едни со други преку рабовите. Па коренот на ова дрво е еден јазол вредност со вредноста 13, која има 2 деца јазли со вредностите 5 и 34. А поддрво е дрво, која е формирана само со гледање во подточка на целиот дрво. 

На пример, лево поддрво на јазол 3 е дрво создадена од страна на јазли 0, 1, и 2. Значи, ако ние се вратиме на својствата на бинарни пребарување дрво, можеме да видиме дека секој јазол во стеблото во согласност со сите 3 својства, имено, левата поддрво содржи само вредности кои се помалку од или еднаква на вредноста на јазол; право поддрво на сите јазли содржи само вредности што се поголема или еднаква на вредноста на јазол и лево и десно subtrees на сите јазли, исто така, се бинарни пребарување дрвја. Иако ова дрво изгледа различно, ова е валидна бинарни пребарување дрво за истиот сет на броеви. Како што, впрочем, постојат многу можни начини на кои можете да креирате валидна бинарни пребарување дрво од овие броеви. Па, ајде да се вратиме на првиот ние направивме. Па што ние да правиме со овие дрвја? Па, ние многу едноставно може да се најдат на минималните и максималните вредности. Минималните вредности може да се најде секогаш ќе левата додека не се повеќе јазли да ја посетите. Спротивно на тоа, да се најде на максимум еден едноставно само оди надолу на правото во секое време. 

Наоѓање на било кој друг број кој не е на минимум или максимум е исто така лесно. Велат ние сме во потрага за бројот 89. Ние едноставно проверете на вредноста на секој јазол и да одат на лево или десно, зависност од тоа дали вредноста на јазол е помала или поголема од оној што го барате. Значи, со почеток во коренот на 13, гледаме дека 89 е поголема, и така одиме право. Тогаш можеме да видиме на јазол за 34, и повторно одиме право. 89 е уште поголема од 55, па продолжи да оди кон десно. Ние тогаш се излезе со еден јазол со вредност од 144 и оди кон лево. Еве и овде, 89 е во право таму. 

Друга работа што можеме да направиме е печатење на сите броеви од вршење на inorder traversal. На inorder traversal значи да се печати се надвор во левата поддрво проследено со печатење на јазол себе а потоа следеа од страна на печатење се во право поддрво. На пример, да го земеме нашиот омилен бинарни пребарување дрво и печатење на броеви во подредени цел. Започнуваме во коренот на 13, но пред печатење 13 мораме да испечатите сè во левата поддрво. Значи одиме до 5. Ние сè уште треба да се оди подлабоко во дрво се додека не се најде на левата повеќето јазол, која е нула. По печатење нула, ние одиме назад до 1 и печатење на тоа. Потоа одиме на правото поддрво, што е 2, и печатење на тоа. Сега дека ние сме направиле со тоа поддрво, можеме да одиме назад до 3 и печати ја надвор. Продолжувајќи се врати, ние печати 5, а потоа на 8. Сега кога имаме заврши целиот лево поддрво, ние може да испечатите на 13 и да почне да работи на десната поддрво. Ние хоп до 34, но пред печатење 34 мораме да испечатите неговата лева поддрво. Значи ние печати од 21, а потоа ние да се печати од 34 и посета своето право поддрво. Од 55 нема лево поддрво, ние го испечатите и продолжи да своето право поддрво. 144 има лево поддрво, и така ние се печати од 89, проследено со 144, и конечно на десната повеќето јазол од 233. Таму ќе ја имаат, сите броеви се испечатени со цел од најниските до највисоките. 

Додавајќи нешто на дрвото е релативно безболно, како и. Сите ние треба да направите е да бидете сигурни дека ние ја следиме 3 бинарни пребарување дрво својства и потоа вметнете вредноста каде што постои простор. Да речеме дека сакаме да вметнете вредноста на 7. Од 7 е помалку од 13, ние одиме кон лево. Но, тоа е поголем од 5, па ние напречни десно. Бидејќи тоа е помалку од 8 и 8 е лист јазол, ние го додадете 7 до левата дете на 8. Voila! Додадовме голем број на нашите бинарни пребарување дрво. 

Ако можеме да додадете нешта, подобро да биде во можност да ги избришете работите како добро. За жал за нас, бришење е малку повеќе комплицирано - не многу, но само малку. Постојат 3 различни сценарија дека ние треба да се разгледа кога бришење елементи од бинарниот пребарување дрвја. Прво, најлесниот случај е тоа што елементот е лист јазол. Во овој случај, ние едноставно го избришете и да продолжи со нашиот бизнис. Велат дека сакаме да го избришете 7 дека ние само додаде. Па, ние едноставно го најдете, отстранете ја, и тоа е тоа. Следниот случај е ако јазол има само 1 дете. Тука можеме да ја избришете јазол, но ние прво мора да бидете сигурни за да се поврзете на поддрво дека сега е оставена без родители на родител на јазол ние едноставно избришани. Велат дека сакаме да го избришете 3 од нашите дрво. Земаме дете елемент на тој јазол и прикачете го на родител на јазол. Во овој случај, ние сме сега со приложување на 1 до 5. Оваа работи без проблем, затоа што знаеме, според бинарни пребарување дрво сопственост, дека сè во левата поддрво од 3 беше помалку од 5. Сега дека 3 е поддрво е згрижени, ние може да го избришете. Третата и последна случај е најсложен. Ова е случај кога јазол сакаме да ја избришете има 2 деца. Со цел да го направите ова, ние прво треба да се најде на јазол кој има следниот најголем вредност, трампа на две, а потоа избришете јазол во прашање. Обрнете внимание на јазол кој има следниот најголемата вредност не може да има 2 деца се од неговата лева дете ќе биде подобар кандидат за следниот најголем. Затоа, бришење на јазол со 2 деца изнесува Замена на 2 јазли, а потоа бришење е постапува од страна 1 од 2 наведените правила. На пример, да речеме ние сакаме да го избришете root јазол, 13. Првото нешто што го правиме е ние се најдат на следниот најголемата вредност во дрво кои, во овој случај, е 21. Ние тогаш трампа на 2 јазли, правејќи 13 лист и 21 на централната група јазол. Сега ние едноставно може да избришете 13. 

Како се алудира погоре, постојат многу можни начини да се направи валидна бинарни пребарување дрво. За жал за нас, некои се полоши од другите. На пример, она што се случува кога ќе се изгради бинарни пребарување дрво од Подредена листа на броеви? Сите броеви се само додава на правото на секој чекор. Кога ќе сакате да пребарувате на број, ние немаме друг избор освен само да се погледне на правото на секој чекор. Ова не е подобар од линеарно пребарување на сите. Иако ние не ќе ги покрие тука, постојат и други, посложени, структури на податоци кои бидете сигурни дека тоа не се случи. Сепак, една едноставна работа што може да се направи за да се избегне ова е само случајно shuffle на влезни вредности. Тоа е многу веројатно дека по случаен случајно мешаат листа на броеви се подредени. Ако ова е случај, казина не ќе остане во бизнисот за долго. 

Таму ќе ја имаат. Вие сега знаете за бинарни пребарување и бинарни пребарување дрвја. Јас сум Патрик Шмид, и ова е CS50. [CS50.TV] Еден очигледен начин ќе биде да го скенира листата од ... [ѕвонче] ... На бројот на предмети ... Да [Се смее] ... Испраќате јазол од 234 ... augh. >> Yay! Тоа беше -