Структуре података претраге
У рачунарству, претрага структуре података је свака структура података која дозвољава повраћај специфичних елемената из скупа елемената, као што је база података.
Најједноставнија, најопштија, а најмање ефикасна претрага структура је само неуређена секвенциона листа свих елемената. Лоцирање жељене ставке у таквој листи, са методом линеарне претраге, неминовно захтева низ операција пропорционалних броју н ставки, у најгорем могућем случају као и у просечном случају. Корисне претраге структуре података омогућавају бржу претрагу; међутим, они су ограничени на упите неке специфичне врсте. Штавише, пошто трошкови изградње таквих структура су барем пропорционални Н, они ће се исплатити само ако се неколико упита треба извршити на истој бази података (или на бази података која се мало мења између упита).
Статичке претраге структура података су дизајниране за одговарање многих упита ка фиксној бази података; Динамичке структуре такође омогућавају уметање, брисање или измену ставки између узастопних упита. У динамичном случају, морају се такође узети у обзир трошкови поправљања структура претраге за одговарајуће промене у бази података.
Класификација[уреди | уреди извор]
Најједноставнија врста упита је да се пронађе запис који има специфичну област (тј. кључ) једнак одређеној вредности В. Друге уобичајене врсте упита су „пронађи ставку са најмањом (или највећом) вредности кључа“, „наћи ставку са највећом вредности кључа која не прелази В", „наћи све ставке са вредностима кључа између наведених граница В<суб>мин</суб> and В<суб>макс</суб>".
У неким базама кључне вредности могу бити тачке у неким димензионим просторима. На пример, кључ може да буде географски положај(географска ширина и географска дужина) на Земљи. У том случају, најчешћи типови упита су нађи запис са вредности кључа најближој датој тачки В", или „нађи све ставке чији кључ лежи у одређеном растојању од В", или „нађи све ставке унутар одређеног простора Р ".
Специјални случај су истовремени опсег упита са два или више једноставних кључева, као што су „нађи све податке о запосленима са платом између 50.000 и 100.000 и ѕапосленим између 1995 и 2007".
Појединачни уређени кључеви[уреди | уреди извор]
- Низ
- По приоритету сортирана листа; погледати Линеарна претрага
- По кључу сортирани низ; погледати бинарна претрага
- Бинарно стабло претраге
- Хеш таблице
Проналажење најмањег елемента[уреди | уреди извор]
Асимптотска анализа најгорег могућег сценарија[уреди | уреди извор]
У овој таблици, асимптотска нотација O(Ф(Н)) значи „не прелази неки фиксни множилац од Ф(Н) у најгорем могућем сценарију."
| Уметни | Обриши | Индекс | Претрага | Нађи максимум-минимум | Заузеће простора | |
|---|---|---|---|---|---|---|
| Несортирани низ | O(n) | O(n) | O(1) | O(n) | O(n) | O(n) |
| Сортирани низ | O(n) | O(n) | O(1) | O(log n) | O(1) | O(n) |
| Несортирана повезана листа | O(1)* | O(1)* | O(n) | O(n) | O(n) | O(n) |
| Сортирана повезана листа | O(1)* | O(1)* | O(n) | O(n) | O(n) | O(n) |
| Самобалансирајуће бинарно стабло претраге | O(log n) | O(log n) | N/A | O(log n) | O(log n) | O(n) |
| Хип | O(log n) | O(log n)** | N/A | O(n) | O(1) | O(n) |
| Хеш таблице | O(1) | O(1) | N/A | O(1) | O(n) | O(n) |
Ова таблица је само приближна; за сваку структуру података постоје посебне ситуације и варијанте које могу довести до различитих резултата. Такође, две или више структуре података могу се комбиновати да се добију нижи трошкови.