Послідовний пошук
Завдання пошуку. Нехай задані лінійні списки: список елементів В=<К1, К2, К3,.., Кn> і список ключів V= (у простому випадку це цілі числа). Вимагається для кожного значення Vi з V знайти безліч усіх співпадаючих з ним елементів з В. Найчастіше зустрічається ситуація коли V містить один елемент, а у В є не більше за один такий елемент.
Ефективність деякого алгоритму пошуку А оцінюється максимальним Max{А} і середнім Avg{А} кількостями порівнянь, необхідних для знаходження елементу V у В. Якщо Pi - відносна частота використання елементу Кi у В, а Si - кількість порівнянь, необхідна для його пошуку, то
n Max{А} = max{ Si, i=1, n } ; Avg{А} = Pi Si . i=1 Послідовний пошук передбачає послідовний перегляд усіх елементів списку У в порядку їх розташування, поки не знайдеться елемент рівний V. Якщо достовірно невідомо, що такий елемент є в списку, то необхідно стежити за тим, щоб пошук не вийшов за межі списку, що досягається використанням стоппера.
Очевидно, що Max послідовного пошуку рівний N. Якщо частота використання кожного елементу списку однакова, тобто P=1/N, то Avg послідовного пошуку рівне N/2. При різній частоті використання елементів Avg можна поліпшити, якщо помістити елементи, що часто зустрічаються, в початок списку.
Нехай у вхідному потоці задано 100 цілих чисел К1, К2,.. К100 і ключ V. Складемо програму для послідовного зберігання елементів Кi і пошуку серед них елементу, рівного V, причому такого елементу може і не бути в списку. Без використання стоппера програма може бути реалізована таким чином:
Інтернполяці
Уявіть собі, що Ви шукаєте слово в словнику. Маловірогідно, що Ви спочатку загляньте в середину словника, потім відступите від початку на 1/4 або 3/4 і т.д, як в бінарному пошуку.
Якщо потрібне слово починається з букви 'А', ви напевно почнете пошук десь на початку словника. Коли знайдена відправна точка для пошуку, ваші подальші дії мало схожі на розглянуті вище методи.
Якщо Ви помітите, що шукане слово повинне знаходитися набагато далі відкритої сторінки, ви пропустите порядну їх кількість, перш ніж зробити нову спробу. Це в корені відрізняється від попередніх алгоритмів, що не роблять різниці між 'багато більше' і трохи 'більше'.
Ми приходимо до алгоритму, званого інтерполяційним пошуком: Якщо відомо, що До лежить між Kl і Ku, то наступну пробу робимо на відстані(Ku - Kl) від l, припускаючи, що ключі є числами, що зростають приблизно в арифметичній прогресії.
// Пошук в масиві K[1.N] числа X інтерполяційним пошуком l=1; u=N;
while(u>=l){ i=l(K[u]- K[l]);
if(X<K[i]] u=i - 1;
else if(X>K[i]] l=i+1;
else ЗНАЙШЛИ, X==K[i].
}
Не знайшли.
Інтерполяційний пошук працює за log log N операцій, якщо дані розподілені рівномірно. Як правило, він використовується лише на дуже великих таблицях, причому робиться декілька кроків інтерполяційного пошуку, а потім на малому підмасиві використовується бінарний або послідовний варіанти.
Дайте визначення BST-дерева і наведіть особливості реалізації пошуку на основі таких дерев.
Бінарне (двійкове) дерево (binary tree) - це впорядковане дерево, кожна вершина якого має не більше двох піддерев, причому для кожного вузла виконується правило: в лівому поддереве містяться тільки ключі, що мають значення, менші, ніж значення цього вузла, а в правому поддереве містяться тільки ключі, що мають значення, більші, ніж значення цього вузла.
Бінарне дерево є рекурсивною структурою, оскільки кожне його поддерево само є бінарним деревом і, отже, кожен його вузол у свою чергу є коренем дерева.
Вузол дерева, що не має нащадків, називається листом.
Схемне зображення бінарного дерева : малюнок
Бінарне дерево може бути порожньою множиною.
Бінарне дерево може звиродніти в список:
