Теорія алгоритмів

Лекція 6:

Тема: Бінарні дерева пошуку. Загальні властивості. Пошук. Додавання та видалення.

План:

1. Загальна класифікація алгоритмів пошуку

2. Алгоритми пошуку

3. Алгоритм бінарного пошуку

Одній з найбільш фундаментальних операцій є пошук.

Пошук - знаходження якої-небудь конкретної інформації у великому об'ємі раніше зібраних даних.

Кажучи про пошук, ми матимемо на увазі якийсь масив даних, а шукати будемо певний елемент в цьому масиві. Оптимальність пошуку для простоти визначимо дуже конкретно - це швидкість роботи алгоритму.

Знайти оптимальний алгоритм, не прив'язуючись при його виборі до умови завдання - це ілюзія.

Немає найоптимальнішого алгоритму в абстрактному сенсі. Вибір його дуже сильно залежить від умови завдання, яке доводиться вирішувати.

Загальна класифікація алгоритмів пошуку

Всі методи можна розділити на статичних і динамічних. При статичному пошуку масив значень не міняється під час роботи алгоритму. Під час динамічного пошуку масив може перебудовуватися або змінювати розмірність.

Уявіть собі, що Ви шукаєте слово в словнику. Як би Ви його не шукали, Ваш агорітм обов'язково буде статичним, оскільки сам словник ( масив слів ) не змінюватиметься під час пошуку. Якщо звичайно не видирати з нього сторінки.

Прикладом динамічного пошуку може служити спроба знайти певну карту в колоді. Відкладаючи убік непотрібні карти, Ви полегшуєте собі завдання пошуку, зменшуючи кількості карт в колоді, що залишилися, які ще потрібно перебрати, тим самим перебудовувавши масив значень під час пошуку!

Так само методи пошуку можна розділити на методи, що використовують дійсні ключі і на методи, що працюють по перетворених ключах. В даному випадку "ключем" називають те значення, яке ми шукаємо.

Пошук в колоді карт - пошук по дійсних ключах, тобто маєте справу з тим, що є. Пошук в словнику - пошук по перетворених ключах, оскільки всі слова відсортовані в алфавітному порядку, тобто масив значень змінений перед початком пошуку. Цей порядок створений спеціально для полегшення пошуку і зовсім не є природним для списку слів!

Алгоритми пошуку

Спробуємо вирішити просту задачу - знайти потрібне значення в масиві. На цьому першому прикладі розглянемо як оптимальність рішення залежить від того, в якому масиві ми шукатимемо.

Перед Вами колода гральних карт, в ній, як правило, 54 карти ( ну або 36 ). Карти лежать безладно. Необхідно знайти певну карту, наприклад пікового короля. Що Ви зробите? Думаю, що здогадатися неважко, перше, що приходить в голову, це послідовно перебирати всі карти, до тих пір, поки потрібна не знайдеться. При найгіршому збігу обставин Вам доведеться перебрати всі карти в колоді, що насправді не так довго, якщо чесно.

Спробуємо трохи змінити умову. Шукати нам треба не карту, а конверт з певною адресою. Конвертів цих перед Вами лежить неміряна кількість, якщо окинути поглядом завалені столи, ну декілька сотень як мінімум. Спосіб, тільки що випробуваний на колоді карт, дуже скоро натомить. Навряд чи хто в цьому сумнівається, чи не так?

А ось якщо заздалегідь всі ці конверти розкласти в алфавітному порядку, то подальша робота по знаходженню цілком певного імені вже не представляється такою жахливою! Звичайно, на сортування необхідно витратити цілком певні сили і час, але вони окупляться при багаторазовому пошуку, ось що найголовніше

Пригадавши приклад з картами, відзначимо, що в тому разі витрачати час на попереднє сортування колоди навряд чи стоїть...

Отже, ми можемо зробити перший і дуже важливий вивід - оптимальність методу пошуку залежить від розміру масиву, в якому ми шукаємо! Прямий перебір всіх значень простий в розумінні, легкий у виконання і достатньо швидкий на малих масивах даних. Легкість і простота - вагомий аргумент, адже Вам після того, як буде вибраний певний метод, необхідно ще формалізувати його і закодувати. У результаті програміста інетересуєт код.

Отже, все це в сукупності дозволяє сказати, що метод прямого перебору оптимальний для малих масивів.

Якщо ж масив даних достатньо великий, то оптимальність пошуку досягається попереднім сортуванням значень в масиві.

Існує декілька класичних способів пошуку значення у відсортованому масиві. Ми розглянемо деякі. Вони були запропоновані в 60-х роках і мало змінилися у наш час.

Один з них дуже відомий, адже Вам напевно доводилося чути такі назви як "метод дихотомії", "бінарного дерева" або "метод половинного ділення", що власне одне і теж. Ось з нього і почнемо.

Суть цього алгоритму достатньо проста. Уявимо собі, що у нас є набір карток з телефонними номерами і адресами людей. Картки відсортовані в порядку зростання телефонних номерів. Необхідно знайти адресу людини, якщо ми знаємо, що його номер телефону 222-22-22. Наші дії? Беремо картку з середини пачки, номер картки 444-44-44. Порівнюючи його з шуканим номером, ми бачимо, що наш менше і, значить, знаходиться точно в першій половині пачки. Сміливо відкладаємо другу частину пачки убік, вона нам не потрібна, масив пошуку ми звузили рівно в два рази. Тепер беремо картку з середини пачки, що залишилася, на ній номер 123-45-67. З чого виходить, що потрібна нам картка лежить в другій половині пачки, що залишилася... Таким чином, при кожному порівнянні, ми зменшуємо зону пошуку в два рази. Звідси і назва методу - половинного ділення або дихотомії.

(Логарифм числа а по підставі b визначається як показник ступеня, у яку треба звести число b, щоб отримати число а. Позначення: logba. З визначення виходить, що записи logba = x і bx = а еквівалентні.

Приклад: log28 = 3, тому що 23 = 8.)

Швидкість збіжності цього алгоритму пропорційна Log(2) N ^-1. Це означає буквально те, що не більш, ніж через Log(2) N порівнянь, ми або знайдемо потрібне значення, або переконаємося в його відсутності.

Інша назва цього алгоритму - «метод бінарного дерева» походить з представлення "шляху" пошуку у вигляді дерева.