[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. >> Ура! Це було -