hledat
Rozdíly
Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.
| Obě strany předchozí revize Předchozí verze Následující verze | Předchozí verze | ||
|
home:inf:ap15 [2016/02/08 04:28] whush [Vyhledávací stromy a jejich modifikace] |
home:inf:ap15 [2020/04/12 16:56] (aktuální) |
||
|---|---|---|---|
| Řádek 171: | Řádek 171: | ||
| nární vyhledávací strom** je (na rozdíl od předchozích trochu složitější) datová struktura používaná pro ukládání a vyhledávání údajů. Je to binární strom, v jehož uzlech jsou umístěna data. Přitom pro uspořádání hodnot uložených ve stromu platí následující pravidlo: | nární vyhledávací strom** je (na rozdíl od předchozích trochu složitější) datová struktura používaná pro ukládání a vyhledávání údajů. Je to binární strom, v jehož uzlech jsou umístěna data. Přitom pro uspořádání hodnot uložených ve stromu platí následující pravidlo: | ||
| - | * Je-li ve vrcholu V uložena hodnota X, pak všechny uzly v levém podstromu vrcholu V obsahují hodnoty menší, nebo rovny X a všechny uzly v pravém podstromu vrcholu V obsahují hodnoty větší, nebo rovny X. (Hodnoty rovny X je výhodné povolit v pravém i levém podstromu z důvodu krajního případů, například když je BVS vyvážený - viz. níže a obsahuje jen prvky jedné hodnoty) | + | * Je-li ve vrcholu V uložena hodnota X, pak všechny uzly v levém podstromu vrcholu V obsahují hodnoty menší, nebo rovny X a všechny uzly v pravém podstromu vrcholu V obsahují hodnoty větší, nebo rovny X. (Hodnoty rovny X je výhodné povolit v pravém i levém podstromu z důvodu krajních případů, například když je BVS vyvážený (viz. níže) a obsahuje jen prvky jedné hodnoty) |
| Časová složitost operací nad vyhledávacím stromem závisí na jeho výšce. Bude-li množina uložených údajů předem pevně dána, není problém vybudovat tzv. **vyvážený vyhledávací strom**. Pokud se budou data v průběhu programu měnit, lze pro zajištění vyváženosti či další optimalizace vyhledávání obecně a v různých konkrétních případech zavést některou z modifikací vyhledávacích stromů: | Časová složitost operací nad vyhledávacím stromem závisí na jeho výšce. Bude-li množina uložených údajů předem pevně dána, není problém vybudovat tzv. **vyvážený vyhledávací strom**. Pokud se budou data v průběhu programu měnit, lze pro zajištění vyváženosti či další optimalizace vyhledávání obecně a v různých konkrétních případech zavést některou z modifikací vyhledávacích stromů: | ||
