Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revisionNext revision | Previous revision | ||
| statnice:bakalar:b4b33alg [2025/06/08 14:06] – [Kolize v hashovacích tabulkách] zapleka3 | statnice:bakalar:b4b33alg [2026/06/06 17:15] (current) – [Counting Sort] knedl1k | ||
|---|---|---|---|
| Line 1: | Line 1: | ||
| - | ==== Základní algoritmy a datové struktury pro vyhledávání a řazení. Vyhledávací stromy, rozptylovací tabulky. Prohledávání grafu. Úlohy dynamického programování. Asymptotická složitost a její určování. ==== | + | ====== Základní algoritmy a datové struktury pro vyhledávání a řazení. Vyhledávací stromy, rozptylovací tabulky. Prohledávání grafu. Úlohy dynamického programování. Asymptotická složitost a její určování. |
| [[https:// | [[https:// | ||
| Line 476: | Line 476: | ||
| === Mazání === | === Mazání === | ||
| * Najdeme a odstraníme klíč (případně jej nahradíme in-order předchůdcem/ | * Najdeme a odstraníme klíč (případně jej nahradíme in-order předchůdcem/ | ||
| - | * Při návratu nahoru testujeme balance; pokud je mimo intervál | + | * Při návratu nahoru testujeme balance; pokud je mimo interval |
| * V nejhorším provedeme až $O(\log n)$ rotací | * V nejhorším provedeme až $O(\log n)$ rotací | ||
| Line 483: | Line 483: | ||
| * prakticky používá v databázových systémech a souborových systémech. | * prakticky používá v databázových systémech a souborových systémech. | ||
| - | B-strom je řízen parametrem **minimální stupeň | + | B-strom je řízen parametrem **minimální stupeň |
| - | * Každý uzel (kromě kořene) má alespoň $t - 1$ a nejvýše $2t - 1$ klíčů. | + | * Každý uzel (kromě kořene) má alespoň $\lfloor |
| * Z toho plyne, že každý vnitřní uzel má mezi $t$ až $2t$ potomků. | * Z toho plyne, že každý vnitřní uzel má mezi $t$ až $2t$ potomků. | ||
| * Kořen může mít méně než $t - 1$ klíčů. | * Kořen může mít méně než $t - 1$ klíčů. | ||
| Line 493: | Line 493: | ||
| * Každý uzel má minimální a maximální počet klíčů (viz definice $t$ výše). | * Každý uzel má minimální a maximální počet klíčů (viz definice $t$ výše). | ||
| - | * Když uzel překročí maximální počet klíčů ($2t - 1$), rozdělí se na dva uzly a prostřední klíč se přesune do rodiče. | + | * Když uzel překročí maximální počet klíčů ($2t$), rozdělí se na dva uzly a prostřední klíč se přesune do rodiče. |
| * Pokud rodič také překročí maximální počet klíčů, proces se opakuje až ke kořeni. | * Pokud rodič také překročí maximální počet klíčů, proces se opakuje až ke kořeni. | ||
| Line 504: | Line 504: | ||
| === Vkládání === | === Vkládání === | ||
| * Klíč vkládáme do správného listu. | * Klíč vkládáme do správného listu. | ||
| - | * Pokud uzel překročí $2t - 1$ klíčů: | + | * Pokud uzel překročí $2t$ klíčů: |
| * Rozdělíme ho na dvě části. | * Rozdělíme ho na dvě části. | ||
| * Prostřední klíč přesuneme do rodiče. | * Prostřední klíč přesuneme do rodiče. | ||
| Line 512: | Line 512: | ||
| === Mazání === | === Mazání === | ||
| - | * Pokud uzel klesne pod $t - 1$ klíčů, musíme situaci opravit: | + | * Pokud uzel klesne pod $\lfloor |
| * **Borrow** – vypůjčíme si klíč od sourozence. | * **Borrow** – vypůjčíme si klíč od sourozence. | ||
| * **Merge** – sloučíme uzel se sourozencem a jeden klíč stáhneme z rodiče. | * **Merge** – sloučíme uzel se sourozencem a jeden klíč stáhneme z rodiče. | ||
| Line 723: | Line 723: | ||
| ==== Counting Sort ==== | ==== Counting Sort ==== | ||
| - | Nevyužívá porovnávání, | + | Nevyužívá porovnávání, |
| * Stabilní, velmi rychlý: $O(n + k)$ (k … rozsah hodnot) | * Stabilní, velmi rychlý: $O(n + k)$ (k … rozsah hodnot) | ||
