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 [2014/10/27 09:07] 127.0.0.1 upraveno mimo DokuWiki |
home:inf:ap15 [2020/04/12 16:56] (aktuální) |
||
|---|---|---|---|
| Řádek 168: | Řádek 168: | ||
| ==== Vyhledávací stromy a jejich modifikace ==== | ==== Vyhledávací stromy a jejich modifikace ==== | ||
| - | Datovou strukturu strom lze výhodně použít k ukládání údajů a vyhledávání nad nimi. **Biná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: | + | Datovou strukturu strom lze výhodně použít k ukládání údajů a vyhledávání nad nimi. **Bi |
| + | 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ší než X a všechny uzly v pravém podstromu vrcholu V obsahují hodnoty větší než X. | + | * 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ů: | ||
| Řádek 188: | Řádek 189: | ||
| ==== Halda ==== | ==== Halda ==== | ||
| - | **Halda** (//heap//) je speciální datová struktura, která má také tvar binárního stromu, ale využívá se nejen k vyhledávání, ale např. i třídění pomocí haldy. Halda je binární strom, pro který jsou splněny následující podmínky:((Tyto podmínky platí pro častější, tzv. minimovou haldu. Maximová halda je definována podobně, až na nerovnost v bodě 3, která je obrácená.)) | + | **Halda** (//heap//) je speciální datová struktura, která má také tvar binárního stromu, ale využívá se nejen k vyhledávání, ale např. |
| + | i třídění pomocí haldy. Halda je binární strom, pro který jsou splněny následující podmínky:((Tyto podmínky platí pro častější, tzv. minimovou haldu. Maximová halda je definována podobně, až na nerovnost v bodě 3, která je obrácená.)) | ||
| - V každé hladině od první až do předposlední je maximální možný počet uzlů, tzn. v //k//-té hladině je 2<sup>//k//-1</sup> uzlů. | - V každé hladině od první až do předposlední je maximální možný počet uzlů, tzn. v //k//-té hladině je 2<sup>//k//-1</sup> uzlů. | ||
| - V poslední hladině jsou všechny uzly umístěny co možná nejvíce "vlevo", tj. při procházení stromu do hloubky zleva nejprve mají uzly předposlední hladiny dva následníky, pak může být jeden s jedním následníkem a zbývající takové uzly jsou pak už bez následníků. | - V poslední hladině jsou všechny uzly umístěny co možná nejvíce "vlevo", tj. při procházení stromu do hloubky zleva nejprve mají uzly předposlední hladiny dva následníky, pak může být jeden s jedním následníkem a zbývající takové uzly jsou pak už bez následníků. | ||
