Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revision | |||
| statnice:bakalar:b4b33alg [2025/06/08 14:07] – zapleka3 | statnice:bakalar:b4b33alg [2025/06/13 10:41] (current) – [B-stromy] prokop | ||
|---|---|---|---|
| Line 484: | Line 484: | ||
| B-strom je řízen parametrem **minimální stupeň _t_ (t ≥ 2)**: | B-strom je řízen parametrem **minimální stupeň _t_ (t ≥ 2)**: | ||
| - | * Každý uzel (kromě kořene) má alespoň $t - 1$ a nejvýše $2t - 1$ klíčů. | + | * Každý uzel (kromě kořene) má alespoň $floor(t/2)$ a nejvýše $2t$ klíčů. |
| * 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 $floor(t/2)$ klíčů, musíme situaci opravit: |
| * **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. | ||
