13. Vyhledávání Flashcards

1
Q

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

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

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

A
  • 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).
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Co je AVL strom a jaké jsou jeho vlastnosti?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

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

A
  • 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).
How well did you know this?
1
Not at all
2
3
4
5
Perfectly