13. Vyhledávání

Question 1

Co je vyhledávání a jaké jsou základní principy vyhledávacích struktur?

Answer 1

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.

Question 2

Jak funguje lineární a binární vyhledávání?

Answer 2

• 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).

Question 3

Co je interpolační vyhledávání a jaké jsou jeho vlastnosti?

Answer 3

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ě.

Question 4

Co je binární vyhledávací strom (BST) a jaké jsou jeho vlastnosti?

Answer 4

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ě.

Question 5

Co je AVL strom a jaké jsou jeho vlastnosti?

Answer 5

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).

Question 6

Jak vypadá základní operace v AVL stromu?

Answer 6

• 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).