13. Vyhledávání Flashcards
Co je vyhledávání a jaké jsou základní principy vyhledávacích struktur?
Vyhledávání je proces lokalizace jednoho nebo více objektů v datové struktuře. Vyhledávací struktura je speciálně navržená struktura dat, která umožňuje efektivní vyhledávání dat, například binární vyhledávací stromy, AVL stromy, B-stromy, hashtabulky.
Jak funguje lineární a binární vyhledávání?
- Lineární vyhledávání: Prochází každý prvek neuspořádaného seznamu nebo pole od začátku do konce, dokud nenalezne hledaný prvek. Časová složitost: O(n).
- Binární vyhledávání: Efektivní na uspořádaných polích, dělí pole na poloviny a zúží vyhledávání na relevantní část. Časová složitost: O(log n).
Co je interpolační vyhledávání a jaké jsou jeho vlastnosti?
Interpolační vyhledávání je varianta binárního vyhledávání, která volí index pro kontrolu na základě distribuce klíčových hodnot. Je velmi rychlé na datových setech s rovnoměrnou distribucí. Časová složitost: O(log log n) v nejlepším případě, O(n) v nejhorším případě.
Co je binární vyhledávací strom (BST) a jaké jsou jeho vlastnosti?
Binární vyhledávací strom je datová struktura, kde každý uzel má až dva potomky: “levý” (menší hodnota) a “pravý” (větší hodnota). Umožňuje efektivní vyhledávání, vkládání a mazání prvků. Časová složitost pro vyhledávání: O(log n) v nejlepším a průměrném případě, O(n) v nejhorším případě.
Co je AVL strom a jaké jsou jeho vlastnosti?
AVL strom je typ binárního vyhledávacího stromu, který je samo vyvažující se. Každý uzel uchovává informaci o “výšce” a strom se při každé operaci vkládání nebo mazání automaticky vyvažuje. Vlastnosti:
- Výška stromu je logaritmicky proporcionální k počtu uzlů, což zajišťuje efektivní operace.
- Rotace (jednoduchá a dvojitá) se používají k udržení vyvážení po každé operaci.
- Časová složitost pro vyhledávání, vkládání a mazání: O(log n).
Jak vypadá základní operace v AVL stromu?
- Vložení: Při vkládání nového prvku se AVL strom automaticky vyvažuje pomocí rotací (jednoduchých nebo dvojitých), aby byla zajištěna optimální výška stromu.
- Vyhledávání: Vyhledávací operace v AVL stromu sleduje standardní binární vyhledávání, což zaručuje časovou složitost O(log n).