[Powered by Google Translate] [Двайковы пошук] [Патрык Шмід - Гарвардскі універсітэт] [Гэта CS50. - CS50.TV] 

Калі б я даў вам спіс імёнаў Дыснею характару ў алфавітным парадку і спытаў, можна знайсці Мікі Маўса, як бы вы пра гэта? Адзін з відавочных шляхоў было б прагледзець спіс з самага пачатку і праверце кожнае імя, каб убачыць, калі гэта Мікі. Але, як вы праглядаеце Aladdin, Аліса, Арыэль, і гэтак далей, Вы хутка зразумееце, што, пачынаючы з пярэдняй часткі спісу не было добрай ідэяй. Добра, можа быць, вы павінны пачаць працаваць у зваротным кірунку ад канца спісу. Цяпер вы праглядаеце Тарзан, сцежка, Беласнежка, і гэтак далей. Тым не менш, гэта не здаецца, што лепшы спосаб гэта зрабіць. 

Ну, яшчэ адзін спосаб, што вы маглі б ісці пра гэта, каб паспрабаваць звузіць спіс імёнаў, якія ў вас ёсць на што паглядзець. Паколькі вы ведаеце, што яны размешчаны ў алфавітным парадку, Вы проста паглядзіце на імёны ў сярэдзіне спісу і праверыць, калі Мікі Маўса да або пасля гэтага імя. Гледзячы на ​​прозвішча ў другім слупку вы б зразумелі, што M Мікі прыходзіць пасля J для Жасмін, так што вам проста ігнараваць першай палове спісу. Тады вы, напэўна, паглядзіце на верхнюю частку апошняга слупка і бачу, што яна пачынаецца з Рапунцэль. Мікі даходзіць да Рапунцэль, падобна, што мы можам ігнараваць апошняй калонцы, а таксама. Працягваючы стратэгію пошуку, вы хутка зразумееце, што Мікі У першай палове пакінутага спісу імёнаў і, нарэшце, знайсці Мікі хаваецца паміж Мерлін і Міні. 

Тое, што вы толькі што зрабілі быў у асноўным бінарнага пошуку. Як гэта вынікае з назвы, яна выконвае сваю стратэгію пошуку ў бінарным пытанне. Што гэта значыць? Ну, далі сьпіс адсартаваных элементаў, алгарытм бінарнага пошуку робіць двайковых рашэнняў - налева або направа, больш ці менш, у алфавітным парадку, да або пасля - у кожнай кропцы. Цяпер у нас ёсць імя, якое ідзе разам з гэтым алгарытм пошуку, Давайце паглядзім на іншы прыклад, але на гэты раз са спісам адсартаваныя нумары. Скажам, мы шукаем лік 144 у гэтым спісе адсартаваныя нумары. Як і раней, мы знаходзім лік, якое знаходзіцца ў сярэдзіне - які ў дадзеным выпадку складае 13. паглядзець, калі 144 больш ці менш, чым 13. Так як гэта відавочна больш, чым 13, мы можам ігнараваць усё, што складае 13 ці менш і проста засяродзіцца на астатнюю палову. Так як у нас зараз ёсць цотная колькасць прадметы, пакінутыя, Мы проста абраць лік, якое бліжэй да сярэдзіны. У гэтым выпадку мы выбіраем 55. Мы маглі б так жа лёгка абраныя 89. Добра. Зноў жа, 144 больш, чым 55, так што мы ідзем направа. На шчасце для нас, наступнае лік з'яўляецца сярэднім 144, той, які мы шукаем. Так што для таго, каб знайсці 144 з дапамогай двайковага пошуку, мы можам знайсці яго толькі ў 3 этапы. Калі б мы выкарысталі лінейны пошук тут, гэта заняло б нам 12 крокаў. На самай справе, так як гэты метад пошуку палоўкі колькасць элементаў ён павінен глядзець на на кожным кроку, ён знойдзе элемент, ён шукае прыкладна ў часопіс лік элементаў у спісе. Цяпер, калі мы бачылі 2 прыкладу, давайце зірнем на некаторыя псевдокод рэкурсіўнага функцыю, якая рэалізуе бінарны пошук. Пачынаючы з верхняга, мы бачым, што мы павінны знайсці функцыю, якая прымае 4 аргументу: ключ, масіў, мін, макс. Ключ гэты лік, якое мы шукаем, таму 144 у папярэднім прыкладзе. Масіў ўяўляе сабой спіс лікаў, якія мы шукаем. Мінімальная і максімальная з'яўляюцца паказчыкі мінімальнай і максімальнай пазіцыі што мы зараз глядзім. Таму, калі мы пачнем, мін будзе роўная нулю і Макс будзе максімальным індэксам масіву. Як звузіць пошук ўніз, мы будзем абнаўляць мінімальнае і максімальнае быць толькі дыяпазон, які мы ўсё яшчэ шукаем цалі 

