[Powered by Google Translate] [Двоично търсене]
Патрик Шмид - Харвардския университет]
[Това е CS50. - CS50.TV]
>> Ако ти дам списък на символни имена на Дисни по азбучен ред
и помоли да намеря Мики Маус,
как ще го направите?
Един очевиден начин е да се сканира списък от самото начало
и да проверите всяко име да се види дали е Мики.
Но докато четете Aladdin, Алис, Ариел, и така нататък,
вие бързо ще осъзнаят, че в предната част на списъка не е добра идея.
Добре, може би трябва да започнат да работят назад от края на списъка.
Сега сте прочели Тарзан, Stitch, Снежанка и т.н..
Все пак, това не изглежда като най-добрият начин да стане това.
>> Е, друг начин, по който биха могли да направят това, е да се опитаме да стесните
списък с имена, които трябва да разгледаме.
Тъй като вие знаете, че те са по азбучен ред,
можете просто да погледнете имената в средата на списъка
и проверете дали Мики Маус е преди или след това име.
Поглед към фамилното име във втората колона
вас ще осъзнаят, че М за Мики идва след J за Жасмин,
така че ще просто да игнорират първата половина на списъка.
Тогава може би ще изглежда в началото на последната колона
и да видим, че тя започва с Рапунцел.
Мики идва преди Рапунцел, изглежда можем да игнорираме последната колона, както и.
Продължаване на стратегия за търсене, вие бързо ще видите, че Мики
е в първата половина на останалите списък с имена
и най-накрая намери Мики се крие между Мерлин и Мини.
>> Какво ти направи, беше основно двоично търсене.
Както подсказва името, тя изпълнява стратегията за нейното търсене в двоичен въпрос.
Какво означава това?
Е, като се има предвид, списък на сортираните елементи, алгоритъма за двоично търсене двоичен решение -
наляво или надясно, по-голяма или по-малко, отколкото по азбучен ред преди или след - във всяка точка.
Сега, когато имаме име, което върви заедно с този алгоритъм за търсене,
нека да разгледаме още един пример, но този път със списък на сортирани номера.
Да речем, ние търсим номер 144 в този списък на сортирани номера.
Точно както преди, ние откриваме номер, който е в средата -
който в този случай е 13 - и да видим дали 144 е по-голямо или по-малко от 13.
Тъй като това е ясно по-голяма от 13, ние можем да пренебрегнем всичко, което е 13 или по-малко
и просто се съсредоточи върху останалата половина.
Тъй като ние сега имаме четен брой останали обекти,
ние просто изберете номер, който е близо до средата.
В този случай ние избираме 55.
Бихме могли да са също толкова лесно, избран 89.
Добре. Отново, 144 е по-голяма от 55, така че отиваме в дясно.
За наше щастие, следващия брой на средата е 144,
търсим.
Така че, за да се намери 144 с помощта на двоично търсене, ние сме в състояние да го намерите само в три стъпки.
Ако бихме могли да използва линеен търсене тук, щеше да ни вземат 12 стъпки.
В интерес на истината, тъй като този метод на търсене наполовина броя на елементите
трябва да се търсят на всяка стъпка, тя ще открие елемент тя търси
за регистър на броя на елементите в списъка.
Сега, когато съм виждал два примери, нека да разгледаме
някои pseudocode за рекурсивна функция, която изпълнява двоично търсене.
Започвайки от горната част, виждаме, че ние трябва да се намери функция, която приема четири аргументи:
ключ, масив, мин. и макс.
Ключът е число, което ние търсим, така че 144 в предишния пример.
Array е от списъка с номера, че ние търсим.
Мин и Макс са индексите на минималните и максималните позиции
, че ние сме в момента търси.
Така че, когато ние започваме, мин. ще бъде нула и максимум ще бъде максималният индекс на масива.
Както стесните търсенето, ние ще актуализираме мин. и макс
да бъде само диапазона, че ние все още се търсят инча
>> Нека първо преминете към интересната част.
Първото нещо, което правим, е да се намери на средата,
индекс, който е по средата между мин. и макс на масива, че ние сме все още обмисля.
След това погледнете в стойността на масива на мястото, че средата
и да видим, ако броят, че ние търсим, е по-малък от този ключ.
Ако броят на тази позиция е по-малко,
то това означава, че ключът е по-голям от всички номера, от лявата страна на тази позиция.
Така можем да наречем двоичен отново функция за търсене,
но този път актуализиране на мин. и макс параметри, за да се чете само половината
, която е по-голяма или равна на стойността, ние просто погледна.
От друга страна, ако ключът е по-малко от броя на текущата средата на масива,
искаме да отидем на ляво и игнорира всички номера, които са по-големи.
Отново, ние наричаме двоично търсене, но този път с обхвата на мин. и макс промяна
да включва само долната половина.
Ако стойността на текущата средната точка в масива не е нито
по-голям от нито по-малък от ключа, тогава тя трябва да бъде равна на ключа.
По този начин, ние можем просто да се върне текущия индекс средата и сме готови.
На последно място, тази проверка тук е по делото, че броят
всъщност не е в масива от числа, ние търсим.
Ако максималният индекс на диапазона, че ние търсим
е все по-малко от минималната, това означава, че ние сме отишли ​​твърде далеч.
Тъй като броят им не е във входния масив, връщаме -1
за да покаже, че нищо не е намерен.
>> Може би сте забелязали, че за този алгоритъм за работа,
списък на номерата трябва да бъдат сортирани.
С други думи, ние можем да се намери само 144 двоично търсене
ако всички числа са подредени от най-ниската до най-високата.
Ако това не беше така, нямаше да сме в състояние да изключва половината от номерата на всяка стъпка.
Така че имаме две възможности.
Или можем да се несортиран списък и да го оправи, преди да използвате двоично търсене,
или можем да се уверите, че списъкът от числа се сортират, тъй като ние добавяне на номера към него.
Така, вместо сортиране, точно когато трябва да търсим,
защо да не се съхранява в списъка подредени по всяко време?
>> Един от начините да се поддържа списък на номерата сортират, като същевременно позволява
да добавите един или преместване на номера от този списък
е с помощта на нещо, наречено двоично търсене дърво.
Двоично търсене дърво е структура от данни, която има три свойства.
Първо, ляво поддърво на всеки възел съдържа само стойности, които са по-малко от
или равна на стойността на възела.
Второ, правото поддърво на възел съдържа само стойности, които са по-големи от
или равна на стойността на възела.
И накрая, както лявото и дясното поддървета на всички възли
също са двоични дървета за търсене.
Нека разгледаме един пример със същите номера, които сме използвали по-рано.
За тези от вас, които никога не са виждали дърво компютърни науки преди,
позволете ми да започна, като ви казвам, че компютърни науки дърво расте надолу.
Да, за разлика от дърветата, с които сте свикнали,
корена на дървото компютърни науки е в горната част,
и листата са на дъното.
Всяка малка кутийка се нарича възел, а възлите са свързани помежду си с ръбове.
Така че корените на това дърво е възел стойност със стойност 13,
, която има две деца възли с ценностите, 5 и 34.
Поддърво е дърво, което се формира само като се погледне в подсекция на цялото дърво.
>> Например, в ляво поддърво на възел 3 е дървото е създадена от възли 0, 1 и 2.
Така че, ако се върнем към свойствата на дърво за двоично търсене,
виждаме, че всеки възел в дървото отговаря на всички три имота, а именно,
ляво поддърво съдържа само стойности, които са по-малка или равна на стойността на възела;
правото поддърво на всички възли
съдържа само стойности, които са по-голяма или равна на стойността на възела и
левите, и десните поддървета на всички възли също са дървета за двоично търсене.
Въпреки това дърво изглежда различно, това е валидно двоично търсене дърво
за същия набор от числа.
В интерес на истината, има много възможни начини, по които можете да създадете
валидно двоично търсене дърво от тези номера.
Е, нека се върнем на първия, ние създадохме.
И така, какво можем да направим с тези дървета?
Ами, много просто може да намерите на минималните и максимални стойности.
Минималните стойности могат да бъдат намерени, като винаги ще наляво
докато няма повече възли за посещение.
От друга страна, за да разберете какъв е максималният просто просто слиза на правото по всяко време.
>> Намирането на друг номер, който не е минималната или максималната
е също толкова лесно.
Кажи търсим номер 89.
Ние просто проверка на стойността на всеки възел и отидете наляво или надясно,
в зависимост от това дали стойността на възела е по-малка или по-голяма от
търсим.
Така че, започвайки от корена на 13, ние виждаме, че 89 е по-голяма,
и така отиваме в дясно.
Тогава ще видите възел за 34, и отново отидем в дясно.
89 все още е по-голяма от 55, така че продължи да ходи в правото.
След това излезе с възел със стойността на 144 и отиди на ляво.
Ето и ето, 89 е точно там.
>> Друго нещо, което можем да направим е да отпечатате всички номера чрез извършване на Inorder прекосява.
Един Inorder прекосява означава да отпечатате всичко в лявото поддърво
последвано от печат на възела се
и последвано от печат всичко в дясното поддърво.
Например, нека вземем нашият любим търсене двоичен дърво
и отпечатване на номерата в сортират за
Започваме в основата на 13, но преди печат 13 ние трябва да отпечатате
всичко в лявото поддърво.
Така че ние до 5. Ние все още трябва да навлезем по-дълбоко в дървото, докато не намерим най-лявата възел,
което е равно на нула.
След отпечатването нула, ние се върнем до 1 и изпечата, че навън.
Тогава отиваме право поддърво, което е два и отпечатвате, че от.
Сега, когато сме готови с тази поддърво,
можем да се върнем на 3 и го разпечатате.
Продължавайки назад, отпечатване на 5 и 8.
Сега, когато сме приключили целия напусна поддърво,
можем да отпечатате на 13 и да започнат да работят на правото поддърво.
Ние хоп до 34, но преди печат 34 ние трябва да отпечатате лявата му поддърво.
Така че ние изкарваме 21, а след това да стигнем до отпечатате 34 и посещение на своето право поддърво.
От 55 не е ляво поддърво, ние го разпечатате и да продължи на дясната му поддърво.
144 има ляво поддърво, и така се печата на 89, следвана от 144,
и накрая най-дясната възел на 233.
Има ли го, всички числа са отпечатани в реда от най-ниската до най-високата.
>> Добавяне на нещо на дървото е сравнително безболезнено, както добре.
Всичко, което трябва да направим, е да сме сигурни, че следват три двоични Търсене на имоти дървета
и след това поставете стойност, когато има място.
Да кажем, че искате да вмъкнете стойност 7.
От 7 е по-малко от 13, ние вървим наляво.
Но това е по-голяма от 5, така че ние да премине в дясно.
Тъй като това е по-малко от 8 и 8 е листо възел, добавят от 7 до лявата дете на 8.
Voila! Сме добавили номер на нашето дърво за двоично търсене.
>> Ако можем да се добавят неща, по-добре да бъде в състояние да изтриете неща, както и.
За съжаление за нас, изтриване е малко по-сложно -
не много, но само малко.
Има три различни сценарии, които ние трябва да се помисли
, когато изтривате елементи от двоични дървета за търсене.
Първо, най-лесният случай е, че елементът е листо възел.
В този случай, ние просто го изтриете и да продължим с нашия бизнес.
Да кажем, че искате да изтриете, че ние просто добавя 7.
Е, ние просто го намерите, премахнете, и това е всичко.
Следващият случай е, ако възел има само 1 дете.
Тук можете да изтривате възела, но ние първо трябва да се уверите,
за да се свържете поддърво, че сега е оставено без родители
майка на възела ние просто заличава.
Да кажем, че искате да изтриете три от нашето дърво.
Вземе детето елемент на този възел и я прикрепете към майка на възела.
В този случай, сега сме поставяне на 1 до 5.
Това работи без проблем, защото знаем, в съответствие с двоично търсене на имот дърво
че всичко в лявото поддърво на три по-малко от 5.
Сега, три поддърво се погрижа за него, можем да го изтриете.
Третият и последен случай е най-сложното.
Това е случаят, когато възел искаме да изтриете има две деца.
За да направите това, първо трябва да намерите възел, който има най-голямата стойност,
суап две, и след това да изтриете възел под въпрос.
Обърнете внимание на възел, който е следващата по големина стойност не може да има две деца
тъй като лявата му дете ще бъде по-добър кандидат за следващия по големина.
Ето защо, изтриване възел с две деца възлиза на размяна на два възли,
и след това изтриване се обработва от 1 на 2 горепосочените правила.
Например, нека кажем, че искате да изтриете коренът, 13.
Първото нещо, което правим, е да намерите най-голямата стойност на дървото
, които в този случай, е 21.
След това разменете две възли, което прави 13 листа и 21 централната група възел.
Сега ние можем просто да изтриете 13.
>> Както споменах по-рано, има много възможни начини, за да направи валидна търсене двоичен дърво.
За съжаление за нас, някои от тях са по-лоши от други.
Например, какво се случва, когато ние изграждаме двоично дърво за търсене
от сортиран списък на номерата?
Всички номера са току що добавени към правото на всеки етап.
Когато искаме да търсите за брой,
ние нямаме друг избор, освен само да погледнем в дясно на всяка стъпка.
Това не е по-добре, отколкото линейно търсене на всички.
Въпреки, че ние няма да ги разглеждаме тук, има и други, по-сложни,
структури от данни, които се уверите, че това не се случи.
Въпреки това, едно просто нещо, което може да се направи, за да се избегне това, е
просто случайно разбъркване на входните стойности.
Това е много малко вероятно, че по случаен разбъркано списък от числа се сортират.
Ако това беше така, казина няма да останат в бизнеса за дълго.
>> Има ли го.
Сега вече знаете за двоично търсене и дървета двоично търсене.
Аз съм Патрик Шмид, и това е CS50.
[CS50.TV]
Един очевиден начин е да се сканира списък от ... [BEEP]
... Броя на елементите ... Аха
[Смее се]
... Публикувате възел на 234 ... augh.
>> Ура! Това беше -