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/13 10:41] – [B-stromy] prokop | statnice:bakalar:b4b33alg [2026/06/06 17:15] (current) – [Counting Sort] knedl1k | ||
|---|---|---|---|
| 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ň $floor(t/2)$ a nejvýše $2t$ 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 512: | Line 512: | ||
| === Mazání === | === Mazání === | ||
| - | * Pokud uzel klesne pod $floor(t/2)$ 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) | ||