Давайце пераходзіць да цікавай часткі першай. Першае, што нам зрабіць, гэта знайсці сярэдзіну, індэкс, які знаходзіцца на паўдарогі паміж мінімальнай і максімальнай масіва, што мы па-ранейшаму разглядаем. Тады мы паглядзім на значэнне масіва ў то сярэдзіна размяшчэння і паглядзець, калі лік, якое мы шукаем менш, чым ключ. Калі лік у гэтай пазіцыі менш, то гэта азначае, што ключ больш, чым усе нумары злева ад гэтай пазіцыі. Такім чынам, мы можам назваць бінарнай функцыі пошуку зноў, але на гэты раз абнаўленню мінімальных і максімальных параметраў прачытаць толькі палову , Што больш або роўная значэнню мы толькі што разгледзелі. З іншага боку, калі ключ менш, чым колькасць у бягучым сярэдзіне масіва, Мы хочам, каб пайсці налева і ігнараваць усе лічбы, якія больш. Зноў жа, мы называем бінарны пошук, але на гэты раз з дыяпазон мінімальных і максімальных абнаўленне , Каб уключыць толькі ніжнюю палову. Калі значэнне на цяперашнім сярэдзіне масіва не з'яўляецца ні больш, ні менш, чым ключ, то яна павінна быць роўная ключ. Такім чынам, мы можам проста вярнуць бягучы індэкс сярэдзіну, і мы зрабілі. Нарэшце, гэтая праверка тут для выпадку, калі лік на самай справе не ў масіў лікаў мы шукаем. Калі максімальны індэкс дыяпазону, які мы шукаем гэта ўсё менш мінімуму, гэта азначае, што мы зайшлі занадта далёка. Паколькі лік не было ў ўваходным масіве, мы вяртае -1 каб паказаць, што нічога не было знойдзена. 

Вы, магчыма, заўважылі, што для гэтага алгарытму на працу, Спіс нумароў павінен быць адсартаваны. Іншымі словамі, мы можам знайсці толькі 144 з дапамогай бінарнага пошуку калі ўсё ліку ўпарадкаваны ад ніжэйшага да вышэйшага. Калі б гэта было не так, мы не змаглі б выключыць палову нумароў на кожным кроку. Таму ў нас ёсць 2 варыянты. Альбо мы можам узяць несортированный спіс і адсартаваць яго перад выкарыстаннем бінарнага пошуку, ці мы можам пераканацца, што спіс лікаў сартуюцца па меры дадання нумары да яе. Такім чынам, замест сартавання толькі тады, калі мы павінны шукаць, чаму б не захаваць спіс, адсартаваны ва ўсе часы? 

Адзін са спосабаў захаваць спіс нумароў адсартаваныя адначасова дазваляючы , Каб дадаць або перамясціць нумары з гэтага спісу з'яўляецца выкарыстанне так званых бінарных дрэў пошуку. Дрэва двайковага пошуку з'яўляецца структурай дадзеных, якая мае 3 ўласцівасці. Па-першае, левага поддерева любога вузла ёсць толькі значэння, якія менш або роўнае значэнне вузла. Па-другое, правае поддерево вузла ёсць толькі значэння, якія больш або роўнае значэнне вузла. І, нарэшце, як левае і правае поддеревья ўсіх вузлоў Таксама бінарныя дрэвы пошуку. Давайце паглядзім на прыклад з тымі ж нумарамі мы выкарыстоўвалі раней. Для тых з вас, хто ніколі не бачыў дрэва інфарматыкі і раней, Дазвольце мне пачаць з аповяду пра тое, што дрэва камп'ютэрныя навукі расце ўніз. Так, у адрозненне ад дрэў вы прывыклі, корань дрэва, камп'ютэрныя навукі знаходзіцца на вяршыні, і лісце ў ніжняй часткі. Кожная скрыначка завецца вузлом, а вузлы злучаны адзін з адным па краях. Так што корань гэтага дрэва з'яўляецца вузлом значэнне з значэннем 13, які мае 2 дзяцей вузлоў са значэннямі 5 і 34. Поддерево дрэва, які ўтворыцца, проста зірнуўшы на падраздзел за ўсё дрэва. 

Напрыклад, левае поддерево вузла 3 з'яўляецца дрэвам створаны вузлы 0, 1, і 2. Такім чынам, калі мы вернемся да ўласцівасцяў бінарнае дрэва пошуку, мы бачым, што кожнаму вузлу ў дрэве адпавядае ўсім 3 ўласцівасці, а менавіта: левае поддерево ўтрымлівае толькі значэння, якія менш або роўна значэнню вузла; правае поддерево ўсіх вузлоў ёсць толькі значэння, якія больш або роўна значэнню вузла, а левага і правага поддеревьев ўсіх вузлоў і дрэвы бінарнага пошуку. Хоць гэта дрэва выглядае па-іншаму, гэта сапраўды бінарнае дрэва пошуку за той жа набор лікаў. На самай справе, існуе мноства магчымых спосабаў, якія вы можаце стварыць сапраўдны бінарнае дрэва пошуку з гэтых нумароў. Ну, давайце вернемся да першага мы стварылі. Так што мы можам зрабіць з гэтымі дрэвамі? Ну, мы можам вельмі проста знайсці мінімальнае і максімальнае значэння. Мінімальныя значэння можна знайсці заўсёды будзе левы пакуль больш няма вузлоў для наведвання. І наадварот, каб знайсці максімальны проста проста спускаецца да правай ў кожны момант часу. 

Пошук любы іншы нумар, які не з'яўляецца мінімальным або максімальным Гэтак жа лёгка. Сказаць, што мы шукаем лік 89. Мы проста правяраем значэнне кожнага вузла і пайсці налева або направа, у залежнасці ад таго, значэнне вузла менш або больш, чым той, які мы шукаем. Такім чынам, пачынаючы з кораня з 13, мы бачым, што 89 больш, і таму мы ідзем направа. Тады мы бачым, вузел 34, і мы зноў ідзем направа. 89 з'яўляецца яшчэ большай, чым 55, так што мы працягваем ісці з правага боку. Мы тады прыдумалі вузел са значэннем 144 і ідзем налева. І вось, 89 тут жа. 

Іншая справа, што мы можам зрабіць, гэта раздрукаваць ўсе лікі, выконваючы сіметрычнага абыходу. Сіметрычнага абыходу азначае друкаваць усё, што ў левым поддереве з наступнай пячаткай самога вузла , А затым з наступнай пячаткай ўсё ў правым поддереве. Напрыклад, давайце возьмем наш каханы бінарнае дрэва пошуку і раздрукаваць ліку ў адсартаваным парадку. Мы пачынаем у корані 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 вышэйзгаданага правілы. Напрыклад, выкажам здагадку, што мы хочам, каб выдаліць каранёвай вузел, 13. Першае, што мы робім, мы знаходзім найбольшае значэнне ў дрэва які, у дадзеным выпадку, 21. Затым памяняйце месцы 2 вузлоў, рашэнняў 13 лісця і 21 цэнтральнага вузла групы. Цяпер мы можам проста выдаліць 13. 

Як згадвалася раней, існуе мноства магчымых спосабаў зрабіць сапраўды бінарнае дрэва пошуку. На жаль для нас, некаторыя з іх горш, чым іншыя. Напрыклад, што адбудзецца, калі мы будуем бінарнае дрэва пошуку ад адсартаваны спіс лікаў? Усе нумары проста дадаў да права на кожным кроку. Калі мы хочам знайсці нумар, у нас няма выбару, але толькі каб паглядзець на праве на кожным кроку. Гэта не лепш, чым лінейны пошук на ўсіх. Хоць мы не будзем разглядаць іх тут, ёсць і іншыя, больш складаныя, структуры дадзеных, каб пераканацца, што гэтага не адбудзецца. Тым не менш, адну простую рэч, што можна зрабіць, каб пазбегнуць гэтага, проста выпадкова змяшаць ўваходных значэнняў. Малаверагодна, што па выпадковасці ператасаваць спіс лікаў сартуецца. Калі б гэта было так, казіно не будзе заставацца ў бізнэсе надоўга. 

Там у Вас ёсць гэта. Цяпер вы ведаеце аб бінарных дрэў пошуку і бінарны пошук. Я Патрык Шмід, і гэта CS50. [CS50.TV] Адзін з відавочных спосабаў будзе сканаваць спіс з ... [сігнал] ... Колькасць элементаў ... ды [Смяецца] ... Апублікаваць вузла 234 ... augh. >> Ура! Гэта было -